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

الرسم البياني المستوي هو الذي يمكن رسمه على مستوٍ مسطح بحيث لا تتقاطع أي حافتين في أي مكان إلا عند نقاط النهاية المشتركة.

ما هي نظرية Kuratowski؟

تنص على أن الرسم البياني غير مستوٍ إذا وفقط إذا احتوى على تقسيم فرعي لـ K₅ أو K₃,₃ — مما يعني أن أحد هذين الرسمين البيانيين، أو نسخة منه بها رؤوس إضافية مُدرجة على طول حوافه، يظهر كرسم بياني فرعي.

ما هما K₅ و K₃,₃؟

K₅ هو الرسم البياني الكامل على 5 رؤوس (كل زوج متصل). K₃,₃ هو الرسم البياني الثنائي التقسيم الكامل على مجموعتين من 3 رؤوس لكل منهما، مع اتصال كل رأس في مجموعة بكل رأس في الأخرى — كلاهما أصغر الرسوم البيانية غير المستوية.

ماذا يعني شرط E ≤ 3V − 6؟

لأي رسم بياني مستوٍ بـ 3 رؤوس على الأقل، لا يمكن أبدًا أن يتجاوز عدد الحواف القيمة 3V − 6 — نتيجة مباشرة لصيغة أويلر للرسوم البيانية المستوية (V − E + F = 2). تجاوز هذا الحد يُثبت عدم الاستواء فورًا.

لماذا الحد أضيق للرسوم البيانية ثنائية التقسيم؟

لا يمكن أن يكون للرسوم البيانية المستوية ثنائية التقسيم أي وجوه مثلثية (تتطلب الدورات الثلاثية دورة فردية، مستحيلة في رسم بياني ثنائي التقسيم)، مما يفرض حد حواف أكثر صرامة يبلغ E ≤ 2V − 4.

لماذا يبحث هذا المدقق عن K₅/K₃,₃ حتى 8 رؤوس فقط؟

يتطلب البحث عن رسم بياني فرعي K₅ أو K₃,₃ حرفي التحقق من تركيبات 5 أو 6 رؤوس من الرسم البياني، والذي ينمو بسرعة — تُبقي 8 رؤوس ذلك البحث سريعًا بشكل مريح مع التقاط الأمثلة الكلاسيكية الصغيرة غير المستوية.

لماذا 'غير حاسم' ليس نفسه 'مستوٍ'؟

يبحث هذا المدقق فقط عن K₅/K₃,₃ كرسوم بيانية فرعية حرفية، وليس تقسيمات فرعية (حيث تُدرج رؤوس إضافية على طول حواف الرسم البياني المحظور) أو قاصرات — يمكن أن يكون الرسم البياني لا يزال غير مستوٍ بطريقة لا يلتقطها هذا البحث المُبسّط، لذا فإن 'غير حاسم' يعني 'لم يُعثر على انتهاك،' وليس 'مُثبت أنه مستوٍ.'

أين تُستخدم استوائية الرسم البياني في الحياة الواقعية؟

هي أساسية لتصميم لوحات الدوائر (تجنب تقاطع المسارات على طبقة واحدة)، وتخطيط الخرائط ومخططات الشبكات، وخوارزميات رسم الرسوم البيانية التي تهدف إلى تصورات مقروءة وخالية من التقاطعات.

مدقق الرسم البياني المستوي — اختبر ما إذا كان يمكن رسم رسم بياني بدون تقاطعات

يختبر مدقق الرسم البياني المستوي الخاص بنا ما إذا كان يمكن رسم رسم بياني على مستوٍ دون تقاطع أي حواف، بتطبيق شرط عدد الحواف الضروري (E ≤ 3V − 6، يُشدد إلى E ≤ 2V − 4 للرسوم البيانية ثنائية التقسيم) و، للرسوم البيانية ذات 8 رؤوس أو أقل، بحث صريح عن رسم بياني فرعي K₅ أو K₃,₃ — أي منهما يُثبت بشكل قاطع عدم الاستواء وفقًا لنظرية Kuratowski.

إجابة سريعة

أدخل رسمك البياني كقائمة حواف للتحقق من شرط عدد الحواف الضروري والبحث عن رسوم بيانية فرعية محظورة K₅/K₃,₃ — فحص استواء قوي لكن غير شامل بالكامل.

الحواف (مفصولة بفواصل)

أدخل حوافًا بصيغة عقدةA-عقدةB، مثل A-B, A-C, A-D, B-C, B-D, C-D.

كيفية استخدام مدقق الرسم البياني المستوي — اختبار بأسلوب Kuratowski عبر الإنترنت

1
أدخل رسمك البياني كقائمة حواف مفصولة بفواصل، مثل A-B, A-C, A-D, B-C, B-D, C-D.
2
انقر على 'احسب' للتحقق من الشروط الضرورية والبحث عن رسوم بيانية فرعية محظورة.
3
راجع الحكم — 'غير مستوٍ بالتأكيد' أو 'مستوٍ على الأرجح (غير حاسم)' — وخطوات التفكير.

لماذا تستخدم مدقق الرسم البياني المستوي — اختبار بأسلوب Kuratowski عبر الإنترنت؟

الرسم البياني مستوٍ إذا كان يمكن رسمه على مستوٍ مسطح دون تقاطع أي حافتين. تعطي نظرية Kuratowski وصفًا دقيقًا: الرسم البياني غير مستوٍ إذا وفقط إذا احتوى على تقسيم فرعي لـ K₅ (الرسم البياني الكامل على 5 رؤوس) أو K₃,₃ (الرسم البياني الثنائي التقسيم الكامل على مجموعتين من 3). يتطلب الاكتشاف الكامل للتقسيمات الفرعية أو القاصرات لهذه الرسوم البيانية خوارزميات معقدة (مثل Boyer-Myrvold) تتجاوز بكثير ما يمكن لآلة حاسبة من جانب العميل تشغيله فورًا — لذا تتبع هذه الأداة نهجًا محددًا النطاق بشفافية بدلاً من ذلك: تتحقق دائمًا من حد عدد الحواف الضروري (طريقة سريعة ودقيقة لاستبعاد العديد من الرسوم البيانية غير المستوية)، وللرسوم البيانية الصغيرة (8 رؤوس أو أقل) تبحث بالإضافة إلى ذلك مباشرة عن K₅ أو K₃,₃ يظهران كرسوم بيانية فرعية حرفية. إيجاد أي منهما يُثبت عدم الاستواء بشكل قاطع؛ عدم إيجاد أحدهما تلميح قوي على الاستواء لكن ليس إثباتًا كاملًا، لأنه لن يلتقط نسخًا مُقسّمة فرعيًا (موسعة الحواف) من هذه الرسوم البيانية المحظورة.

الأسئلة الشائعة

أدوات ذات صلة

مدقق تسلسل درجات الرسم البياني — نظرية Erdős–Gallai عبر الإنترنت

تحقق مما إذا كان تسلسل من الأرقام تسلسل درجات صالحًا (قابلًا للتحقيق كرسم بياني) باستخدام نظرية Erdős–Gallai. آلة حاسبة مجانية بتحقق خطوة بخطوة.

آلة حاسبة تلوين الرسم البياني — خوارزمية Welsh-Powell عبر الإنترنت

لوّن رؤوس رسم بياني بحيث لا تشترك عقدتان متصلتان في نفس اللون، باستخدام خوارزمية Welsh-Powell الجشعة. آلة حاسبة مجانية بإدخال قائمة حواف بسيط.

آلة حاسبة مصفوفة التجاور — ابنِ مصفوفة رسم بياني عبر الإنترنت

ابنِ واعرض مصفوفة تجاور رسم بياني من إدخال بسيط لقائمة الحواف، مع تسلسل الدرجات. آلة حاسبة مجانية، موزونة أو غير موزونة.