تثبيت الرؤوس وكسر التناظر: لماذا لا يكفي رأس واحد في الدورة؟

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

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

• المجموعة المحددة لتماثلات الرسم تختار رؤوسًا لا يثبتها كلها سوى تناظر الهوية، والعدد المحدد هو أصغر حجم لمثل هذه المجموعة. [1]
• في C4، تثبيت A يترك الهوية وتبديل B مع D، فيفشل الرأس الواحد مهما اخترنا موضعه؛ المجموعة الفارغة تترك التناظرات الثمانية كلها.
• تثبيت A وB المتجاورين يثبت D ثم C، فلا تبقى إلا الهوية؛ لكن تثبيت A وC المتقابلين يترك تبديل B مع D، فلا يكفي أي زوج كيفما اتفق.
• حفظ المجموعة {A,B} يسمح بتبديل A مع B وC مع D، بينما تثبيت A نفسه وB نفسه يمنعه؛ علامة عضوية واحدة لا تعني تثبيت الرؤوس فردًا فردًا.
• تحدد صور الرؤوس المختارة كل تناظر تحديدًا وحيدًا إذا وفقط إذا لم يبق غير الهوية مثبتًا لها؛ في {A,B} نميز القائمة المرتبة لصورتيهما عن مجموعة الصورتين.
• طرف P3 يكفي وحده ووسطه لا يكفي؛ نجمة بثلاث أوراق تحتاج تثبيت ورقتين، وK4 وأربعة معزولين يحتاجان ثلاثة رؤوس، والمعزول الوحيد يقبل المجموعة الفارغة.
• وافق حصران في 25 نموذجًا و 64 رسمًا من أربعة رؤوس، شمل كل المجموعات لا مجموعات الحد الأدنى فقط؛ في الأربعة 36 حدها 1 و 26 حدها 2 واثنتان حدهما 3، دون تعميم نتائج الحصر.

نختار رؤوسًا يجب أن يثبت كل واحد منها

يعرف المصدر تناظر الرسم بأنه تقابل للرؤوس يحفظ التجاور، ويعرف المجموعة المحددة بأنها مجموعة رؤوس لا يثبتها سوى الهوية، ويأخذ أصغر حجم لها عددًا محددًا للرسم. [1]

نستعمل أيضًا تعريف التناظر بأنه تبديل للرؤوس يحفظ علاقة التجاور، أي تماثل للرسم مع نفسه. [2]

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

نقول إن S تكسر التناظر المطلوب إذا كان التبديل الوحيد الذي يحفظ الحواف ويحقق هذه التثبيتات هو الهوية. نبحث أصغر عدد رؤوس مختارة، دون إسناد ألوان للرؤوس أو الحواف، ودون شرط صحة تلوين.

علامة الرأس في الرسم التوضيحي تعني أنه مطلوب الثبات باسمه نفسه. العلامة ليست لونًا يدخل في مسألة تلوين، ولا تسمح بتبادل الرؤوس المختارة فيما بينها.

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

تثبيت رأس واحد في C4 يترك انعكاسًا

نكتب رؤوس الدورة A B C D وحوافها AB BC CD DA فقط. لا توجد الحافتان AC وBD. للدورة ثمانية تناظرات قبل تثبيت أي رأس.

اختر S={A}. الحركة A→A وB→D وC→C وD→B تحفظ الحواف: AB تتحول إلى AD، وBC إلى DC، والحافتان الأخريان تتحولان بالعكس.

هذه الحركة تثبت A المختار وتثبت C أيضًا، لكنها تبدل B وD. فهي غير الهوية وتحقق شرط تثبيت A؛ لا تكسر المجموعة ذات الرأس الواحد كل التناظرات.

يبقى بعد تثبيت A تناظران فقط: الهوية وهذا الانعكاس. اختيار B أوC أوD بدلًا من A لا يعالج المشكلة؛ لكل رأس انعكاس يثبته ويثبت مقابله ويبادل الرأسين الآخرين.

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

المتجاوران يكفيان والمتقابلان لا يكفيان

اختر S={A,B} واشترط تثبيت A نفسه وB نفسه. جيران A هما B وD، وبعد تثبيت A وB لا يبقى لـD إلا أن يثبت لأنه جار A الآخر.

جيران B هما A وC، فيثبت C بالطريقة نفسها. ثبتت الرؤوس الأربعة، فلا يبقى سوى الهوية؛ المجموعة ذات الرأسين المتجاورين تنجح.

مع استبعاد الصفر والواحد سابقًا، يثبت الحد الأدنى اثنين. المجموعات الدنيا الأربع هي {A,B} و{A,D} و{B,C} و{C,D}، أي أزواج الحواف الأربع.

أما S={A,C} فلا تنجح. الانعكاس الذي ثبت A في المثال السابق يثبت C كذلك، ويظل قادرًا على تبادل B وD. يبقى تناظران مثبتان للرأسين المختارين.

وكذلك الزوج {B,D} يترك تبديل A مع C. إذن من الأزواج الستة الممكنة في الدورة تنجح أربعة وتفشل اثنتان، رغم أن حجم كل زوج اثنان.

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

حفظ المجموعة لا يثبت عناصرها واحدًا واحدًا

في S={A,B}، قارن بين شرطين: أن تكون صورة A هي A وصورة B هي B، وأن تكون مجموعة صورتيهما هي {A,B} فقط. الثاني يسمح بصورتي A وB أن تتبادلا.

الحركة A→B وB→A وC→D وD→C تحفظ الدورة وتحفظ المجموعة {A,B} بوصفها مجموعة، لكنها لا تثبت A أوB فرديًا. لذلك تدخل في فحص حفظ المجموعة وتخرج من فحص التثبيت الفردي.

تحت شرط التثبيت الفردي يبقى تناظر واحد لهذه المجموعة؛ وتحت حفظ المجموعة يبقى اثنان. وللمجموعة المقابلة {A,C} يبقى اثنان فرديًا وأربعة عند حفظ المجموعة فقط.

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

وفي المسألة التي تجمع صحة تلوين الرؤوس مع تمييز التناظر، نبحث أقل ألوان في تلوين صحيح لا يحفظه سوى الهوية. [3]

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

في جدول المقارنة، العمود الفردي هو شرط قبول المجموعة المحددة؛ العمود الجماعي تشخيص يشرح لماذا لا تكفي عبارة «الرؤوس المختارة تبقى مختارة».

صور المختارين تحدد التناظر إذا سجلنا كل صورة

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

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

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

في C4 مع S={A}، صور A الممكنة أربع، بينما التناظرات ثمانية؛ يوجد تناظران لكل صورة، فلا تحدد صورة A التناظر وحدها. ومع S={A,B} توجد ثماني قوائم مرتبة مختلفة للصور للتناظرات الثمانية.

نكتب صورة A أولًا وصورة B ثانيًا؛ مثل (A,B) و(B,A) قائمتان مختلفتان. لكن إذا حذفنا هذا الارتباط بالأسماء وأخذنا مجموعة الصورتين فقط، اتفقت الحركتان على المجموعة {A,B} رغم اختلافهما.

الحصر فحص هذا التكافؤ لكل مجموعة مختارة: عدد القوائم المرتبة المختلفة لصور المختارين يساوي عدد تناظرات الرسم إذا وفقط إذا لم يبق غير الهوية مثبتًا لهم. لا نحتاج حساب مسافات الرؤوس لتطبيق الاختبار.

طرف المسار وورقتا النجمة يوضحان أثر الاختيار

في P3 بالرؤوس A B C والحافتين AB BC، تثبيت الوسط B لا يمنع تبديل A مع C. أما تثبيت الطرف A فيثبت جاره B ثم الطرف الباقي C، فيكفي رأس واحد. المجموعة الفارغة تفشل لأن تبادل الطرفين تناظر غير الهوية.

في النجمة ذات المركز A والأوراق B C D، يمكن تبديل أي أوراق مع تثبيت المركز. إذا اخترنا ورقة واحدة بقي تبادل الورقتين الأخريين؛ اختيار المركز وحده لا يحد تبديلات الأوراق أصلًا.

ثبّت B وC فرديًا: يثبت المركز A لأنه الرأس الوحيد ذو ثلاثة جيران، ثم تثبت الورقة المتبقية D. لذلك تكفي ورقتان، ومع فشل كل اختيار ذي رأس واحد يثبت الحد اثنين.

لكن تثبيت المركز A وورقة B لا يكفي، لأن C وD يظلان قابلين للتبادل. مثل زوجي الدورة، مجموعتان متساويتان في الحجم قد تختلفان في النجاح.

في K4، كل تبديل للرؤوس يحفظ الرسم الكامل. إذا بقي رأسان غير مثبتين، أمكن تبادلهما؛ لذلك يلزم تثبيت ثلاثة رؤوس. يثبت الرأس الرابع تلقائيًا، فيكفي العدد ثلاثة.

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

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

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

نحصي كل المجموعات ولا نتوقف عند أول حجم ناجح

فحصنا 25 نموذجًا و 64 رسمًا مسمى من أربعة رؤوس، أي جميع اختيارات الحواف من الأزواج الستة. احتفظنا ببيانات الرسوم من فحص سابق، ثم حسبنا مجموعات التثبيت من جديد، دون استعارة حدود ألوان الرؤوس.

الحصر الأول جرب جميع تبديلات الرؤوس وحفظ ما يحفظ مجموعة الحواف. ثم جرب جميع المجموعات المختارة بحسب الحجم من صفر حتى جميع الرؤوس؛ لم يتوقف عند أول مجموعة ناجحة.

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

جرب كل منهما 15229 تبديل رؤوس في النماذج و 1536 في الأربعة. جرب كل منهما 962 مجموعة في النماذج و 1024 في الأربعة؛ لأن كل رسم من أربعة رؤوس له 16 مجموعة، تشمل الفارغة والمجموعة الكاملة.

اتفقا على التناظرات، ومثبتات المجموعات الفردية والجماعية، وتحديد التناظر بصور المختارين، والحدود وكل الشواهد الدنيا. وفي الأربعة، 36 رسمًا حده 1 و 26 حده 2 واثنان حدهما 3؛ جميعها تقبل حلًا.

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

الجدول يعد مجموعات C4 بحسب حجمها ويبين نجاح التثبيت الفردي. الأعداد تخص الرسوم المختبرة، ولا تتبنى نتائج المصدر لعائلات الرسوم أو لتثبيت الحواف. المراجعة تحريرية آلية، ولا ندعي مراجعة بشرية أو اعتماد خبير.