تمييز الجيران بمجموع أوزان الحواف: لماذا تكفي قيمتان للدورة الرباعية؟

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

تكفي أوزان حتى 2 للدورة الرباعية لأن التعيين 1،1،2،2 يعطي المجاميع 3،2،3،4 المختلفة عند طرفي كل حافة، بينما حد 1 يعطي المجموع 2 عند الرؤوس الأربعة فيفشل.

• نعطي الحواف أوزانًا صحيحة ونطلب اختلاف مجاميع الرؤوس المتجاورة؛ نختار {1,...,k} ونقلل الحد الموجب k، دون منع تساوي أوزان الحواف المتلاقية. [1]
• على الدورة AB BC CD DA، الأوزان AB=1 وBC=1 وCD=2 وDA=2 تعطي مجاميع A B C D بالقيم 3،2،3،4؛ طرفا كل حافة مختلفان، وتساوي A وC مسموح لأنهما غير متجاورين.
• مع k=1 تكون الأوزان كلها 1، وكل رأس في الدورة له حافتان فيكون مجموعه 2؛ تفشل الحواف الأربع، فيلزم حد 2، وقد كتبنا شاهدًا يحققه.
• في تمييز جميع الرؤوس نرفض تساوي A وC، فتحتاج الدورة حدًا 3 في الحصر السابق؛ أما النجمة بثلاث أوراق فتقبل هنا أوزانًا كلها 1، رغم تساوي مجاميع الأوراق الثلاث عند 1.
• عندما تكون الأوزان كلها 1، يساوي مجموع الرأس درجته؛ يكفي الحد 1 بالضبط عندما تختلف درجتا طرفي كل حافة، دون اشتراط اختلاف درجات جميع الرؤوس.
• أي عدد من الرؤوس المعزولة مسموح لأن المعزول لا يدخل مقارنة على حافة؛ لكن حافة تشكل مكونًا وحدها تجعل مجموع طرفيها متساويًا مهما اخترنا وزنها، فتمنع الحل.
• راجعنا 25 نموذجًا و 64 رسمًا من أربعة رؤوس؛ الفحص المنفصل جرب 5603 تعيينات في النماذج و 1516 في رسوم الأربعة رؤوس، ووافق الحدود والشواهد؛ في الرسوم 17 بحد 1 و 33 بحد 2 و 5 بحد 3 و 9 بلا حل.

نقارن طرفي كل حافة، ولا نضيف مقارنات بين غير المتجاورين

خاصية الأوزان في المصدر تعني إسناد أعداد صحيحة من مجموعة محددة للحواف، مع اختلاف مجموع أوزان الحواف عند كل رأسين متجاورين. [1]

نختار المجموعة {1,...,k} والأوزان الموجبة، ونقلل k الموجب؛ لا نشترط اختلاف قيم الحواف المتلاقية. [1]

في تلوين الحواف الصحيح، تختلف ألوان الحافتين إذا التقتا عند رأس؛ هذا قيد آخر، ولا نضيفه إلى مسألة الأوزان هنا. [2]

نكتب Q[A] لمجموع أوزان الحواف الملتقية عند A، مع حساب كل حافة مرة، حتى لو تكرر وزنها. لا نضيف وزنًا مستقلًا للرأس، ولا نجمع أسماء جيرانه.

نفترض رسمًا بسيطًا غير موجه، له رأس واحد على الأقل. نفحص Q[u]≠Q[v] لكل حافة uv أصلية؛ رأس غير متجاور مع آخر لا يحتاج إلى مجموع مختلف عنه.

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

الدورة الرباعية: المجاميع 3،2،3،4 تنجح على الحواف الأربع

الدورة هنا حواف AB BC CD DA فقط، دون قطري AC أو BD. نعطي AB=1 وBC=1 وCD=2 وDA=2.

عند A نجد Q[A]=1+2=3، وعند B نجد Q[B]=1+1=2. وعند C نجد Q[C]=1+2=3، وعند D نجد Q[D]=2+2=4.

نراجع الحواف الأصلية: AB تقارن 3 و 2، وBC تقارن 2 و 3، وCD تقارن 3 و 4، وDA تقارن 4 و 3؛ لا يوجد زوج متساوٍ على حافة.

يتساوى Q[A]=Q[C]=3، لكن AC ليست حافة في هذه الدورة. لذلك لا نفشل الشاهد بسبب هذه المقارنة، ولا نرسم حافة جديدة لفرضها.

الحافتان AB وBC تلتقيان عند B ولهما الوزن 1، وكذلك CD وDA لهما الوزن 2 عند D؛ التكرار مسموح، فليس هذا شاهدًا لتلوين الحواف الصحيح.

كل وزن من 1 إلى 2، فالشاهد يثبت أن الحد 2 يكفي. المجموع عند D هو 4، وهذا لا يخرق الحد الذي يخص وزن الحافة فقط.

حد 1 يفشل لأن الرؤوس الأربعة درجتها 2

عند الحد k=1، لا نملك إلا الوزن 1، فيجب أن تأخذه الحواف الأربع. لا توجد حرية في اختيار توزيع مختلف داخل هذه اللوحة.

كل رأس في الدورة له حافتان، فيكون مجموع أوزانه 1+1=2. إذن مجاميع A B C D هي 2،2،2،2.

طرفا AB متساويان، وكذلك طرفا كل حافة أخرى، فيفشل شرط الجيران. هذا يستبعد الحد الموجب الوحيد الأصغر من 2.

الشاهد 1،1،2،2 نجح بحد 2، والحد 1 مستبعد؛ لذلك الحد الأدنى للدورة الرباعية هنا هو 2.

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

تمييز جميع الرؤوس يضيف مقارنات، ومنها الزوج A وC

في قوة عدم الانتظام، نضع أوزانًا من 1 إلى k على الحواف، ونطلب اختلاف مجموع أوزان الحواف عند كل رأسين مختلفين؛ نقلل k، ولا نشترط التلوين الصحيح للحواف. [3]

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

للدورة الرباعية، الشاهد 1،1،2،2 ينجح للجيران، ويفشل لجميع الرؤوس عند A وC. في المسألة العامة يحتاج الرسم حدًا 3، بشاهد AB=1 وBC=1 وCD=2 وDA=3 ومجاميع 4،2،3،5.

في النجمة بحواف AB AC AD، الأوزان كلها 1 تعطي المركز A المجموع 3، والأوراق B وC وD المجموع 1. كل حافة تصل 3 إلى 1، فينجح تمييز الجيران بحد 1.

الأوراق غير متجاورة، فلا نقارن B مع C أو D هنا. لكن تمييز جميع الرؤوس يتطلب ثلاثة أوزان مختلفة على الحواف لأن كل ورقة ترى وزن حافتها وحده؛ الشاهد 1،2،3 يعطي المركز 6 والأوراق 1 و 2 و 3.

إضافة رأس معزول أو أكثر لا تضيف حواف ولا مقارنات في مسألة الجيران، بينما معزولان في المسألة العامة لهما المجموع 0 نفسه، فيستحيل تمييز جميع الرؤوس.

متى يكفي وزن 1 على كل حافة؟ ننظر إلى درجتي كل طرفين

إذا أعطينا كل حافة الوزن 1، فمجموع أوزان الرأس هو عدد حوافه الملتقية، أي درجته. لذلك Q[A] يساوي درجة A تحت هذا التعيين.

يكون التعيين ناجحًا للجيران إذا وفقط إذا اختلفت درجتا طرفي كل حافة. الشرط يخص الحواف الأصلية، ولا يشترط اختلاف درجات الرؤوس غير المتجاورة.

النجمة بثلاث أوراق مثال ناجح: درجة المركز 3 ودرجة كل ورقة 1. تكرار درجة الأوراق لا يضر لأنها لا تتصل ببعضها بحواف.

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

هذا اختبار للحد 1 فقط. إذا فشل، نعرف أن الحد الأدنى أكبر من 1 أو أن الحل مستحيل، ولا نستنتج منه وحده أن حد 2 سيكفي لكل رسم.

المعزول لا يدخل مقارنة، والحافة المنفردة تمنع الحل

الرأس المعزول مجموعه 0، لكنه ليس طرفًا لأي حافة. يجوز وجود معزولين كثيرين جميع مجاميعهم 0، ولا يخالف ذلك شرط الجيران.

أما الحافة التي تشكل مكونًا وحدها، فلكل طرف حافة واحدة هي نفسها؛ إذا كان وزنها t، كان مجموع كل طرف t، وهما متجاوران، فيستحيل الحل مهما كبر الحد.

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

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

على الدورة، الأوزان AB=1 وBC=2 وCD=4 وDA=8 تعطي المجاميع 9،3،6،12، فتنجح المقارنات الأربع. لكنها تحتاج حدًا 8، وقد وجدنا حدًا 2؛ شاهد الوجود لا يثبت أقل حد.

وجود المعزولين لا يغير هذا البرهان، لأننا لا نقارنهم بغيرهم. ولا نزعم حدًا ثابتًا لجميع الرسوم بناء على أمثلتنا الصغيرة.

حصر الأوزان يفحص الحواف الأصلية، ويحتفظ بالتكرار العددي

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

حصرنا 25 نموذجًا، وجربنا الحدود من k=1 حتى أول حد ناجح. جمعنا الوزن مرة لكل حافة ملتقية، وقارنا طرفي كل حافة أصلية، دون حذف تبديلات الأرقام أو اشتراط اختلاف أوزان الحواف المتلاقية.

فحص منفصل بطريقة حاصل الضرب جرب 5603 تعيينات عبر الحدود المختبرة للنماذج، ومنها 496 تميز الجيران، و 177 تميز جميع الرؤوس أيضًا؛ الفحص العام الأخير تشخيص إضافي لا شرط قبول هنا.

في أربعة رؤوس توجد ست حواف ممكنة، ومنها 64 رسمًا مسمى. تسعة بلا حل؛ الحد الأدنى 1 في 17، و 2 في 33، و 3 في 5. المجموع 64.

الفحص المنفصل جرب 1516 تعيينًا لهذه الرسوم عبر الحدود المختبرة؛ 377 تميز الجيران، و 288 من هذه التعيينات تميز جميع الرؤوس أيضًا. هذه أعداد تعيينات، لا أعداد رسوم أو أزمنة تنفيذ.

راجعنا الحدود والشواهد وأعداد التعيينات، واختبار الحد 1 بالدرجات، والمعزولين والحواف المنفردة، وشواهد قوى 2؛ وافق الفحص المنفصل الحصر الأول في كل حد جربناه.

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