الرسم البياني المستوي

قدم كازيميرز كوراتوفسكي توصيفًا للرسوم البيانية المستوية من حيث الرسوم البيانية المحظورة ، والمعروفة الآن باسم نظرية كوراتوفسكي :

يكون الرسم البياني المحدود مستوياً إذا وفقط إذا لم يحتوي على رسم بياني فرعي يمثل تقسيمًا للرسم البياني الكامل K ₅ أو الرسم البياني الثنائي الكامل K _3,3 ( رسم بياني للمنفعة ).

ينتج تقسيم الرسم البياني عن إدخال رؤوس في الحواف (على سبيل المثال، تغيير حافة • —— • إلى • — • — • ) صفر أو أكثر من المرات.

بدلاً من النظر في التقسيمات الفرعية، تتعامل نظرية فاغنر مع التقسيمات الصغرى :

يكون الرسم البياني المحدود مستوياً إذا وفقط إذا لم يكن لديه K ₅ أو K _3,3 كعنصر فرعي .

ينتج الرسم البياني الفرعي من أخذ رسم بياني فرعي وتقليص حافة بشكل متكرر إلى رأس، حيث يصبح كل جار للرؤوس النهائية الأصلية جارًا للرأس الجديد.

تساءل كلاوس فاغنر، بشكل أعم، عما إذا كانت أي فئة من الرسوم البيانية المغلقة جزئيًا تُحدد بمجموعة منتهية من " القواسم الجزئية المحظورة ". وهذا ما يُعرف الآن بنظرية روبرتسون-سيمور ، التي تم إثباتها في سلسلة طويلة من الأبحاث. وبعبارة أخرى، فإن K₅ _و K₃ , _₃ هما القواسم الجزئية المحظورة لفئة الرسوم البيانية المستوية المنتهية.

من الناحية العملية، يصعب استخدام معيار كوراتوفسكي لتحديد ما إذا كان الرسم البياني المعطى مستويًا بسرعة. ومع ذلك، توجد خوارزميات سريعة لهذه المشكلة: بالنسبة لرسم بياني يحتوي على n رأسًا، من الممكن تحديد ما إذا كان الرسم البياني مستويًا أم لا في زمن O ( n ) (زمن خطي) (انظر اختبار الاستواء ).

بالنسبة لرسم بياني بسيط ومتصل ومستوٍ يحتوي على v رأسًا و e حافة و f وجهًا، فإن الشروط البسيطة التالية تنطبق على v ≥ 3 :

• النظرية 1. e ≤ 3 v − 6 ؛
• النظرية 2. إذا لم تكن هناك دورات بطول 3، فإن e ≤ 2 v − 4 .
• النظرية 3. f ≤ 2 v − 4 .

بهذا المعنى، تُعتبر الرسوم البيانية المستوية رسومًا بيانية متفرقة ، إذ تحتوي على O ( v ) حافة فقط، ^وهو عدد أصغر تقاربًا من الحد الأقصى O ( v² ) . على سبيل المثال، يحتوي الرسم البياني K₃ , _₃ على 6 رؤوس و9 حواف، ولا يحتوي على دورات بطول 3. لذلك، وفقًا للنظرية 2، لا يمكن أن يكون مستويًا. تُقدّم هذه النظريات شروطًا ضرورية للاستواء، وهي ليست شروطًا كافية، وبالتالي لا يمكن استخدامها إلا لإثبات أن الرسم البياني ليس مستويًا، وليس لإثبات أنه مستوي. إذا لم تتحقق كلتا النظريتين 1 و2، فيمكن استخدام طرق أخرى.

• يقدم معيار ويتني للتسطيح توصيفًا قائمًا على وجود ثنائي جبري؛
• يقدم معيار ماك لين للتسطيح توصيفًا جبريًا للرسوم البيانية المستوية المحدودة، من خلال فضاءات دوراتها ؛
• يقدم معيار فرايسيكس-روزنستيل للتسطيح توصيفًا يعتمد على وجود تقسيم ثنائي لحواف الشجرة المشتركة لشجرة بحث ذات عمق أول . وهو عنصر أساسي في خوارزمية اختبار التسطيح من اليسار إلى اليمين ؛
• تُعطي نظرية شنايدر توصيفًا للتسطيح من حيث بُعد الترتيب الجزئي ؛
• يقدم معيار كولين دي فيرديير للتسطيح توصيفًا يعتمد على الحد الأقصى لتعدد القيمة الذاتية الثانية لبعض عوامل شرودنغر المحددة بواسطة الرسم البياني.
• تنص نظرية هاناني -توت على أن الرسم البياني يكون مستوياً إذا وفقط إذا كان له رسم يتقاطع فيه كل زوج مستقل من الحواف عددًا زوجيًا من المرات؛ ويمكن استخدامها لتوصيف الرسوم البيانية المستوية من خلال نظام من المعادلات modulo  2.

تنص صيغة أويلر على أنه إذا تم رسم مخطط مستوٍ متصل ومحدود في المستوى دون أي تقاطعات بين الحواف، وكان v هو عدد الرؤوس، وe هو عدد الحواف، و f هو عدد الأوجه (المناطق المحصورة بالحواف، بما في ذلك المنطقة الخارجية اللانهائية)، فإن

${\displaystyle v-e+f=2.}$

كمثال توضيحي، في الرسم البياني للفراشة المذكور أعلاه، v = 5 و e = 6 و f = 3. بشكل عام، إذا تحققت هذه الخاصية لجميع الرسوم البيانية المستوية ذات f وجهًا، فإن أي تغيير في الرسم البياني يُنشئ وجهًا إضافيًا مع الحفاظ على استواء الرسم البياني سيُبقي v − e + f ثابتًا. بما أن هذه الخاصية تتحقق لجميع الرسوم البيانية التي يكون فيها f = 2 ، فإنها تتحقق بالاستقراء الرياضي في جميع الحالات. يمكن أيضًا إثبات صيغة أويلر كما يلي: إذا لم يكن الرسم البياني شجرة ، فقم بإزالة حافة تُكمل دورة . هذا يُقلل كلاً من e و f بمقدار واحد، مما يجعل v − e + f ثابتًا. كرر ذلك حتى يصبح الرسم البياني المتبقي شجرة؛ الأشجار لها v = e + 1 و f = 1 ، مما ينتج عنه v − e + f = 2 ، أي أن خاصية أويلر هي 2.

في الرسم البياني المحدود والمتصل والبسيط والمستوي ، يكون أي وجه (باستثناء الوجه الخارجي ربما) محاطًا بثلاثة حواف على الأقل، وتلامس كل حافة وجهين على الأكثر، لذا فإن 3f ≤ 2e ؛ باستخدام صيغة أويلر، يمكن للمرء أن يثبت أن هذه الرسوم البيانية متفرقة بمعنى أنه إذا كان v ≥ 3 :

${\displaystyle e\leq 3v-6.}$

تُعدّ صيغة أويلر صالحةً أيضًا للمجسمات المحدبة . ليس هذا من قبيل المصادفة، إذ يُمكن تحويل أي مجسم محدب إلى رسم بياني مستوٍ بسيط ومتصل باستخدام مخطط شليغل للمجسم، وهو إسقاط منظوري للمجسم على مستوى، حيث يُختار مركز المنظور بالقرب من مركز أحد أوجه المجسم. لا يتوافق كل رسم بياني مستوٍ مع مجسم محدب بهذه الطريقة، فالأشجار، على سبيل المثال، لا تُطابقه. تنصّ نظرية شتاينيتز على أن الرسوم البيانية للمجسمات المُشكّلة من المجسمات المحدبة هي تحديدًا الرسوم البيانية المستوية البسيطة المتصلة ثلاثيًا . وبشكلٍ أعم، تنطبق صيغة أويلر على أي مجسم تكون أوجهه مضلعات بسيطة تُشكّل سطحًا مكافئًا طوبولوجيًا للكرة، بغض النظر عن تحدبه.

تخضع الرسوم البيانية المستوية المتصلة التي تحتوي على أكثر من حافة واحدة للمتباينة 2e ≥ 3f ، لأن لكل وجه ثلاث نقاط اتصال على الأقل مع حواف الوجه ، وتساهم كل حافة بنقطتي اتصال بالضبط. وبإجراء تحويلات جبرية لهذه المتباينة باستخدام صيغة أويلر v − e + f = 2، يتضح أن متوسط ​​درجة الرسوم البيانية المستوية المحدودة أقل من 6. ولا يمكن أن تكون الرسوم البيانية ذات متوسط ​​درجة أعلى مستوية.

نقول إن دائرتين مرسومتين في مستوى واحد تلامسان (أو تتقاطعان ) عندما تتقاطعان في نقطة واحدة فقط. يُعرف "مخطط العملة" بأنه مخطط يتكون من مجموعة من الدوائر، لا تتداخل أي دائرتين منها من الداخل، وذلك برسم رأس لكل دائرة وحافة لكل زوج من الدوائر المتلامسة. تنص نظرية تعبئة الدوائر ، التي أثبتها بول كوبي لأول مرة عام 1936، على أن المخطط يكون مستويًا إذا وفقط إذا كان مخطط عملة.

تُقدّم هذه النتيجة برهانًا بسيطًا لنظرية فاري ، التي تنص على أنه يُمكن تضمين أي رسم بياني مستوٍ بسيط في المستوى بحيث تكون حوافه عبارة عن قطع مستقيمة لا تتقاطع. إذا وُضع كل رأس من رؤوس الرسم البياني في مركز الدائرة المقابلة له في تمثيل الرسم البياني للعملة، فإن القطع المستقيمة بين مراكز الدوائر المتلامسة لا تتقاطع مع أي من الحواف الأخرى.

معامل التشابك أو الكثافة D للرسم البياني المستوي، أو الشبكة، هو نسبة عدد الوجوه المحدودة f − 1 (وهو نفس رتبة الدائرة للرسم البياني، وفقًا لمعيار ماك لين للتسطيح ) إلى أقصى قيمها الممكنة 2 v − 5 للرسم البياني الذي يحتوي على v رأسًا:

${\displaystyle D={\frac {f-1}{2v-5}}}$

تخضع الكثافة للعلاقة 0 ≤ D ≤ 1 ، حيث D = 0 للرسم البياني المستوي المتفرق تمامًا (الشجرة)، و D = 1 للرسم البياني المستوي الكثيف تمامًا (الأقصى). ^{[ 3 ]}

بفرض وجود تمثيل G لبيان متصل (ليس بالضرورة بسيطًا) في المستوى دون تقاطعات بين الحواف، نقوم بإنشاء الرسم البياني الثنائي G* كما يلي: نختار رأسًا واحدًا في كل وجه من أوجه G (بما في ذلك الوجه الخارجي)، ولكل حافة e في G، نُدخل حافة جديدة في G* تربط بين الرأسين في G* اللذين يقابلان الوجهين في G اللذين يلتقيان عند e . علاوة على ذلك، تُرسَم هذه الحافة بحيث تتقاطع مع e مرة واحدة فقط، ودون أن تتقاطع مع أي حافة أخرى من G أو G* . عندئذٍ، يكون G* تمثيلًا لبيان مستوٍ (ليس بالضرورة بسيطًا)؛ إذ يحتوي على نفس عدد حواف G ، ونفس عدد رؤوس G ، ونفس عدد وجوه G. يُبرر مصطلح "ثنائي" بحقيقة أن G ** = G ؛ حيث تُمثل المساواة هنا تكافؤ التمثيلات على الكرة . إذا كان G هو الرسم البياني المستوي المقابل لمتعدد السطوح المحدب، فإن G* هو الرسم البياني المستوي المقابل لمتعدد السطوح المزدوج.

تعتبر الرسوم البيانية الثنائية مفيدة لأن العديد من خصائص الرسم البياني الثنائي ترتبط بطرق بسيطة بخصائص الرسم البياني الأصلي، مما يتيح إثبات النتائج المتعلقة بالرسوم البيانية من خلال فحص الرسوم البيانية الثنائية الخاصة بها.

في حين أن الثنائي الذي تم إنشاؤه لتضمين معين فريد (حتى التماثل )، قد يكون للرسوم البيانية ثنائيات مختلفة (أي غير متماثلة)، تم الحصول عليها من تضمينات مختلفة (أي غير متماثلة ).

يُطلق على الرسم البياني البسيط اسم " رسم بياني مستوٍ أقصى" إذا كان مستويًا، ولكن إضافة أي حافة (على مجموعة الرؤوس المعطاة) تُفقده هذه الخاصية. جميع الأوجه (بما في ذلك الوجه الخارجي) تكون محاطة بثلاث حواف، مما يُفسر المصطلح البديل " التثليث المستوي " (والذي يعني تقنيًا رسمًا مستويًا للرسم البياني). كما استُخدمت التسميات البديلة "الرسم البياني المثلثي" ^{[ 4 ]} أو "الرسم البياني المُثلث" ^{[ 5 ]} ، لكنها غامضة، حيث تشير عادةً إلى الرسم البياني الخطي للرسم البياني الكامل وإلى الرسوم البيانية الوترية على التوالي. كل رسم بياني مستوٍ أقصى يحتوي على أكثر من 3 رؤوس يكون على الأقل ثلاثي الاتصال. ^{[ 6 ]}

إذا كان الرسم البياني المستوي الأقصى يحتوي على v رأسًا حيث v > 2 ، فإنه يحتوي بالضبط على 3 v − 6 حواف و 2 v − 4 وجوه.

الشبكات الأبولونية هي الرسوم البيانية المستوية القصوى التي تتشكل من خلال تقسيم الوجوه المثلثية بشكل متكرر إلى ثلاثيات من المثلثات الأصغر. وبصورة مكافئة، هي الأشجار المستوية الثلاثية .

الرسوم البيانية المختنقة هي تلك التي تكون فيها كل دورة محيطية مثلثًا. في الرسم البياني المستوي الأقصى (أو بشكل أعم، الرسم البياني متعدد السطوح)، تمثل الدورات المحيطية الأوجه، لذا فإن الرسوم البيانية المستوية القصوى مختنقة. تشمل الرسوم البيانية المختنقة أيضًا الرسوم البيانية الوترية ، وهي تحديدًا الرسوم البيانية التي يمكن تكوينها من خلال مجاميع الزمر (دون حذف الحواف) للرسوم البيانية الكاملة والرسوم البيانية المستوية القصوى. ^{[ 7 ]}

الرسوم البيانية الخارجية المستوية هي رسوم بيانية ذات تمثيل في المستوى بحيث تنتمي جميع رؤوسها إلى الوجه غير المحدود لهذا التمثيل. كل رسم بياني خارجي مستوي هو رسم بياني مستوٍ، ولكن العكس غير صحيح: الرسم _{البياني} K⁴ مستوٍ ولكنه ليس خارجيًا مستويًا. تنص نظرية مشابهة لنظرية كوراتوفسكي على أن الرسم البياني المحدود يكون خارجيًا مستويًا إذا وفقط إذا لم يحتوِ على تقسيم فرعي من K⁴ أو K² _{, ³} . ما سبق هو نتيجة مباشرة لحقيقة أن الرسم البياني G يكون خارجيًا مستويًا إذا كان الرسم البياني المُشكَّل من G بإضافة رأس جديد، مع حواف تربطه بجميع الرؤوس الأخرى، رسمًا بيانيًا مستويًا. ^{[ 8 ]}

التمثيل الخارجي المستوي من الرتبة 1 للرسم البياني هو نفسه التمثيل الخارجي المستوي. بالنسبة لـ k > 1، يكون التمثيل المستوي k- خارجي مستوي إذا أدى حذف الرؤوس على الوجه الخارجي إلى تمثيل خارجي مستوي من الرتبة ( k - 1) . يكون الرسم البياني k- خارجي مستوي إذا كان له تمثيل خارجي مستوي من الرتبة k .

مخطط هالين هو مخطط يتكون من شجرة مستوية غير موجهة (بدون عقد من الدرجة الثانية) عن طريق ربط أوراقها في دورة، بالترتيب الذي يحدده التضمين المستوي للشجرة. وبصورة مكافئة، هو مخطط متعدد الأوجه يكون فيه وجه واحد مجاورًا لجميع الأوجه الأخرى. كل مخطط هالين هو مخطط مستوٍ. ومثل المخططات المستوية الخارجية، تتميز مخططات هالين بعرض شجري منخفض ، مما يجعل حل العديد من المسائل الخوارزمية عليها أسهل من حلها في المخططات المستوية غير المقيدة. ^{[ 9 ]}

الرسم البياني المستوي الصاعد هو رسم بياني موجه غير دوري يمكن رسمه في المستوى بحيث تكون حوافه منحنيات غير متقاطعة وموجهة باستمرار نحو الأعلى. ليس كل رسم بياني موجه غير دوري مستوي هو رسم بياني صاعد، وتُعدّ مسألة اختبار ما إذا كان رسم بياني معين مستويًا صاعدًا مسألةً كاملةً من نوع NP .

يُقال إن الرسم البياني المستوي محدب إذا كانت جميع أوجهه (بما في ذلك الوجه الخارجي) مضلعات محدبة . لا تمتلك جميع الرسوم البيانية المستوية تمثيلاً محدباً (مثل الرسم البياني الثنائي الكامل K _2,4 ). الشرط الكافي لرسم رسم بياني محدب هو أن يكون تقسيمًا لرسم بياني مستوي متصل بثلاثة رؤوس . تنص نظرية توت الربيعية على أنه بالنسبة للرسوم البيانية المستوية البسيطة المتصلة بثلاثة رؤوس، يمكن اختيار موضع الرؤوس الداخلية ليكون متوسط ​​موضع جيرانها.

تشمل الرسوم البيانية المستوية القابلة للتمثيل بالكلمات الرسوم البيانية المستوية الخالية من المثلثات، وبشكل أعم، الرسوم البيانية المستوية القابلة للتلوين بثلاثة ألوان، ^{[ 10 ]} بالإضافة إلى بعض التقسيمات الفرعية للوجوه في الرسوم البيانية الشبكية المثلثية، ^{[ 11 ]} وبعض التثليثات في الرسوم البيانية الأسطوانية المغطاة بالشبكة. ^{[ 12 ]}

السلوك التقاربي لعدد الرسوم البيانية المستوية (المصنفة) على${\displaystyle n}$الرؤوس هي${\displaystyle g\cdot n^{-7/2}\cdot \gamma ^{n}\cdot n!}$، أين${\displaystyle \gamma \approx 27.22687}$و${\displaystyle g\approx 0.43\times 10^{-5}}$[ ^{13 ]​}

تحتوي جميع الرسوم البيانية المستوية تقريبًا على عدد أسي من التشاكلات الذاتية. ^{[ 14 ]}

عدد الرسوم البيانية المستوية غير المصنفة (غير المتماثلة) على${\displaystyle n}$الرؤوس تقع بين${\displaystyle 27.2^{n}}$و${\displaystyle 30.06^{n}}$[ ^{15 ]​}

تنص نظرية الألوان الأربعة على أن كل رسم بياني مستوٍ قابل للتلوين بأربعة ألوان (أي، رباعي الأجزاء).

تنص نظرية فاري على أن كل رسم بياني مستوٍ بسيط يمكن تمثيله كرسم بياني مستوٍ بخطوط مستقيمة . مجموعة النقاط الشاملة هي مجموعة من النقاط بحيث يكون لكل رسم بياني مستوٍ ذي n رأس تمثيلٌ شاملٌ مع جميع الرؤوس في مجموعة النقاط هذه؛ وتوجد مجموعات نقاط شاملة ذات حجم تربيعي، تتكون من أخذ مجموعة جزئية مستطيلة من الشبكة الصحيحة . كل رسم بياني خارجي مستوٍ بسيط يمكن تمثيله في المستوى بحيث تقع جميع الرؤوس على دائرة ثابتة وجميع الحواف عبارة عن قطع مستقيمة تقع داخل القرص ولا تتقاطع، لذا فإن المضلعات المنتظمة ذات n رأس هي شاملة للرسوم البيانية الخارجية المستوية.

تنص فرضية شاينرمان (التي أصبحت الآن نظرية) على أنه يمكن تمثيل كل رسم بياني مستوٍ على أنه رسم بياني لتقاطع القطع المستقيمة في المستوى.

تنص نظرية الفاصل المستوي على أنه يمكن تقسيم أي رسم بياني مستوي ذي n رأس إلى رسمين بيانيين فرعيين بحجم لا يتجاوز 2n / 3 عن طريق إزالة${\displaystyle O({\sqrt {n}})}$الرؤوس. ونتيجة لذلك، فإن الرسوم البيانية المستوية لها أيضًا عرض الشجرة وعرض الفرع.${\displaystyle O({\sqrt {n}})}$.

تنص نظرية بنية الضرب المستوي على أن كل رسم بياني مستوي هو رسم بياني جزئي من حاصل الضرب القوي لرسم بياني بعرض شجري لا يتجاوز 8 ومسار. ^{[ 16 ]} وقد استُخدمت هذه النتيجة لإثبات أن الرسوم البيانية المستوية لها عدد طوابير محدود ، وعدد ألوان غير متكرر محدود ، ورسوم بيانية شاملة ذات حجم شبه خطي. كما أن لها تطبيقات في ترتيب الرؤوس ^{[ 17 ]} وتلوين الرسوم البيانية المستوية بمركز p ^{[ 18 ] .}

بالنسبة لرسمين بيانيين مستويين لهما v رأس، من الممكن تحديد ما إذا كانا متماثلين أم لا في وقت O( v ) (انظر أيضًا مشكلة تماثل الرسوم البيانية ). ^{[ 19 ]}

أي رسم بياني مستوي على n عقدة يحتوي على 8(n-2) زمر قصوى على الأكثر، ^{[ 20 ]} مما يعني أن فئة الرسوم البيانية المستوية هي فئة بها عدد قليل من الزمر.

وفقًا لنظرية توت حول الدورات الهاميلتونية ، فإن كل رسم بياني مستوٍ متصل بأربعة رؤوس يحتوي على دورة هاميلتونية . ^{[ 21 ]}