نظرية البيان

هو زوج مرتب ${\displaystyle G=(V,E)}$ يشمل مجموعة ${\displaystyle V\{a,b,c,d,...\}}$ من الرؤوس ومجموعة ${\displaystyle E\{\{a,c\},\{b,d\},\{a,d\},...\}}$ من الأضلاع والتي هي بدورها مجموعة ثنائيات جزئية غير مرتبة من ${\displaystyle V}$ ويعرف هذا النوع من البيانات بالبيان البسيط غير الموجه.

• إذا كان الضلع مزوداً باتجاه (سهم) أصبح البيان موجهاً وأصبحت مجموعة الأضلاع ${\displaystyle E\{(a,b),(b,c),(d,a),...\}}$ مجموعة ثنائيات مرتبة من ${\displaystyle V}$.

• 
  بيان موجه
• 
  بيان غير موجه

هو عدد عقد (رؤوس) البيان (مثال: بيان فيه 3 رؤوس هو بيان من المرتبة الثالثة).

هو عدد حروف (أضلاع) البيان.

• درجة عقدة (رأس) البيان الغير موجه:${\displaystyle \deg(v).}$ : هي عدد الأضلاع المتصلة بالعقدة.
• درجة عقدة (رأس) البيان الموجه : يوجد نوعان من الدرجات

1. درجة الدخول للعقدة ${\displaystyle \deg ^{-}(v)}$ : وهي عدد الأضلاع الداخلة إلى عقدة.
2. درجة الخروج للعقدة ${\displaystyle \deg ^{+}(v)}$ : وهي عدد الأضلاع الخارجة من عقدة.

• درجة البيان غير الموجه ${\displaystyle \sum _{v\in V}\deg(v)}$ : هي مجموع درجات العقد فيه.

حيث:

${\displaystyle \sum _{v\in V}\deg(v)=2|E|\,}$

• درجة البيان الموجه :

1. درجة الدخول ${\displaystyle \sum _{v\in V}\deg ^{-}(v)}$: هي مجموع درجات دخول العقد.
2. درجة الخروج ${\displaystyle \sum _{v\in V}\deg ^{+}(v)}$ : هي مجموع درجات خروج العقد.

حيث:

${\displaystyle \sum _{v\in V}\deg ^{+}(v)=\sum _{v\in V}\deg ^{-}(v)=|E|\,}$

مثال:

بيان غير موجه تحمل كل عقدة فيه درجتها وتكون درجته:

${\displaystyle \sum _{v\in V}\deg(v)=0+1+3+2+3+5+2=16}$

هو بيان لا يحوي حلقة ذاتية (Self-loop) أو أضلاع مكررة (Multiple-edges).

• 
  بيان بسيط

هو بيان لا يحوي حلقة ذاتية (Self-loop) ولكن يحتوي على الأقل على ضلع مكرر (Multiple-edge).

• 
  بيان متعدد

هو بيان يحوي حلقات ذاتية (Self-loops) وأضلاع مكررة (Multiple-edges).

• 
  بيان زائف

نقول عن بيان ${\displaystyle G}$ أنه منتظم من الدرجة ${\displaystyle r}$ إذا كانت درجة كل عقدة من البيان ${\displaystyle G}$ هي ${\displaystyle r}$ .

• 
  بيان منتظم من الدرجة 3

الطريق في بيان ${\displaystyle G}$ هو متتالية متناوبة من العقد والأضلاع:${\displaystyle W=v_{0},e_{1},v_{1},e_{2},v_{2},...,v_{n-1},e_{n},v_{n}}$ تبدأ وتنتهي بالعقد بحيث أن ${\displaystyle e_{i}=v_{i-1},v_{i}(i=1,2,3,...,n)}$.

• (e دلالة على الضلع و v دلالة على العقدة)

في الشكل 1 :

${\displaystyle W=a,e_{1},b,e_{2},c,e_{3},g,e_{4},d}$

هو طريق طوله 4 (طول الطريق يعرف بعدد أضلاعه).

• القافلة: هي طريق لا يحوي أضلاع مكررة.

من الشكل 1 نجد القافلة التالية:

${\displaystyle a,e_{1},b,e_{6},a,e_{9},c,e_{8},d}$

• المسار: هو طريق لا يحوي عقد مكررة.

• 
  مسار يحوي 6 عقد

• كل مسار هو قافلة ولكن العكس غير صحيح.

هي مسار يبدأ وينتهي بنفس العقدة. في الشكل 1 نجد الحلقة التالية:

${\displaystyle a,e_{1},b,e_{2},c,e_{3},g,e_{4},d,e_{5},a}$.

هو بيان من المرتبة ${\displaystyle n}$ فيه كل عقدتين متمايزتين متصلتين ونرمز له بـ ${\displaystyle K_{n}}$.
البيان التام من المرتبة ${\displaystyle n}$ هو بيان منتظم من المرتبة ${\displaystyle n-1}$ وحجمه يعطى بالعلاقة:

${\displaystyle |E|={\binom {n}{2}}={\frac {n(n-1)}{2}}}$

• 
  بيان كامل ${\displaystyle K_{7}}$

إذا كانت لدينا حلقة Cn. فالعجلة فيها رأس واحد يجاور جميع رؤوس البيان الأخرى ورمز العجلة Wn

هو بيان فيه 14 عقدة و21 ضلع.

• 
  ${\displaystyle KG_{5,2}}$

• 
  الشكل الأكثر شهرة لبيان بيترسن

إذا كانت قمتين من مخطط مرتبطتان بحرف، نقول أنهما متجاورتان أو مرتبطتان.

مربع مخطط هو مخطط له نفس قمم المخطط الأول وله نفس الحروف أو الأقواس بالإضافة إلى وجود حروف أو أقواس تربط بين القمم التي لها جوارات مشتركة.

السلسلة أو السبيل هو جزء من مخطط يربط بين قمتين بواسطة أزواج قمم مرتبط مثنى مثنى على التوالي.

البئر هو عقدة في بيان موجه درجة خروجه منعدمة. أي: ${\displaystyle \deg ^{+}(v)=0}$

المنبع هو عقدة في بيان موجه درجة دخوله منعدمة. أي: ${\displaystyle \deg ^{-}(v)=0}$

المخطط المكمل لمخطط هو مخطط له نفس القمم مرتبطة إذا لم تكن مرتبطة في المخطط الأصلي.

المسار هو سلسلة رؤوس مرتبطة، لها بداية ونهاية (نقطة انطلاق ونقطة وصول).

إذا كانت نقطتي الانطلاق والوصول منطبقتين، المسار يكون مغلقا.

مسار أولير لمخطط G غير موجه هو مسار يمر بكل الحروف مرة واحدة فقط.

نقول أن المخطط متصل إذا كان يحتوي على مسار أولير، وكل رؤوسه من درجة مزدوجة

مسار هاميلتون لمخطط G هو مسار يمر بكل القمم مرة واحدة فقط.

المخطط الكامل هو مخطط بسيط يكون كل زوج من رؤوسه متصلان بضلع. بحيث أن المخطط الكامل ذو n رأس يكون له n(n-1)/2 ضلع.

المخطط المستقر هو مخطط ليس له حروف.

المخطط المستوي هو مخطط يمكن تمثيله بكيفية لا تتقاطع الحروف فيه.

مخطط يمكن الوصول فيه من أي عقدة إلى أي عقدة أخرى.