مخطط مستوي

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

معايير المخطط المستوي

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

• Graphe K32C3.png

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

• Graphe K5.png

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

وجوه مخطط مستوي

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

ليكن G مخطط مستوي، و a عدد حروف G. إذن : خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{F}^{} deg (F) = 2a }

صيغة أولير

تعاريف

• المسار ذو الطول r هو سلسلة خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle (S_0,...,S_r) } من القمم المرتبطة مع خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_0} أصل السبيل وخطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_r} طرفه.
• يكون المخطط متصلا إذا وُجد مسار بين كل قمتين من G.
• المسار المغلق هو حالة خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_0 = S_r} .
• الشجرة هي مخطط متصل بدون أي مسار مغلق.

تمهيدة

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

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

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

المعايير

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

1. خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \le {3n-6}} في حالة وجود مثلثات.
2. خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \le {2n-4}} في حالة عدم وجود مثلثات.

مميزة Kuratowski

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

يكون المخطط مستويا إذا وفقط إذا لم يتضمن مخططا جزئيا عبارة عن تمديد ل 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,000 puzzles