مخطط مستوي

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

فهرس

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

مخطط ثنائي كامل من الرتبة 3

زمرة من الرتبة 5

ليكن 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 عدد حروفه:

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

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

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

Edge Addition Planarity Algorithm Source Code — Free C source code for reference implementation of Boyer-Myrvold planarity algorithm, which provides both a combinatorial planar embedder and Kuratowski subgraph isolator.
Public Implementation of a Graph Algorithm Library and Editor — GPL graph algorithm library including planarity testing, planarity embedder and Kuratowski subgraph exhibition in linear time.
3 Utilities Puzzle and Planar Graphs
Planarity — A puzzle game created by John Tantalo.
Mindgames nTangle Freeware nTangle puzzle program with 20,000puzzles