مخطط مستو

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

في المخططات، المخطّط المستوي هو المخطّط الذي يقبل تمثيلا في المستوى، بحيث لا يتقاطع أي حرفين من المخطّط.

معايير المخطّط المستوي[عدل]

حسب كوراتوفسكي, يكون المخطط مستويا إذا لم يتضمن زمرة من الرتبة الخامسة، أو مخططا ثنائيا كاملا من الرتبة الثالثة.


وجوه مخطط مستوي[عدل]

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

ليكن G مخطّطا مستويا، و a عدد حروف G. إذن : 
\sum_{F}^{} deg (F) = 2a

صيغة أويلر[عدل]

تعاريف[عدل]

  • المسار ذو الطول r هو سلسلة  (S_0,...,S_r)
من القمم المرتبطة مع S_0 أصل السبيل وS_r طرفه.
  • يكون المخطّط متّصلا إذا وُجد مسار بين كل قمتين من G.
  • المسار المغلق هو حالة S_0 = S_r.
  • الشجرة هي مخطط متّصل بدون أي مسار مغلق.

تمهيدة[عدل]

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

صيغة أويلر للمخطّطات المستوية المتّصلة[عدل]

ليكن G مخطّط مستوي متّصل. ليكن n عدد قمم a, G عدد حروفه و f عدد وجوهه. إذن: n − a + f = 2

المعايير[عدل]

تحديد المعايير التي تمكّن من معرفة ان كان مخطّط ما مستويا. ليكن G مخطّط مستوي متّصل. ليكن n عدد قمم a, G عدد حروفه:

  1. a \le {3n-6} في حالة وجود مثلّثات.
  2. a \le {2n-4} في حالة عدم وجود مثلّثات.

مميّزة كوراتوفسكي[عدل]

الرياضي البولوني كوراتوفسكي وضع الميّزة التالية للمخطّطات المستوية :

يكون المخطّط مستويا إذا وفقط إذا لم يتضمّن مخطّطا جزئيّا عبارة عن تمديد ل K5 (زمرة ب 5 قمم) أو K3,3 (المخطّط ثنائي كامل ب3+3 رؤوس).

'التمديد بالنّسبة لمخطّط هو نتيجة إضافة قـمّة أو أكثر لحرف أو عدّة حروف (مثلا, تحويل الحرف•——• إلى •—•—•).

وصلات خارجية[عدل]