الرسم المستوي: ستة رؤوس وتسع حواف لا تحسم إمكان الرسم بلا تقاطع

الخلاصة السريعة

لأن العدد والدرجة لا يحددان مَن يتصل بمَن. المنشور الثلاثي في مثالنا يُرسم بلا تقاطع وله خمسة وجوه، بينما افتراض تمثيل مستو للرسم الثنائي الكامل ثلاثة وثلاثة يفرض خمسة وجوه تحتاج إلى 20 جانبًا على الأقل، مع أن الحواف التسع لا توفر إلا 18 جانبًا.

• المستوية تعني وجود تمثيل بلا تقاطع؛ قد يكون للرسم نفسه تمثيل آخر متقاطع. [1] لا تضف رأسًا عند تقاطع خطين ما لم يكن جزءًا من تعريف الرسم.
• المنشور عندنا حوافه AB وAC وBC وDE وDF وEF وAD وBE وCF. رسم المثلثين المتداخلين ووصل الرؤوس المتناظرة يعطي تمثيلًا بلا تقاطع، مع ثلاث وصلات لكل رأس.
• الوجه الخارجي يدخل في العد. للمنشور وجهان ثلاثيان وثلاثة رباعية: أطوال الحدود (3,3,4,4,4) مجموعها 18، وعدد الوجوه 5؛ لذلك 6−9+5=2.
• في K3,3، كل رأس من A B C يتصل بكل رأس من D E F. لا مثلث ولا جسر فيه؛ لو كان مستويًا لفرضت صيغة أويلر 5 وجوه، لكل منها 4 جوانب على الأقل: 20≤18 تناقض.
• الحد العام 3V−6 لا يحسم مثالنا: عند V=6 يسمح حتى 12 حافة، فيمر الرسمان ذوا الحواف التسع. الشرط الأقوى 2V−4 يرفض K3,3 ذي التقسيم الثنائي؛ لا نطبقه على المنشور ذي المثلثات.
• K4 مثال آخر: الحواف الست نفسها تظهر متقاطعة في ترتيب مربع، وبلا تقاطع في ترتيب مثلث ورأس داخلي. وجود الرسم الثاني يثبت المستوية؛ فشل محاولة واحدة لا يثبت استحالة جميع المحاولات.

ثبّت الاتصال قبل مقارنة الصور

نستعمل رسومًا بسيطة متصلة غير موجهة: لا حلقات من رأس إلى نفسه، ولا حافتان مختلفتان بين الزوج نفسه، ولا اتجاه سير مفروض. A وB اسمان لرأسين، وAB هي الحافة نفسها التي يمكن كتابتها BA؛ لا نعدها مرتين.

وجود تقاطع في صورة لا يمنع المستوية إذا أمكن رسم الاتصال نفسه بصورة أخرى بلا تقاطع. [1] نحافظ أثناء تغيير المواضع على أسماء الرؤوس وأزواجها المتصلة؛ تغيير الحواف يغير الرسم الذي نختبره.

الرسمان الرئيسيان لهما الرؤوس A B C D E F، والحواف تسع في كل واحد، ودرجات الرؤوس (3,3,3,3,3,3). هذه قائمة بعدد الوصلات عند كل اسم، لكنها لا تسرد أسماء جيرانه؛ لهذا يمكن أن تتساوى القائمتان مع اختلاف البنية.

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

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

المثلثان المتداخلان يقدمان شاهدًا ناجحًا

حواف المنشور الثلاثي هي AB وAC وBC للمثلث الخارجي، وDE وDF وEF للمثلث الداخلي، ثم AD وBE وCF لربط الرؤوس المتناظرة. هذه التسع هي القائمة النهائية؛ لا توجد AE أو BD أو CE في هذا الرسم.

ضع A أعلى المثلث الكبير وB عند أسفل يمينه وC عند أسفل يساره. ضع D أعلى المثلث الصغير وE عند أسفل يمينه وF عند أسفل يساره. تصل AD القمتين، وتصل BE وCF الزوجين الآخرين دون أن تمر الوصلات داخل المثلث الصغير.

درجة A ثلاثة لأن جيرانه B وC وD؛ ودرجة D ثلاثة لأن جيرانه E وF وA. بالطريقة نفسها جيران B هم A وC وE، وجيران C هم A وB وF. إذن اختلاف الترتيب بين المثلثين لا يغير عدد الوصلات عند الرأس.

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

وجود مثلث ABC وآخر DEF يجعل هذا المثال مختلفًا عن الرسم الثنائي الكامل الذي يأتي لاحقًا. لا نحتاج إحصاء كل ترتيبات المواضع لكي نثبت مستوية المنشور: نحتاج تمثيلًا واحدًا صحيحًا يحفظ قائمة الحواف كلها.

عدّ الوجه الخارجي وراجِع جانبي كل حافة

في تمثيل مستو متصل، تربط صيغة أويلر عدد الرؤوس V والحواف E والوجوه F بالعلاقة V−E+F=2. الوجوه مناطق المستوى التي تفصلها الحواف والرؤوس. [2] نستعمل العلاقة بعد تثبيت تمثيل بلا تقاطع، أو تحت افتراض وجوده.

في لوحة المنشور، هناك وجه داخل المثلث الصغير DEF، وثلاث مناطق بين المثلثين، ومنطقة خارج المثلث الكبير ABC. الأخيرة غير محدودة في المستوى، لكنها وجه واحد وتدخل في العدد؛ يصبح F=5، لا أربعة.

حدود المناطق الوسطى هي ABED وACFD وBCFE. عند قراءة ABED نمر من A إلى B، ثم E، ثم D، ثم نعود إلى A. كل خطوة حافة موجودة في القائمة. لا نستبدل BCFE بـBCEF: الانتقال من C إلى E ليس حافة عندنا.

في هذا التمثيل، لكل حافة جانبان في حدود الوجوه؛ لذلك مجموع أطوال الحدود يساوي 2E. [2] الطول هنا عدد مرات المرور على الحواف في الحد، لا طول الخط بالسنتيمتر. جدول مثالنا يسمح بمراجعة كل حد بالاسم.

الأطوال 3 و3 و4 و4 و4 تجمع إلى 18، وهو ضعف الحواف التسع. وتظهر AD في الحدين ABED وACFD، وتظهر EF في DEF وBCFE. راجعنا بقية الحواف أيضًا: لكل واحدة ظهوران بالضبط في قوائم الحدود الخمس.

بالتعويض نحصل على 6−9+5=2، كما تتطلب العلاقة. لو نسينا الوجه الخارجي لحصلنا على 6−9+4=1؛ هذا خطأ في العد، لا نفي لمستوية الرسم. تطابق الأعداد يراجع التمثيل الذي عرضناه، ولا يعوض غياب تمثيل صحيح لرسم آخر.

الرسم الثنائي الكامل يفرض أكثر مما توفره الحواف

في K3,3 نقسم الأسماء إلى A B C وD E F، ونصل كل اسم في المجموعة الأولى بكل اسم في الثانية. الحواف AD وAE وAF وBD وBE وBF وCD وCE وCF. عند كل اسم ثلاث حواف، فيتطابق العدد والدرجات مع المنشور.

لا توجد وصلة بين اسمين من المجموعة نفسها. عند اتباع دورة ينتقل السير بين المجموعتين في كل خطوة؛ العودة إلى المجموعة التي بدأنا منها تحتاج عددًا زوجيًا من الخطوات. لذلك لا مثلث في هذا الرسم؛ حواف المنشور مثل AB غير موجودة هنا.

ولا توجد حافة جسر: بعد حذف AD مثلًا يبقى طريق من A إلى D عبر A E B D. وبإبدال الأسماء نجد طريقًا بديلًا للحافة التي نحذفها. راجعنا أيضًا اتصال الرسم بعد حذف كل واحدة من حوافه التسع منفردة.

افترض الآن وجود تمثيل بلا تقاطع لهذا الاتصال. لأنه متصل، تعطينا العلاقة 6−9+F=2، ومن ثم F=5. هذا عدد مفروض بالافتراض؛ لا نستخرج خمسة وجوه صالحة من الصورة المتقاطعة اليمنى، ولا نحسب التقاطعات رؤوسًا.

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

إذن كل حد يحتاج أربعة جوانب على الأقل. خمسة وجوه تحتاج إلى 4×5=20 جانبًا أو أكثر، بينما الحواف التسع توفر 2×9=18 فقط. يلزم 20≤18، وهو مستحيل. يسقط افتراض التمثيل المستوي؛ التقاطع الظاهر في الصورة ليس وحده سبب الحكم.

الحواف الست نفسها في رسمين لـ K4

خذ أربعة رؤوس A وB وC وD، ووصل كل زوج: AB وAC وAD وBC وBD وCD. هذه حواف K4 الست. في الصورة الداخلية اليسرى وضعت الأسماء عند زوايا مربع، فتتقاطع القطعتان AC وBD داخل المربع دون رأس عند التقاطع.

الآن حافظ على الحواف الست وأعد ترتيب المواضع: اجعل A وB وC زوايا مثلث، وضع D داخله. AB وAC وBC حدود المثلث، وAD وBD وCD تصل الرأس الداخلي بكل زاوية. الحواف لا تتقاطع خارج الرأس المشترك في اللوحة اليمنى.

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

في اللوحة اليمنى، الوجوه ABC الخارجي وABD وACD وBCD الداخلية. الأربعة ثلاثية الحدود، ومجموع أطوالها 12 يساوي ضعف ست حواف. والتعويض 4−6+4=2 يراجع عد الوجوه في هذا التمثيل الناجح.

محاولة المربع المتقاطعة لا تصلح برهانًا على أن K4 غير مستو، لأن التمثيل الثاني أمامنا يدحض ذلك الحكم. بالمقابل، تناقض K3,3 لم يعتمد على تحريك خطوط لوحة واحدة؛ استبعد كل تمثيل مفترض يحفظ الاتصال المحدد.

افصل شرط الاستبعاد عن الشاهد الذي يثبت الإمكان

للرسم البسيط المستوي ذي ثلاثة رؤوس على الأقل، حد عام للحواف هو E≤3V−6. [2] تجاوز الحد يستبعد المستوية؛ اجتيازه وحده لا يثبتها. لا نعطي هذه الصيغة لرسم ذي رأس واحد أو رأسين.

عند V=6 يصبح الحد 12، والحواف التسع أقل منه. يمر المنشور وK3,3 بهذا الفحص معًا، رغم اختلاف الحكم النهائي. لهذا لا نضع علامة «مستو» لمجرد أن 9≤12؛ ما زلنا نحتاج الشاهد أو الفحص الأقوى المناسب للبنية.

في حالة K3,3 السابقة، اشتراط أربعة جوانب للوجه أعطى 4F≤2E. ومع F=2−V+E نحصل على 4(2−V+E)≤2E، ومنه E≤2V−4. عند ستة رؤوس هذا يسمح بثماني حواف فقط؛ الحافة التاسعة تخالف الشرط.

هذا الاستنتاج استعمل بنية خالية من المثلثات كما تحققنا منها في K3,3، مع شروط البساطة والتمثيل المفترض. لا نطبقه على المنشور ذي الوجهين الثلاثيين؛ تطبيقه هناك سيستبعد خطأً التمثيل الذي عرضناه فعلًا. الجدول يلخص الفرق بين الفحصين.

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

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