التلوين الكلي بمجاميع الجيران: لماذا يحتاج المثلث العدد 5؟

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

يحتاج المثلث الحد 5 لأن التلوينات الكلية الصحيحة حتى الحد 4 لا تميز مجاميع طرفي كل حافة، بينما التعيين A=1 وB=2 وC=3 مع AB=3 وBC=5 وCA=4 يعطي المجاميع 8،10،12 المختلفة.

• نعطي كل رأس وحافة عددًا صحيحًا موجبًا من 1 إلى k في تلوين كلي صحيح، ثم نقارن مجموع عدد الرأس وأعداد حوافه عند كل رأسين متجاورين، ونقلل k. [1]
• الشاهد A=1 وB=2 وC=3 مع AB=3 وBC=5 وCA=4 صحيح كليًا، ومجاميعه 8،10،12 مختلفة؛ الحد 5 يخص الأعداد المعينة، ولا يحد المجاميع الناتجة.
• للمثلث لا يوجد تلوين كلي صحيح بحد 1 أو 2؛ عند الحد 3 توجد 6 تعيينات صحيحة وعند 4 توجد 96، ولا يميز أي منها المجاميع؛ عند 5 توجد 780 تعيينًا صحيحًا، منها 288 يميز المجاميع، فيثبت أقل حد 5.
• التلوين الكلي العادي للمثلث يحتاج 3 فقط؛ وتبديل العددين 4 و 5 في الشاهد يحافظ على صحته الكلية، لكنه يعطي المجاميع 9،9،12 ويفشل على AB، فلا نحذف تبديلات أسماء الأعداد قبل فحص المجاميع.
• أوزان الحواف وحدها لا تحل الحافة المنفردة، أما هنا فتعطي A=1 وB=2 وAB=3 المجاميع 4 و 5 بحد أدنى 3؛ وعلى المسار P3 ينجح الحد 3 بمجاميع 4،6،4، فتساوي الطرفين غير المتجاورين مسموح.
• لكل رسم بسيط حل بإعطاء جميع رؤوسه وحوافه قوى مختلفة للعدد 2؛ يسمح بأي عدد من المعزولين، وباصطلاح حد موجب 1 للرسم الخالي من الحواف؛ شاهد الوجود لا يثبت أقل حد.
• راجعنا 10 نماذج و 64 رسمًا من أربعة رؤوس بطريقتين؛ الفحص المنفصل جرب 13300636 تعيينًا للنماذج و 26072442 للرسوم، ووافق الحدود والشواهد؛ توزيع حدود الرسوم هو واحد بحد 1 و 21 بحد 3 و 31 بحد 4 و 11 بحد 5.

عدد الرأس نفسه يدخل المجموع، والتلوين الصحيح يشمل الرؤوس والحواف

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

التلوين الكلي الصحيح يفرض اختلاف لوني الرأسين المتجاورين، واختلاف لوني الحافتين المتلاقيتين، واختلاف لون الرأس عن لون كل حافة ملتقية به. [2]

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

لا نجمع أعداد الرؤوس المجاورة لـA. ولا نضيف مقارنة بين رأسين غير متجاورين أو رأسين من مكونين منفصلين؛ العدد على الرأس والعدد على الحافة كميتان معينتان، والمجموع ناتج محسوب.

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

الشاهد بحد 5: الرؤوس 1،2،3 والحواف 3،5،4

المثلث حوافه AB BC CA، وكل رأسين فيه متجاوران. نعطي A=1 وB=2 وC=3، والحواف AB=3 وBC=5 وCA=4.

الرؤوس المتجاورة تحمل أعدادًا مختلفة، والحواف الثلاث تحمل أعدادًا مختلفة. AB بالعدد 3 تختلف عن طرفيها 1 و 2؛ BC بالعدد 5 تختلف عن 2 و 3؛ CA بالعدد 4 تختلف عن 3 و 1.

عدد C يساوي عدد الحافة AB، وكلاهما 3، وهذا مسموح لأن C ليس طرفًا لـAB. لا يتطلب التلوين الكلي اختلاف أعداد العناصر غير المتجاورة وغير الملتقية.

المجاميع هي S[A]=1+3+4=8، وS[B]=2+3+5=10، وS[C]=3+5+4=12. نفحص AB وBC وCA: كل حافة تصل مجموعين مختلفين، فينجح الشاهد.

كل عدد معين يقع بين 1 و 5. هذا يثبت أن الحد 5 يكفي، ولا يثبت أنه الأقل قبل استبعاد الحدود الأصغر.

الحدان 3 و 4 يعطيان تلوينات صحيحة، لكنها لا تميز المجاميع

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

عند الحد 3، فحصنا التعيينات الكلية الصحيحة الستة؛ لا يميز أي منها المجاميع. مثالها A=1 وB=2 وC=3 مع AB=3 وBC=1 وCA=2، وفيه المجاميع 6،6،6.

عند الحد 4، فحصنا 96 تعيينًا كليًا صحيحًا؛ لا يميز أي منها مجاميع طرفي كل حافة. العدد 96 يشمل التعيينات التي لا تستعمل 4 أيضًا، لأن اللوحة المسموحة من 1 إلى 4.

مثال يستعمل 4 هو A=1 وB=2 وC=3 مع AB=3 وBC=1 وCA=4. هذا تلوين كلي صحيح، لكنه يعطي المجاميع 8،6،8؛ الحافة CA تفشل لتساوي مجموعي طرفيها.

فشل مثال واحد بحد 4 لا يكفي لاستبعاد الحد. استبعدناه بحصر كل التعيينات الصحيحة الـ96، بعد فحص جميع شروط التلوين الكلي، ثم فحص الحواف الأصلية.

عند الحد 5، وجدنا 780 تعيينًا كليًا صحيحًا، ومنها 288 يميز المجاميع. كل الحدود الموجبة الأصغر مستبعدة، وقد كتبنا شاهدًا ناجحًا بحد 5، إذن الحد الأدنى هو 5.

ثلاثة ألوان تكفي للتلوين العادي، وتبديل أسماء الأعداد قد يفسد المجاميع

التعيين A=1 وB=2 وC=3 مع AB=3 وBC=1 وCA=2 صحيح كليًا ويستعمل ثلاثة ألوان. احتياج رؤوس المثلث إلى ثلاثة ألوان يستبعد أقل منها، فيثبت الحد العادي 3.

المجاميع في ذلك الشاهد كلها 6، فيفشل شرط المجاميع. لذلك إضافة القيد العددي رفعت الحد من 3 في التلوين الكلي العادي إلى 5 في المسألة الحالية.

في شاهد الحد 5 الناجح، نبدل اسمي العددين 4 و 5 في كل العناصر. تبقى الرؤوس A=1 وB=2 وC=3، وتصبح الحواف AB=3 وBC=4 وCA=5.

كل اختلاف بين عددين معينين محفوظ، فيبقى التلوين الكلي صحيحًا. لكن المجاميع تصبح 9،9،12؛ الحافة AB تفشل. كلا التعيينين يستعمل الأعداد الخمسة، ومع ذلك نجح أحدهما وفشل الآخر.

لذلك لا نعامل كل تبديلات أسماء الأعداد كحالة واحدة عند فحص المجاميع. قواعد التلوين الصحيح تتعلق بالمساواة، وقواعد الجمع تتعلق بالقيم العددية.

الحافة المنفردة تنجح هنا، ومجاميع طرفي المسار قد تتساوى

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

الحافة AB إذا كانت مكونًا وحدها تجعل مجموع طرفيها يساوي وزنها نفسه، فلا يوجد حل في مسألة الحواف وحدها. هنا يدخل عدد كل رأس مستقلًا، فيمكن اختلاف المجموعين.

الشاهد A=1 وB=2 وAB=3 صحيح كليًا، ومجموعاه 4 و 5. الرأس A والرأس B والحافة AB عناصر متعارضة زوجيًا في التلوين الكلي، فيلزمها ثلاثة أعداد مختلفة، فيثبت الحد الأدنى 3.

للمسار P3 بحواف AB BC، نعطي A=1 وB=2 وC=3 مع AB=3 وBC=1. هذا صحيح كليًا، ويعطي المجاميع 4،6،4؛ كل حافة تقارن قيمتين مختلفتين.

لا توجد حافة AC، فتساوي مجموعي A وC مسموح. والحافتان الملتقيتان عند B مع الرأس B تحتاج ثلاثة أعداد مختلفة، فتستبعد الحد 2 وتثبت أقل حد 3.

قوى 2 على كل العناصر تعطي شاهد وجود، والمعزول لا يفرض مقارنة

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

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

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

الرأس المعزول مجموعه هو عدد نفسه، وليس 0. أي عدد من المعزولين مسموح لأنهم لا يدخلون مقارنة على حافة؛ يمكن إعطاؤهم جميعًا العدد 1.

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

الحصر يفحص التلوين الكلي أولًا، ثم يقارن مجاميع الحواف الأصلية

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

راجعنا 10 نماذج و 64 رسمًا مسمى من أربعة رؤوس، من الحواف الست الممكنة. جربنا كل حد من 1 حتى أول حد ناجح، وفحصنا شروط التلوين الكلي الثلاثة ثم مجاميع طرفي كل حافة.

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

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

في رسوم الأربعة رؤوس، جرب الفحص المنفصل 26072442 تعيينًا؛ 49441 صحيح كليًا، و 24505 منها يميز الجيران بالمجموع، و 19824 من الأخيرة يميز جميع الرؤوس أيضًا. هذه أعداد تعيينات، لا أعداد رسوم أو أزمنة تنفيذ.

توزيع الحدود الدنيا للمجاميع في الرسوم الـ64 هو: رسم واحد بحد 1، و 21 بحد 3، و 31 بحد 4، و 11 بحد 5؛ كلها لها حل. للتلوين الكلي العادي التوزيع: واحد بحد 1، و 37 بحد 3، و 25 بحد 4، وواحد بحد 5.

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