نظرية المخططات

نظرية المخططات أو نظرية البيان (Graph theory)‏ هي نظرية في الرياضيات وعلوم الحاسب، تدرس خواص المخططات حيث يتم تمثيل مجموعة كائنات تدعى رؤوسا، ترتبط ببعضها بأضلاع و تدعى أحيانا أقواسا، يمكن أن تكون موجهة أي مزودة باتجاه (تستخدم الاسهم بدل الأضلاع) أو بدون اتجاه (أضلاع فقط). التمثيل لهذا المخطط يكون على الورق بمجموعة نقاط تمثل الرؤوس متصلة بخطوط هي حروف (أضلاع أو أسهم) المخطط. رياضياً يُمكن أن يُعطى المخطط عبر مصفوفة المجاورة (Adjacency Matrix).

تُمكن الاستعانة بالمخططات من حلحلة الكثير من المشاكل العملية، فمثلا بنية موسوعة ويكيبيديا يمكن تمثيلها بمخطط رؤوسه هي أسماء المقالات ونقوم برسم خط موجه بين مقالتين من أ إلى ب إذا كانت المقالة أ تحوي رابطا إلى المقالة ب. تطبيقات هذه النظرية واسعة جدا ولحل مشاكلها يستخدم الحاسوب بشكل واسع. لذلك تهتم علوم الحاسوب بتصميم خوارزميات لنظرية المخططات حيث يمكن معالجة أي مخطط لتمييز خصائصه واستخلاص المعلومات منه.

تاريخ

يعد البحث الذي كتبه ليونهارد أويلر ونشره في عام 1736 حول موضوع جسور كونيغسبرغ السبعة أول بحث في التاريخ في نظرية المخططات^[1]. هذا البحث بالإضافة إلى المقالة التي كتبها فانديرموند عن مسألة الفارس، بالإضافة إلى العمل الذي قام به غوتفريد لايبنتز في وضع علاقات لعدد الرؤوس بالأضلاع وأوجه متعددات السطوح المحدبة تعتبر بدايات لعلم الطوبولوجيا.

تعاريف

البيان (Graph)

هو زوج مرتب ${\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}$.

• 

  بيان موجه

• 

  بيان غير موجه

ترتيب البيان ${\displaystyle |V|}$

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

حجم البيان ${\displaystyle |E|}$

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

درجة العقدة

• درجة عقدة (رأس) البيان الغير موجه:${\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}$

أنواع البيانات

1- البيان البسيط (Simple Graph)

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

• 

  بيان بسيط

2- البيان المتعدد (Multigraph)

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

• 

  بيان متعدد

3- البيان الزائف أو شبه البيان (Pseudograph)

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

• 

  بيان زائف

4- البيان المنتظم (Regular Graph)

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

• 

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

5-الطريق (Walk)

الطريق في بيان ${\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 (طول الطريق يعرف بعدد أضلاعه).

6-القافلة (Trail) والمسار (Path)

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

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

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

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

• 

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

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

7- الحلقة (Cycle Graph)

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

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

8- البيان التام أو الكامل (Complete Graph)

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

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

• 

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

9- العجلة (Wheel Graph)

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

10- البيان المكعب (Cubic graph)

بعض البيانات الخاصة

1- بيان هيوود (Heawood Graph)

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

• 

2- بيان نيسر (Kneser Graph)

• 

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

3- بيان بيترسن (Petersen Graph)

• 

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

تعاريف إضافية

الارتباط والجوار

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

مربع مخطط

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

سلاسل وسبل

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

البئر

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

المنبع

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

مخطط مكمل

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

مسار ومسار مغلق

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

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

مسار أولير

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

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

مسار هاميلتون

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

مخطط كامل

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

مخطط مستقر

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

مخطّط مستوي

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

مخطط قوي التوصيل

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

تمثيلات

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

مسائل

1. مشكلة الرحالة التاجر
2. مشكلة تلوين المخطط
3. تساوي شكلي مخططين

مقالات ذات صلة

• نظرية الشبكات
• مصفوفة المجاورة

مراجع

موسوعات ذات صلة :

• موسوعة رياضيات
• موسوعة علم الاجتماع
• موسوعة علم الحاسوب