تمييز جميع الرؤوس دون شرط التلوين الصحيح: لماذا يكفي للمسار لونان؟

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

يكفي للمسار لونان لأن التعيين A=1 وB=1 وC=2 مع AB=1 وBC=2 يعطي المجموعات {1} و{1,2} و{2} المختلفة جميعًا، والتلوين العام يسمح بمخالفة شروط الصحة الكلية.

• نعين ألوانًا للرؤوس والحواف، ونطلب اختلاف مجموعة لون الرأس وألوان حوافه لكل رأسين مختلفين، ثم نقلل عدد الألوان؛ التلوين العام لا يشترط أن يكون صحيحًا. [1]
• شاهد المسار P3 هو A=1 وB=1 وC=2 مع AB=1 وBC=2؛ مجموعاته {1} و{1,2} و{2} تميز الأزواج الثلاثة، رغم تساوي لون الرأسين المتجاورين A وB وتكرار لون رأس مع حافته.
• اللون الواحد يجعل كل المجموعات {1} فلا يميز رؤوس المسار؛ شاهد اللونين يثبت أنهما الأقل، بينما التلوين الكلي الصحيح المميز للجميع كان يحتاج أربعة.
• تكرار اللون داخل مجموعة الرأس يحسب مرة واحدة؛ حجمها بين واحد ودرجة الرأس زائد واحد، ولا يساوي هذا الحد دائمًا، مع بقاء أسماء الألوان قابلة للتبديل العام دون تغيير النجاح.
• لوحة k ألوان تعطي 2^k-1 مجموعة غير فارغة؛ يجب أن تكفي لعدد الرؤوس، لكن القيد لازم لا يكفي وحده، والمثلث لا يقبل لونين رغم توافر ثلاث مجموعات غير فارغة.
• لون مختلف لكل رأس وحافة يثبت الوجود؛ المعزولين يحتاجون مجموعات مختلفة، والرسم الخالي من الحواف بأربعة رؤوس يحتاج أربعة ألوان؛ إعادة استخدام لون غير معزول تتطلب فحص المجموعة، لأنها قد تكون مفردة أيضًا.
• وافق فحص كل التعيينات المسماة حصر الأنماط في 10 نماذج و 64 رسمًا من أربعة رؤوس؛ 63 رسمًا منها يحتاج ثلاثة ألوان وواحد يحتاج أربعة؛ صحة التلوين فحص تشخيصي فقط.

نميز مجموعات جميع الرؤوس دون إلزام التلوين الصحيح

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

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

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

نكتب C[A] للمجموعة عند A، ونطلب C[u]≠C[v] لكل u≠v. المقارنة تشمل غير المتجاورين والرؤوس من مكونات منفصلة؛ لا نضيف حواف جديدة عند المقارنة.

نضم لون الرأس وألوان حوافه فقط، دون ألوان الرؤوس المجاورة. نختبر مجموعات أسماء رمزية، لا مجاميع الأرقام ولا جداءها؛ الهدف عدد الألوان المستخدمة.

المسار يقبل مجموعات {1} و{1,2} و{2} بلونين

للمسار P3 الحافتان AB BC. نعطي A=1 وB=1 وC=2، والحافتين AB=1 وBC=2.

عند A، لون الرأس ولون حافته كلاهما 1، فتكون C[A]={1}. عند B، الرأس بلون 1 والحافتان بلونَي 1 و 2، فتكون C[B]={1,2}. عند C، الرأس والحافة بلون 2، فتكون C[C]={2}.

الأزواج AB وBC وAC لها مجموعات مختلفة، فينجح الشرط. لا يمنع نجاحه أن A وB متجاوران ولهما اللون نفسه، أو أن لون AB يساوي لون طرفه A ولون طرفه B.

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

لو سمحنا بلون واحد فقط، حمل كل رأس وحافة اللون 1، فتصير المجموعات الثلاث {1}. هذا يستبعد اللون الواحد، ومع الشاهد يثبت أن أقل لوحة للمسار لونان.

التلوين الصحيح للجميع يحتاج أربعة، والمجموعة قد تصغر بالتكرار

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

الشاهد الصحيح للمسار A=1 وB=2 وC=1 مع AB=3 وBC=4 يعطي {1,3} و{2,3,4} و{1,4}. الحصر السابق استبعد ثلاث ألوان وأثبت أن الأربعة هي الأقل لذلك النموذج.

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

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

في شاهد اللونين، درجة B هي 2، لكن مجموعته حجمها 2 لا 3، ومجموعة A حجمها 1 لا 2. لا ننقل مساواة الحجم بالدرجة زائد واحد من التلوين الصحيح إلى العام.

التبديل العام المتقابل لأسماء الألوان يحفظ تساوي مجموعتين أو اختلافهما، فيحفظ النجاح. تغيير بعض العناصر وحدها ليس إعادة تسمية عامة، وقد يغير المجموعات.

عدد المجموعات غير الفارغة قيد لازم، وليس شاهدًا للحل

كل مجموعة رأس غير فارغة لأنها تشمل لون الرأس نفسه. لوحة k ألوان لها 2^k مجموعات جزئية، منها مجموعة فارغة واحدة؛ يبقى 2^k-1 مجموعة غير فارغة.

إذا كان عدد الرؤوس n، فيجب أن يكون 2^k-1≥n حتى تتوافر مجموعات مختلفة لجميع الرؤوس. هذا قيد عددي لازم، لكنه لا يضمن إمكان تحقيق المجموعات بألوان الحواف والرؤوس.

لوحة لونين تعطي {1} و{2} و{1,2}. استعمل المسار المجموعات الثلاث لأن الرأسين ذوي المجموعتين المفردتين غير متجاورين.

في المثلث، لكي تختلف ثلاث مجموعات تحت لونين، يجب أن تكون هي تلك المجموعات الثلاث. لكن الرأس ذا المجموعة {1} والرأس ذا المجموعة {2} متجاوران؛ لون حافتهما يجب أن ينتمي إلى المجموعتين، وهذا مستحيل.

أي حافة بين u وv لها لون موجود في C[u] وفي C[v]، فتتقاطع مجموعتا طرفيها. لا يشترط أن تتقاطع مجموعتا رأسين غير متجاورين، كما يبين طرفا المسار.

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

حصر المسار يفرق بين كل التعيينات والتعيينات الصحيحة

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

عند لون واحد يوجد تعيين واحد ونمط واحد، ولا يميز الجميع. عند لونين يوجد 32 تعيينًا مسمى؛ يحسب الفحص عدد الناجح منها ويوافق عدد أنماطها.

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

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

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

المعزول قد يصطدم بمجموعة مفردة عند رأس له حافة

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

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

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

خذ الحافة AB والرأس C المعزول. نعطي A=1 وB=2 وC=1 مع AB=1، فتكون المجموعات {1} و{1,2} و{1}. يفشل الزوج AC رغم عدم وجود حافة بينهما.

نغير لون C وحده إلى 2، ونبقي A=1 وB=2 وAB=1؛ تصبح المجموعات {1} و{1,2} و{2} المختلفة جميعًا. إعادة استخدام لون B للمعزول تنجح هنا لأن مجموعة B ليست {2}.

إذن يجوز إعادة استخدام لون موجود إذا لم تتساوَ المجموعة المفردة للمعزول مع أي مجموعة أخرى. افحص المجموعات الفعلية، ولا تعتمد على وجود الحافة أو على لون الرأس وحده.

فحص مستقل يجرب الأسماء كلها دون استبعاد مخالفات الصحة

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

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

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

في النماذج جرب 153251 تعيينًا؛ 30730 يميز مجموعات الجيران و 9490 يميز الجميع. وفي رسوم الأربعة رؤوس جرب 343760؛ 79816 يميز الجيران و 51720 يميز الجميع. قبول الجميع هو الشرط المطلوب، لا قبول الجيران وحده.

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

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