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

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

التلوين الكامل للرؤوس صحيح عند طرفي كل حافة، ويحقق ظهور كل زوج من الألوان المستخدمة مرة واحدة على الأقل. العدد الأكروماتي هو أكبر عدد يحقق ذلك؛ تكرار الزوج مسموح. المسار A-B-C-D-E يحقق ثلاثة ولا يحقق أكثر، أما C4 فلا يحقق تلوينًا كاملًا بثلاثة، فيكون أكبر عدد له 2.

• التلوين العادي للرؤوس يختلف عند طرفي كل حافة. [2] وفي التلوين الكامل يظهر كل زوج من الألوان المستخدمة على حافة، والعدد الأكروماتي هو أكبر عدد من الألوان في تلوين صحيح كامل. [1] النموذج محدود وبسيط وغير موجه، بلا حلقات أو أوزان، ورؤوسه غير فارغة؛ نلون كل رأس مرة واحدة.
• نعد الألوان المستخدمة فقط، وكل فئة غير فارغة؛ إضافة اسم لون لا تحمله دائرة لا تكبر الجواب. الأزواج غير مرتبة، ويجوز تكرارها. فئات اللون مستقلة، وبين كل فئتين حافة واحدة على الأقل؛ كامل التلوين لا يعني أن الأصل رسم كامل.
• مع k ألوان يلزم k(k-1)/2 حافة على الأقل، وكذلك k لا يتجاوز عدد الرؤوس. لذلك P5 بأربع حواف لا يحقق أربعة ألوان كاملة، ويحقق ثلاثة بالتعيين 1 2 3 1 2: الأزواج 12 و 23 و 13 موجودة، و 12 يتكرر دون مشكلة. التناوب 1 2 1 2 1 كامل أيضًا لكنه لا يحقق الأكبر.
• في C4، أربعة ألوان تحتاج ست حواف وهي غير موجودة. وأي تلوين صحيح بثلاثة على الرؤوس الأربعة يكرر لون رأسين متقابلين، فيغيب زوج بين لوني الرأسين الآخرين. إذن الثلاثة مستحيلة، والتناوب 1 2 1 2 كامل باثنين، فيثبت أكبر عدد 2.
• كل تلوين عادي بأقل عدد يكون كاملًا: غياب زوج يسمح بدمج فئتيه ويقلل الألوان مع بقاء الاختلاف. لكن الكامل قد يستعمل أكثر من الأقل، كما أثبت المسار. يختلف السؤال عن المتناغم الذي يمنع تكرار الزوج ويبحث عن الأقل؛ P5 عادي 2، وكامل أقصى 3، ومتناغم أدنى 4.
• السداسية تحقق كاملًا بثلاثة بالتكرار 1 2 3 1 2 3؛ أربعة مستحيلة لأن الأزواج الستة كانت ستعطي كل لون ثلاث نهايات حواف، بينما رؤوس الدورة تضيفها زوجيًا. P4 والمثلث أكبرهما 3، والنجمة والحافتان المنفصلتان أكبرهما 2، والحافة مع رأسين معزولين أكبرها 2 أيضًا. الرؤوس المعزولة لا تضيف لونًا جديدًا بلا ظهور أزواجه. بلا حواف ومع رؤوس، الأكبر 1.
• حصرنا 64 رسمًا رباعيًا:960 تقسيمًا و 337 تلوينًا عاديًا و 129 كاملًا و 117 يحقق الأكبر؛ تجاوز الأكبر الأقل العادي في 12 مدخلًا. اتفق فحص الأزواج والفئات في 960 حالة، وراجع البحث المستقل الأكبر بتجربة 19065 تعيينًا كاملًا مسمى. التوزيع: رسم واحد أكبره 1، و 28 أكبرها 2، و 34 أكبرها 3، وواحد أكبره 4؛ P5 وC6 خارج الحصر.

الألوان المستخدمة كلها يجب أن تلتقي زوجيًا

التلوين العادي للرؤوس يعطي كل رأس لونًا مع اختلاف طرفي كل حافة. [2] ويكون التلوين كاملًا إذا ظهر كل زوج من الألوان على طرفي حافة؛ العدد الأكروماتي هو أكبر عدد من الألوان في تلوين صحيح كامل. [1]

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

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

زوج 1 و 2 هو زوج 2 و 1 نفسه. سنكتب 12 اختصارًا لهذا الزوج في القوائم، و 23 للزوج 2 و 3، وهكذا؛ لا نقصد لونًا اسمه اثنا عشر. في الصور نفصل رقمي الزوج بجانب كل خط، ولون الدائرة هو لون الرأس.

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

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

المسار يقبل ثلاثة كاملة رغم أن أقل تلوين له اثنان

المسار A-B-C-D-E له AB BC CD DE فقط. التناوب 1 2 1 2 1 يختلف عند طرفي كل حافة، ويستعمل لونين. يظهر الزوج الوحيد 12 على الحواف الأربع، فيكون التلوين كاملًا أيضًا.

هذا يثبت وجود تلوين كامل باثنين، لكنه لا يثبت أن اثنين أكبر عدد. جرب A باللون 1 وB باللون 2 وC باللون 3 وD باللون 1 وE باللون 2. الحواف بالترتيب تعطي 12 و 23 و 13 و 12.

كل حافة مختلفة عند طرفيها، والألوان المستخدمة 1 و 2 و 3 لها الأزواج الممكنة 12 و 13 و 23. كل زوج وجد حافة تمثله، فيكون الشاهد كاملًا بثلاثة؛ تكرار 12 على AB وDE مسموح.

لإثبات الأكبر، مع k ألوان مستخدمة توجد k(k-1)/2 أزواج مختلفة. كل حافة تمثل زوجًا واحدًا، ولا تستطيع أن تمثل زوجين مختلفين في التعيين نفسه. لذلك يتطلب الكامل هذا العدد من الحواف على الأقل.

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

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

اللوحتان الرئيسيتان تعرضان الأصل نفسه. اليسرى كاملة باثنين، واليمنى كاملة بثلاثة وتحقق الأكبر. لم نضف حافة بين A وC لتوفير الزوج 13؛ وجدناه بالفعل على CD من قائمة الأصل.

وجود حافة بين كل فئتين يكافئ ظهور الأزواج

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

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

في الشاهد الثلاثي للمسار، فئة 1 هي A وD، وفئة 2 هي B وE، وفئة 3 هي C. بين 1 و 2 توجد AB وDE، وبين 2 و 3 توجد BC، وبين 1 و 3 توجد CD. الحافتان بين الفئتين الأولى والثانية لا تفسدان القيد.

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

المسار ذو خمسة رؤوس يملك أقل عادي 2، وأكبر كامل 3، وأقل متناغم 4. للشاهد المتناغم نختار الرؤوس 1 2 3 1 4، فتظهر 12 و 23 و 13 و 14 دون تكرار؛ ثلاثة لا تكفيه لأن أربعة حواف تحتاج أربعة أزواج مختلفة.

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

الرباعية تفشل بثلاثة رغم نجاح حد الحواف

الرباعية على A B C D لها AB AD BC CD. ستة أزواج لازمة لأربعة ألوان، ولا تملك إلا أربع حواف، فيكون الأكبر على الأكثر 3. لكن وجود أربع حواف مقابل ثلاثة أزواج لا يثبت أن الثلاثة ممكنة.

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

إذا كان A وC باللون نفسه، كانت AB وBC تمثلان الزوج نفسه مع لون B، وكانت AD وCD تمثلان الزوج نفسه مع لون D. لونا B وD هما اللونان الآخران، لكن لا توجد BD؛ لا تظهر حافة بزوج لونيهما.

وإذا كان B وD باللون نفسه، انعكس الدور: الحواف تمثل زوج لونهما مع A أو C فقط، ولا توجد AC لتمثيل زوج اللونين الآخرين. في الحالتين يغيب زوج، فيستحيل التلوين الكامل بثلاثة.

الصورة الداخلية اليسرى تعرض محاولة صحيحة عاديًا بثلاثة: A1 B2 C3 D2. توجد الأزواج 12 و 23، ويغيب 13. الخطوط الأربعة كاملة؛ لا يرسم غياب الزوج حافة جديدة يمكن إضافتها إلى قائمة الأصل.

أعطِ A وC اللون 1 وB وD اللون 2، فتظهر 12 على كل حافة. الألوان المستخدمة اثنان وزوجهما الوحيد موجود، فيكون الشاهد كاملًا ويثبت الأكبر 2. الصورة اليمنى تعرضه على الرسم نفسه.

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

أقل تلوين عادي كامل، لكن الكامل قد يزيد عليه

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

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

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

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

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

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

السداسية والنجمة والمكونات المنفصلة

السداسية A-B-C-D-E-F-A لها AB AF BC CD DE EF. مع ست حواف، أربعة ألوان تعطي ستة أزواج بالضبط، وأكثر من أربعة يحتاج أكثر من ستة حواف. لو تحقق الكامل بأربعة، لظهر كل زوج مرة واحدة.

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

التعيين 1 2 3 1 2 3 على A B C D E F صحيح، وتظهر 12 و 13 و 23 مرتين لكل زوج. هو كامل بثلاثة وتثبت الأكبر 3، لكنه ليس متناغمًا بسبب التكرار. السداسية تحتاج خمسة متناغمة، في حين نزيد عدد الكامل هنا حتى ثلاثة فقط.

المسار A-B-C-D ذو ثلاث حواف يقبل 1 2 3 1، فتظهر الأزواج الثلاثة مرة واحدة. ثلاثة هي الأكبر لأن أربعة تحتاج ست حواف. والمثلث AB AC BC يقبل A1 B2 C3؛ الأكبر 3 لأن الرؤوس ثلاثة فقط.

في النجمة AB AC AD، لا توجد حواف بين الأوراق. مع ثلاثة ألوان مستخدمة أو أكثر يوجد لونان مختلفان على الأوراق، دون حافة بين فئتيهما؛ فيغيب زوجهما. أعطِ المركز 1 وكل الأوراق 2، فيكون التلوين كاملًا وتثبت الأكبر 2.

الحافتان المنفصلتان AB وCD تقبلان A1 B2 C1 D2؛ يظهر 12 مرتين، وهو الزوج الوحيد المطلوب. ثلاثة تحتاج ثلاثة أزواج لكن الحواف اثنتان، فيكون الأكبر 2. بخلاف المتناغم، تكرار الزوج بين المكونين مسموح.

مع AB وحدها ورأسين معزولين، نختار A1 B2 C1 D1 ونحقق الكامل باثنين. إعطاء رأس معزول لونًا جديدًا لا يوفر حافة لزوج ذلك اللون مع الألوان الأخرى، فلا يكبر العدد الكامل بهذه الإضافة.

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

الحصر يفصل أكبر تلوين عن عدد حلول الأكبر

ثبتنا A B C D والأزواج الممكنة AB AC AD BC BD CD. لكل حافة خيار إبقاء أو حذف، فحصرنا 2^6=64 رسمًا، مع إبقاء الرؤوس الأربعة حتى إذا انعزل بعضها.

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

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

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

حسب أكبر عدد كامل، هناك رسم واحد أكبره 1، و 28 أكبرها 2، و 34 أكبرها 3، ورسم واحد أكبره 4. المجموع 64، وهي قوائم على أسماء ثابتة؛ لم نوحد الرسوم حتى إعادة تسمية الرؤوس.

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

التقسيمات 960 توحد أسماء الألوان، أما 19065 فعد لتعيينات كاملة مسماة جربها بحث تنازلي. ليست عقد بحث جزئية، ولا نقارن العددين بوصفهما عدًا للشيء نفسه.

النماذج والحسابات حفظت قبل البحث في المراجع، والشواهد والصور من قوائمنا دون ادعاء اختراع المفهوم أو الأمثلة المعروفة. P5 بخمسة رؤوس وC6 بستة مثالان خارج الحصر الرباعي. براهين حدود الأزواج والرباعية والدمج والسداسية منفصلة عن الحصر؛ لا نستنتج صيغة عامة أو ضمان سرعة من هذه الأعداد.