مخطط مستوي

من ويكيبيديا، الموسوعة الحرة

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

فهرست

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

حسب Kuratowski يكون المخطط مستويا إذا لم يتضمن زمرة من الرتبة 5، أو مخطط ثنائي كامل من الرتبة 3 (انظر الصور).

[تحرير] وجوه مخطط مستوي

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

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

[تحرير] صيغة أولير

[تحرير] تعاريف

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

[تحرير] تمهيدة

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

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

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

[تحرير] المعايير

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

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