الرسم المنتظم: هل تستطيع تماثلاته ربط أي رأسين؟

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

لا؛ انتظام الرسم لا يكفي لإثبات انتقالية الرؤوس. في مثالنا الأول، يمر بـA مثلث واحد وبـC مثلثان، مع أن درجتيهما3؛ لذلك لا يوجد تماثل ذاتي ينقل A إلى C. للمثال16 تماثلًا ومداران منفصلان. أما رسم المكعب المقارن فله48 تماثلًا ومدار واحد؛ نقدم قاعدة XOR تحفظ حوافه وتربط كل زوج من رؤوسه.

• انتقالية الرؤوس تعني وجود تماثل ذاتي مناسب لكل زوج من الرؤوس؛ ويمكن وصفها بوجود مدار واحد تحت التماثلات. يلزمها الانتظام، لكن الانتظام وحده لا يكفي. [1]
• نثبت المثال الأول بالحواف AC AD BC BD CD EG EH FG FH GH AE BF. كل رأس له ثلاثة جيران، والرسم متصل؛ لا نحكم من شكل الخطوط أو أطوالها.
• مثلثات المثال هي ACD وBCD وEGH وFGH. يمر بـA واحد وبـC اثنان؛ التماثل ينقل مثلثات الرأس تقابليًا، فيستحيل نقل A إلى C.
• حصر جميع40320 تبديلًا للرؤوس أعطى16 تماثلًا للمثال الأول. المداران هما ABEF وCDGH، وعدد أزواج الرؤوس المرتبة التي يمكن ربطها32 من64، مع احتساب الرأس مع نفسه.
• نسمي رؤوس المكعب بالثلاثيات من000 إلى111؛ التجاور يعني اختلاف خانة واحدة. تطبيق x↦x⊕(u⊕v) يرسل u إلى v ويحفظ هذا الاختلاف، فيعطي شاهدًا لكل زوج مرتب.
• حصر تبديلات المكعب أعطى48 تماثلًا ومدارًا واحدًا؛ تحققت أيضًا64 شهادة XOR للأزواج المرتبة. فحصنا هذين الرسمين الثابتين، ولا ندعي حصر كل الرسوم على ثمانية رؤوس.

السؤال عن وجود تماثل لكل زوج

التماثل الذاتي تقابل بين رؤوس الرسم يحفظ علاقة التجاور؛ إنه تماثل من الرسم إلى نفسه. [2] ننقل طرفي كل حافة، ثم نطلب أن تعود مجموعة الحواف الأصلية نفسها. لا يكفي أن تكون الصورة رسمًا آخر له العدد نفسه من الحواف.

نقول إن الرسم انتقالي الرؤوس إذا أمكن، لكل رأسين، اختيار تماثل ذاتي ينقل الأول إلى الثاني. التماثل المختار قد يختلف من زوج إلى آخر. وتكافئ هذه الخاصية وقوع الرؤوس كلها في مدار واحد تحت التماثلات. [1]

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

في مقال التبديل السابق، فشل تبديل محدد لرأسين في دورة، لكن دوران الأسماء يستطيع ربط أي رأسين فيها. السؤال الحالي أقوى من رفض مرشح واحد: نريد مثالًا يفشل فيه كل مرشح ينقل A إلى C، مع بقاء تساوي الدرجات.

سنثبت الأسماء A B C D E F G H والقوائم، ونعمل برسوم بسيطة غير موجهة. AB وBA يمثلان الحافة نفسها؛ لا حلقات أو أوزان أو حواف مكررة. تقاطع خطين في الصورة لا يضيف رأسًا، واللون وسيلة لعرض الشهادة المحلية فقط.

رسم متصل منتظم من قطعتين

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

ننشئ قطعة أخرى على E F G H بالحواف EG وEH وFG وFH وGH. هنا الزوج الناقص هو EF والمثلثان يشتركان في GH. ثم نربط القطعتين بالحافتين AE وBF. المجموع خمس حواف ثم خمس ثم اثنتان، أي12 حافة.

جيران A هم C وD وE، وجيران B هم C وD وF. جيران C هم A وB وD، وجيران D هم A وB وC. في القطعة الأخرى، جيران E هم G وH وA، وجيران F هم G وH وB، وجيران G هم E وF وH، وجيران H هم E وF وG.

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

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

مثلث واحد مقابل مثلثين يمنع النقل

المثلث ثلاث رؤوس مختلفة، تصل الحواف بين كل زوج منها. في القطعة الأولى لدينا ACD وBCD، وفي الثانية EGH وFGH. لا يوجد مثلث يمر بين القطعتين: الحافتان الرابطتان AE وBF لا تغلقان مع حافة ثالثة طريقًا من ثلاث حواف.

حول A، الجيران هم C وD وE. من الأزواج CD وCE وDE، توجد CD فقط، فيمر بـA مثلث واحد. حول C، الجيران هم A وB وD؛ الزوج AB غائب، لكن AD وBD موجودان، فيمر بـC مثلثان: CAD وCBD.

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

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

الصورة الداخلية تعرض الجوارين مع الحواف بين الجيران. حول A، تبقى AE خارج المثلث الذهبي ACD. حول C، يشترك المثلثان CAD وCBD في CD. نعد كل مجموعة من ثلاثة أسماء مرة واحدة، ولا نعد الاتجاهين أو ترتيب الأسماء مثلثات جديدة.

قائمة أعداد المثلثات هي (1,1,2,2,1,1,2,2). اختلاف العدد يمنع بعض عمليات النقل، لكن تساويه لا يثبت وحده وجود تماثل. فقد تتفق شهادة محلية وتختلف بنية أبعد؛ لذلك سنثبت انتقالية المكعب بخرائط فعلية، لا بأصفار المثلثات فقط.

ستة عشر تماثلًا ومداران

مدار الرأس هو مجموعة الصور التي يستطيع الوصول إليها تحت جميع تماثلات الرسم الذاتية. يسمح تماثل الهوية ببقاء الرأس نفسه، ويسمح التماثل العكسي بالعودة؛ وتركيب تماثلين يواصل الانتقال. لذلك تقسّم المدارات الرؤوس إلى مجموعات منفصلة.

عدد التقابلات الممكنة بين الأسماء الثمانية8!=40320. جرّبناها جميعًا على قائمة الحواف المعلنة، وقبلنا التبديل إذا أعاد الحواف الاثنتي عشرة نفسها. خرج16 تماثلًا، فتوجد تماثلات فعلية في المدخل؛ لا نقول إنه بلا تماثل.

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

عدد الأزواج المرتبة داخل مدار من أربعة رؤوس هو4×4=16، مع الأزواج التي طرفاها الرأس نفسه. للمدارين32 زوجًا يمكن ربطه، بينما المجموعة الكاملة من ثمانية رؤوس لها8×8=64 زوجًا. الأزواج الأخرى تربط رأسين من مدارين مختلفين.

عدد التماثلات16 ليس عدد الأزواج القابلة للربط32؛ قد يربط التماثل الواحد عدة أزواج، وقد تربط تماثلات مختلفة الزوج نفسه. ننشر العدين لأنهما يجيبان عن سؤالين: كم تقابلًا يحفظ الحواف، وكم طلب نقل له حل.

المكعب وشاهد ثنائي لكل زوج

للمكعب المقارن الحواف AB AC AE BD BF CD CG DH EF EG FH GH. نسمي الرؤوس بالثلاثيات A=000 وB=001 وC=010 وD=011 وE=100 وF=101 وG=110 وH=111. يكون رأسان متجاورين إذا اختلفت ثلاثيتاهما في خانة واحدة بالضبط.

لكل ثلاثية ثلاثة جيران، بقلب الخانة الأولى أو الثانية أو الثالثة. عدد الرؤوس8 ودرجتها3، فيكون عدد الحواف8×3÷2=12؛ القسمة لأن كل حافة حسبت عند طرفيها. ويمكن الوصول بين ثلاثيتين بقلب الخانات التي تختلفان فيها واحدة بعد أخرى.

لتعيين نقل من ثلاثية u إلى ثلاثية v، نثبت القناع s=u⊕v، ثم نرسل كل ثلاثية x إلى x⊕s. عملية XOR تقلب الخانات التي يقابلها1 في القناع وتترك بقية الخانات. وتطبيق القناع نفسه مرتين يعيد الثلاثية الأصلية، فالخريطة تقابل.

صورة u هي u⊕(u⊕v)=v. وإذا اختلفت x وy في خانة واحدة، فإن تطبيق القناع نفسه عليهما يبقي موضع اختلافهما نفسه؛ لأن القلب المشترك لا ينشئ اختلافًا جديدًا ولا يمحو الاختلاف القائم. لذلك تحفظ الخريطة حواف المكعب.

مثلًا، لنقل A=000 إلى H=111 نستخدم القناع111. الأزواج المتبادلة هي A مع H وB مع G وC مع F وD مع E. صورة الحافة AB هي HG، وهي GH الموجودة في القائمة؛ والقاعدة تحفظ الحواف الأخرى بالسبب نفسه، لا بفحص هذا الزوج وحده.

تحققنا من الخرائط لكل64 زوجًا مرتبًا. لكن الأقنعة الممكنة ثمانية فقط، فلا تعني64 شهادة أن لدينا64 تماثلًا مختلفًا من هذه القاعدة؛ يتكرر القناع لطلبات نقل مختلفة. والحصر الكامل40320 تبديلًا وجد48 تماثلًا للمكعب، ومدارًا واحدًا يضم الرؤوس كلها.

ما الذي تثبته المقارنة؟

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

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

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

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

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