نظرية المخططات
نظرية المخططات أو نظرية البيان هي نظرية في الرياضيات وعلوم الحاسب، تدرس خواص المخططات حيث يتم تمثيل مجموعة كائنات تدعى رؤوسا، ترتبط ببعضها بأضلاع و تدعى أحيانا أقواسا، يمكن أن تكون موجهة أي مزودة باتجاه (تستخدم الاسهم بدل الأضلاع) أو بدون اتجاه (أضلاع فقط). التمثيل لهذا المخطط يكون على الورق بمجموعة نقاط تمثل الرؤوس متصلة بخطوط هي حروف (أضلاع أو أسهم) المخطط. رياضياً يُمكن أن يُعطى المخطط عبر مصفوفة المجاورة (Adjacency Matrix).
تُمكن الاستعانة بالمخططات من حلحلة الكثير من المشاكل العملية، فمثلا بنية موسوعة ويكيبيديا يمكن تمثيلها بمخطط رؤوسه هي أسماء المقالات ونقوم برسم خط موجه بين مقالتين من أ إلى ب إذا كانت المقالة أ تحوي رابطا إلى المقالة ب. تطبيقات هذه النظرية واسعة جدا ولحل مشاكلها يستخدم الحاسوب بشكل واسع. لذلك تهتم علوم الحاسوب بتصميم خوارزميات لنظرية المخططات حيث يمكن معالجة أي مخطط لتمييز خصائصه واستخلاص المعلومات منه.
يعد البحث الذي كتبه ليونهارد أويلر ونشره في عام 1736 حول موضوع جسور كونيغسبرغ السبعة أول بحث في التاريخ في نظرية المخططات. هذا البحث بالإضافة إلى المقالة التي كتبها فانديرموند عن مسألة الفارس، بالإضافة إلى العمل الذي قام به غوتفريد لايبنتز في وضع علاقات لعدد الرؤوس بالأضلاع وأوجه متعددات السطوح المحدبة تعتبر بدايات لعلم الطوبولوجيا.
هو زوج مرتب formula_1 يشمل مجموعة formula_2 من الرؤوس و مجموعة formula_3 من الأضلاع والتي هي بدورها مجموعة ثنائيات جزئية غير مرتبة من formula_4 ويعرف هذا النوع من البيانات بالبيان البسيط غير الموجه.
هو عدد عقد (رؤوس) البيان (مثال: بيان فيه 3 رؤوس هو بيان من المرتبة الثالثة) .
هو عدد حروف (أضلاع) البيان.
حيث :حيث:
مثال:
بيان غير موجه تحمل كل عقدة فيه درجتها وتكون درجته:
هو بيان لا يحوي حلقة ذاتية(Self-loop) أو أضلاع مكررة(Multiple-edges).
هو بيان لا يحوي حلقة ذاتية(Self-loop) ولكن يحتوي على الأقل على ضلع مكرر(Multiple-edge).
هو بيان يحوي حلقات ذاتية(Self-loops) و أضلاع مكررة(Multiple-edges).
نقول عن بيان formula_18 أنه منتظم من الدرجة formula_19 إذا كانت درجة كل عقدة من البيان formula_18 هي formula_19 .
الطريق في بيان formula_18 هو متتالية متناوبة من العقد والأضلاع
تبدأ وتنتهي بالعقد بحيث أن formula_24.
في الشكل 1 :
هو طريق طوله 4 (طول الطريق يعرف بعدد أضلاعه).
من الشكل 1 نجد القافلة التالية:هي مسار يبدأ وينتهي بنفس العقدة.
في الشكل 1 نجد الحلقة التالية :
هو بيان من المرتبة formula_28 فيه كل عقدتين متمايزتين متصلتين ونرمز له بـ formula_29.
البيان التام من المرتبة formula_28 هو بيان منتظم من المرتبة formula_31 وحجمه يعطى بالعلاقة:
اذا كانت لدينا حلقة Cn. فالعجلة فيها رأس واحد يجاور جميع رؤوس البيان الاخرى ورمز العجلة Wn
هو بيان فيه 14 عقدة و21 ضلع.
إذا كانت قمتين من مخطط مرتبطتان بحرف, نقول أنهما متجاورتان أو مرتبطتان.
مربع مخطط هو مخطط له نفس قمم المخطط الأول وله نفس الحروف أو الأقواس بالإضافة إلى وجود حروف أو أقواس تربط بين القمم التي لها جوارات مشتركة.
السلسلة أو السبيل هو جزء من مخطط يربط بين قمتين بواسطة أزواج قمم مرتبط مثنى مثنى على التوالي.
البئر هو عقدة في بيان موجه درجة خروجه منعدمة.
أي : formula_33
المنبع هو عقدة في بيان موجه درجة دخوله منعدمة.
أي : formula_34
المخطط المكمل لمخطط هو مخطط له نفس القمم مرتبطة إذا لم تكن مرتبطة في المخطط الأصلي.
المسار هو سلسلة رؤوس مرتبطة, لها بداية ونهاية (نقطة انطلاق ونقطة وصول).
إذا كانت نقطتي الانطلاق والوصول منطبقتين, المسار يكون مغلقا.
مسار أولير لمخطط G غير موجه هو مسار يمر بكل الحروف مرة واحدة فقط.
نقول أن المخطط متصل إذا كان يحتوي على مسار أولير, وكل رؤوسه من درجة مزدوجة
مسار هاميلتون لمخطط G هو مسار يمر بكل القمم مرة واحدة فقط.
المخطط الكامل هو مخطط بسيط يكون كل زوج من رؤوسه متصلان بضلع. بحيث أن المخطط الكامل ذو n رأس يكون له n(n-1)/2 ضلع.
المخطط المستقر هو مخطط ليس له حروف.
المخطط المستوي هو مخطط يمكن تمثيله بكيفية لا تتقاطع الحروف فيه.
مخطط يمكن الوصول فيه من أي عقدة إلى أي عقدة أخرى.
كل مخطط يضم مجموعة قمم يمكن تمثيلها على شكل دوائر، إذا كان المخطط موجه يتم تمتيل كل قوس بسهم، وبخط في حالة مخطط عادي.