تساوي الدرجات: هل يسمح بتبديل أي رأسين؟

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

لا؛ تساوي الدرجات لا يكفي للسماح بكل تبديل للرؤوس مع حفظ الرسم نفسه. في الدورة AB BC CD DE EF AF، يحفظ تبديل A وB الدرجات كلها، لكنه لا يحفظ الحواف. فحص720 تبديلًا لهذه الدورة يعطي12 تماثلًا ذاتيًا فقط. النسخة الناتجة من إعادة الأسماء تظل متماثلة البنية مع الأصل؛ المطلوب هنا أن يعيد التبديل حواف الرسم الثابت نفسها.

• التماثل الذاتي تبديل للرؤوس يحفظ علاقة التجاور، أي تماثل من الرسم إلى نفسه. [1] سنفحص قائمة الحواف الثابتة، لا شكل الصورة أو أطوال خطوطها.
• في الدورة AB BC CD DE EF AF، درجات الرؤوس الستة2. تبديل A وB وحدهما يرسل BC إلى AC وAF إلى BF؛ غياب هاتين الحافتين من الأصل ينفي أنه تماثل ذاتي.
• الدوران A→B→C→D→E→F→A يحفظ الحواف الست. هو تبديل للأسماء كلها وفق قاعدة واحدة، وليس إضافة أسهم إلى الرسم غير الموجه أو تحريك رأسين فقط.
• من720 تبديلًا للرؤوس في هذه الدورة، جميعها تحفظ الدرجات، لكن12 فقط تحفظ الحواف. يمكن اختيار صورة A بست طرق وصورة B بجوارها بطريقتين؛ بقية الدورة تتحدد، فيكون6×2=12.
• في النجمة AB AC AD AE AF، درجة A تساوي5 ودرجات الأوراق1. حفظ الدرجات يثبت A ويسمح بكل120 تبديلًا للأوراق؛ كل هذه التبديلات تحفظ الحواف الخمس في هذا المثال.
• راجعنا720 تبديلًا لكل من الدورة والنجمة، ثم جميع1024 رسمًا ذا خمسة رؤوس مع120 تبديلًا لكل رسم، أي122880 فحصًا. حفظ الدرجة شرط لازم، ويظهر في672 مدخلًا من هذه الرسوم تبديل يحفظها ولا يحفظ الحواف.

حفظ الجيران أقوى من حفظ عددهم

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

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

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

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

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

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

تبديل الرأسين المتجاورين يغير وصلتين

نثبت الدورة بالحواف AB وBC وCD وDE وEF وAF. لكل رأس جار سابق وجار لاحق حول الدورة، لذلك قائمة الدرجات هي (2,2,2,2,2,2). لا توجد حافة AC أوBF في هذه القائمة.

نعرف التبديل σ بأنه يرسل A إلى B وB إلى A، ويثبت C وD وE وF. على سبيل المثال، صورة BC تتكون من صورة B وصورة C: الأولى A والثانية C، فيصبح الزوج AC. ليس هذا الزوج حافة في الأصل.

وصورة AF هي BF، لأن صورة A تساويB وصورة F تساويF. أما AB فتذهب إلى BA، وهي الحافة الأصلية نفسها لأن الرسم غير موجه. والحواف CD وDE وEF لا تتغير؛ طرفا كل منها ثابتان تحت σ.

قائمة الصور هي AB وAC وBF وCD وDE وEF. لها ست حواف ودرجة كل رأس2، لكنها تختلف من قائمة الحواف الأصلية ذات الأسماء الثابتة. تكفي الحافة BC التي أرسلت إلى AC لنفي حفظ التجاور؛ الحافة الثانية تؤكد موضع الخطأ.

في الصورة الرئيسية نلون AC وBF بالأحمر في لوحة الصور. اللون يعني أنهما غير موجودتين في قائمة الأصل، وليس أنهما حافتان سالبتان أو موجهتان. وتبقى الدوائر الست مسماة، ولا نضيف رأسًا عند تقاطع خطين.

اللوحة اليمنى ما زالت دورة من ستة رؤوس، ويمكن تتبعها بالترتيب A ثم B ثم F ثم E ثم D ثم C ثم A. هي نسخة متماثلة البنية مع الأصل عبر إعادة الأسماء المعلنة. لهذا لا نستعمل المثال لنفي تماثل رسمين؛ ننفي أن σ يحفظ الرسم الأصلي من نفسه إلى نفسه.

دوران الأسماء يحفظ القائمة كلها

نأخذ تبديلًا آخر ρ يرسل A إلى B وB إلى C وC إلى D وD إلى E وE إلى F وF إلى A. جميع الصور مختلفة، ويصل كل اسم إلى اسم داخل المجموعة نفسها. هذه قاعدة شاملة للرؤوس الستة، لا نقل لرأس A وحده.

صورة AB هي BC، وصورة BC هي CD، وصورة CD هي DE. ثم DE تذهب إلى EF، وEF تذهب إلى AF، وAF تذهب إلى AB. كل زوج في هذه السلسلة حافة موجودة في قائمة الدورة الأصلية.

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

الأسهم في العبارة A→B→C→D→E→F→A تصف صور أسماء الرؤوس. حواف الدورة نفسها بقيت غير موجهة. لا نحسب طريقًا باتجاه الأسهم ولا نختبر اتصالًا قويًا؛ نقرأ التقابل ونطبقه على طرفي كل حافة.

الجدول يسجل صورة كل رأس تحت ρ وتحت σ، مع درجته في الدورة. نقرأ الصف نفسه في عمودي التبديلين، ثم نركب صورة حافة من صفّي طرفيها. تساوي2 في كل صف لا يمحو الفرق بين صوري BC في العمودين.

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

لماذا بقيت اثنا عشر من سبعمئة وعشرين؟

عدد التبديلات التقابلية للرؤوس الستة هو6!=720: ستة اختيارات للصورة الأولى، ثم خمسة، ثم أربعة، ثم ثلاثة، ثم اثنان، ثم واحد. في الدورة كلها درجة2، لذلك لا يستبعد شرط حفظ الدرجات أي تبديل من هذه التبديلات.

فحصنا صورة قائمة الحواف لكل تبديل، ووجدنا12 تبديلًا يعيد القائمة نفسها. الـ708 الأخرى تحفظ الدرجات لكنها لا تحفظ علاقة التجاور كلها. العدد720 يصف تبديلات الرسم المعلن، وليس عدد رسوم جديدة مختلفة في البنية.

يمكن تبرير12 مباشرة أيضًا. نختار صورة A بين الرؤوس الستة. يجب أن تقع صورة B عند أحد جاري تلك الصورة، لأن AB حافة. يعطي ذلك ستة اختيارات مضروبة في اختيارين، قبل تعيين بقية الأسماء.

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

السير حول هذه الدورة في أي من الاتجاهين يكمل التقابل، وتبقى صورة AF حافة تغلق الدورة. إذن كل اختيار من6×2 يعطي تبديلًا صالحًا، ويختلف من الاختيارات الأخرى بصورتي A أوB. لهذا العدد12، لا مجرد حد أعلى.

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

في النجمة تعمل كل تبديلات الأوراق

نثبت النجمة ذات الحواف AB وAC وAD وAE وAF. A هو المركز، وجميع الرؤوس الخمسة الأخرى أوراق متصلة به فقط. قائمة الدرجات في ترتيب الأسماء هي (5,1,1,1,1,1). ولا حواف بين ورقتين.

أي تبديل يحفظ الدرجات يجب أن يثبت A، لأنه الرأس الوحيد ذو الدرجة5. يمكنه تبديل B وC وD وE وF فيما بينها، لأنها كلها درجة1. عدد هذه التبديلات5!=120، وقد فحصناها ضمن جميع720 تبديلًا للرؤوس الستة.

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

مثلًا، تبديل B وC وحدهما يبدل AB مع AC ويترك AD وAE وAF. هذا تماثل ذاتي للنجمة، بينما تبديل A مع B يفشل اختبار الدرجات من البداية. اختلاف مركز واحد عن الأوراق يساعد على الاستبعاد دون اختبار حواف كثيرة.

الصورة الداخلية تجمع دوران الدورة الصالح وتبديل الورقتين في النجمة. الذهبية على B وC في النجمة تعين الاسمين المتبادلين؛ الحواف ما زالت زرقاء غير موجهة. لا نعني أن كل رسم له أوراق يسمح بكل تبديل لها عند وجود مراكز مختلفة.

المقارنة توضح حدود الاختبار: في النجمة تساوى عدد المرشحين بحسب الدرجات مع عدد التماثلات الذاتية120. وفي الدورة كان المرشحون720 والناجحون12 فقط. لا نحول نجاح الشرط في مدخل واحد إلى قاعدة تكفي لكل الرسوم.

الدرجة مرشح والحواف هي الفحص الحاسم

راجعنا جميع720 تبديلًا للدورة وجميع720 للنجمة، وليس بضعة تبديلات مرسومة فقط. سجلنا صور الحواف وأعداد المرشحين بحسب الدرجات والتماثلات الذاتية، وراجعنا σ وρ وتبديل الورقتين B وC بصورة مستقلة من قوائم الحواف.

ثم ولدنا جميع1024 رسمًا بسيطًا على خمسة رؤوس ثابتة. لكل مدخل اختبرنا120 تبديلًا تقابليًا لهذه الأسماء الخمسة، فكان عدد حالات الفحص1024×120=122880. هذا نطاق محدد يمكن إعادة تنفيذه دون ادعاء حصر الرسوم على ستة رؤوس.

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

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

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

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