تلوين الحواف اللادوري: لماذا تحتاج الدورة لونًا ثالثًا؟

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

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

• تلوين الحواف اللادوري تلوين صحيح لا توجد فيه دورة بلونين؛ وعدده اللوني هو أقل عدد من الألوان الذي يحقق هذا الشرط. [1] نفترض رسمًا محدودًا وبسيطًا وغير موجه، بلا حلقات أو أوزان وبقائمة رؤوس غير فارغة؛ نلون كل حافة مرة، وتبقى قائمة الأصل ثابتة.
• التلوين الصحيح للحواف يعطي الحافتين المتلاقيتين عند رأس لونين مختلفين، ويبحث عن أقل عدد من الألوان. [2] نراجع كل دورة، لا مجرد وجود ثلاثة ألوان في الرسم كله. الدورة الثلاثية تحتاج ثلاثة ألوان أصلًا؛ الدورة المحظورة في التلوين الصحيح تتناوب بين لونين ويكون طولها زوجيًا.
• في C4 بحواف AB AD BC CD، الفئتان AB CD وAD BC تحققان لونين عاديين، لكن اتحادهما دورة. أعطِ CD لونًا ثالثًا مع إبقاء AB باللون 1 وAD وBC باللون 2؛ يبقى الرسم دورة، لكن أقل الألوان اللادورية 3.
• يكافئ منع الدورة الثنائية أن يكون اتحاد كل فئتي لون خاليًا من الدورات. نحفظ حواف هذين اللونين فقط، لا كل الحواف الأصلية بين أطرافهما. الفئة الواحدة مطابقة، واتحاد اثنتين قد يكون مسارًا مقبولًا؛ لا نطلب أن يكون مطابقة.
• المسار AB BC CD يقبل اللونين 1 2 1 لادوريًا رغم وجود BC بين أطراف AB CD؛ لذلك يختلف الشرط عن التلوين القوي الذي يحتاج 3 هناك. كل تلوين صحيح على رسم بلا دورات لادوري، والمعزول لا يغيره، والرسم بلا حواف يحتاج 0 ألوان وتعيينًا فارغًا واحدًا.
• في C6 يكفي تغيير EF إلى لون ثالث في التناوب العادي، فيثبت الأقل اللادوري 3 مقابل العادي 2. المثلث والنجمة يحتاجان 3 في الحالين. الكامل على أربعة يحتاج 3 عادية و 5 لادورية: فئتان من حافتين كانتا ستكوّنان دورة ثنائية اللون، وخمسة ألوان تحقق شاهدًا صالحًا.
• راجعنا 64 قائمة حواف و 877 تقسيمًا بعد توحيد أسماء الألوان؛125 عادية و 112 لادورية. بلغ مجموع التقسيمات الدنيا 64 للعادي و 75 للادوري، واختلف الأقلان في 10 مدخلات. اتفق فحص الدورات وفحص اتحادات اللونين 877 مرة، وراجعنا الأقلين بتعيينات مسماة مستقلة؛ الأعداد محدودة وليست صيغة عامة أو ادعاء سرعة.

اللا دورية تخص ألوان الدورة، لا حذفها من الأصل

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

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

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

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

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

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

الدورة الرباعية تمنع الاكتفاء بلونين

التلوين الصحيح للحواف يعطي الحافتين المتلاقيتين عند رأس لونين مختلفين، ويبحث عن أقل عدد من الألوان. [2]

لدينا A B C D وحواف AB وAD وBC وCD، أي الدورة A-B-C-D-A. أعطِ AB وCD اللون 1، وAD وBC اللون 2. عند كل رأس لونان مختلفان، فيكون التلوين صحيحًا عاديًا.

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

ولا يوجد تلوين صحيح آخر بلونين يتجنب المشكلة: لون AB يفرض اختلاف BC، ثم اختلاف CD عن BC، ثم اختلاف AD عن CD وAB. مع لونين فقط يلزم التناوب نفسه، حتى لو بدلنا أسماء اللونين.

أعطِ الآن CD اللون 3، وأبقِ AB باللون 1 وAD وBC باللون 2. عند C نجد 2 و 3، وعند D نجد 2 و 3، وعند A وB نجد 1 و 2. لا تكرار عند رأس، والدورة الوحيدة تستعمل 1 و 2 و 3.

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

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

اجمع لونين واطلب غابة، لا مطابقة مستحثة

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

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

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

اللا دورية لا تطلب أن يكون اتحاد اللونين مطابقة. في اللوحة اليمنى للرباعية، اتحاد اللونين 1 و 2 هو AD وAB وBC، وهو المسار D-A-B-C. يلتقي فيه لونان مختلفان عند بعض الرؤوس، ولا توجد فيه دورة.

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

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

المسار المفتوح بلونين ينجح دون الشرط القوي

المسار A-B-C-D ذو AB BC CD يقبل التعيين 1 2 1. عند B وC لونان مختلفان، ولا توجد أي دورة أصلًا. اتحاد اللونين هو المسار كله، فيظل غابة، ويكون أقل العادي واللادوري 2.

لكن فئة اللون 1، أي AB CD، ليست مطابقة مستحثة، لأن BC تصل بين أطرافها في الأصل. لذلك يفشل التلوين القوي بهذا التعيين، رغم نجاح اللادوري؛ القوي في هذا المسار يحتاج ثلاثة ألوان.

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

على أي رسم أصلي بلا دورات، يبقى كل اتحاد جزئي للحواف بلا دورات أيضًا. لذلك كل تلوين صحيح لهذا الرسم لادوري، ويتساوى أقل العددين. لا يعني ذلك أن لونًا واحدًا يكفي؛ النجمة AB AC AD تحتاج ثلاثة لأن حوافها تتلاقى كلها عند A.

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

اللون الثالث يكسر الثنائية في الدورة السداسية

الدورة A-B-C-D-E-F-A لها AB AF BC CD DE EF. للتلوين العادي نعطي AB وCD وEF اللون 1، وAF وBC وDE اللون 2. تتناوب الألوان حول الدورة، فيكفي 2، لكن الدورة نفسها ثنائية اللون.

غير EF وحدها إلى اللون 3، وأبقِ الحواف الخمس الأخرى كما هي. عند E أصبحت DE بلون 2 وEF بلون 3، وعند F أصبحت AF بلون 2 وEF بلون 3. بقية الرؤوس لم تتغير، فلا يتكرر لون عند رأس.

الدورة الأصلية لها ست حواف وتستعمل الآن الألوان 1 و 2 و 3. وهي الدورة الوحيدة في هذا الرسم، لذلك لا توجد دورة ثنائية اللون. يمكن أيضًا فحص اتحاد كل زوج من الألوان؛ سيفقد حافة على الأقل من الدورة، ولا يغلق مسارًا جديدًا.

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

في المثلث AB AC BC، كل حافتين تتلاقيان، فيلزم 3 عادية وتتحقق بثلاثة ألوان مختلفة. الدورة الثلاثية تستعملها كلها، فتكون لادورية أيضًا؛ وجود دورة في الرسم لا يوجب زيادة عدد الألوان فوق العادي دائمًا.

الكامل على أربعة يمنع أربع فئات أو أقل

الكامل على A B C D له AB AC AD BC BD CD. للتلوين العادي تكفي الفئات AB CD، وAC BD، وAD BC. كل منها مطابقة، ودرجة كل رأس 3 تمنع أقل من 3، فيكون العدد العادي الأقل 3.

في أي تلوين صحيح على أربعة رؤوس، حجم فئة اللون لا يتجاوز حافتين، لأن أطرافها مستقلة. إذا وزعنا الحواف الست على أربعة ألوان أو أقل، فلابد من فئتين على الأقل بحافتين؛ وإلا لم نتجاوز 2+1+1+1=5 حواف.

كل فئة من حافتين تغطي الرؤوس الأربعة، وتكون إحدى المطابقات الكاملة AB CD أوAC BD أوAD BC. أي اثنتين مختلفتين منها يجتمعان في دورة رباعية، بألوان الفئتين وحدهما. لذلك لا يمكن تلوين الكامل لادوريًا بأربعة ألوان أو أقل.

خمسة ألوان تكفي: AB وCD باللون 1، وAC باللون 2، وAD باللون 3، وBC باللون 4، وBD باللون 5. الفئة الأولى مطابقة، وبقية الفئات منفردة، فيبقى التلوين صحيحًا. الصورة الداخلية تعرض هذا الشاهد كاملًا.

كل اتحاد لفئتين فيه حافتان على الأكثر إذا كانتا منفردتين، أو ثلاث حواف إذا ضم الفئة الأولى. لا تكفي هذه الحواف لدورة بطول 4 أو أكثر، ولا يمكن أن تكون دورة ثلاثية بلونين في تلوين صحيح. إذن كل اتحاد غابة، والشاهد لادوري.

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

حصر مستقل للدورات واتحادات اللونين

ثبتنا A B C D وأخذنا كل واحدة من 2^6=64 قائمة حواف بسيطة غير موجهة. لكل مدخل حصرنا تقسيمات حوافه إلى فئات غير فارغة، ووحدنا أسماء الألوان حسب أول ظهور في قائمة مرتبة.

فالتعيين 1 2 1 للمسار والتعيين 2 1 2 يصفان الفئتين نفسيهما بعد تبديل الأسماء. لا نعد إعادة التسمية تقسيمًا جديدًا. بلغ مجموع المرشحات 877، واجتاز التلوين الصحيح 125 تقسيمًا، واللادوري 112.

فحصنا اللا دورية بطريقتين مستقلتين: حصر الدورات البسيطة واختبار عدد ألوان كل منها، ثم اتحاد كل فئتي لون واختبار الغابة بوصل المكونات ورفض حافة تغلق دورة. تحقق شرط التلوين الصحيح أولًا في الطريقتين، واتفق الحكم في 877 مرشحًا.

بلغ مجموع التقسيمات التي تحقق أقل عدد عادي 64، والتي تحقق أقل عدد لادوري 75. هذه مجاميع عبر المدخلات، وليست عدد الألوان نفسه. اختلف أقل العددين في 10 مدخلات؛ يتساويان في المدخلات الأخرى رغم اختلاف مجموع الحلول الدنيا.

راجعنا الأقل بطريقة أخرى تعطي الحواف ألوانًا مسماة وتجرب الأعداد تصاعديًا حتى تجد تعيينًا صالحًا. بلغ مرشحوها 4143 للعادي و 30251 للادوري، واتفق الأقل مع حصر التقسيمات في 64 مدخلًا. لا نقارن هذه التعيينات بوصفها 877 تقسيمًا؛ أسماء الألوان وطريقة التجربة مختلفتان.

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

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