التلوين اللادوري للرؤوس: لماذا ينجح المسار ويفشل إغلاقه؟

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

لأن التلوين اللادوري يسمح بمسار بلونين، ويمنع دورة بلونين. على A B C D، التناوب 1 2 1 2 ينجح في P4 بأقل 2؛ إضافة AD تغلقه إلى C4 وتفسد الشاهد، والتعيين 1 2 1 3 يصلح الدورة بأقل 3.

• التلوين اللادوري للرؤوس تلوين صحيح يكون فيه الرسم المستحث بكل زوج فئات لونية غابة، أي مكونات من أشجار. [1] نلون جميع رؤوس رسم محدود وبسيط وغير موجه وغير فارغ الرؤوس؛ ونستخدم أسماء ألوان حرة ونبحث عن أقل عدد مستعمل. الشرط على كل زوج ألوان، لا كل لون وحده. نمنع دورة بسيطة بأي طول، لا الرباعية فقط؛ الحواف الإضافية لا تلغي الدورة. نلون المعزول أيضًا؛ الخالي يحتاج 1 لا 0، وتبديل أسماء الألوان يحفظ الحل.
• التلوين الصحيح العادي يفرض اختلاف لون طرفي كل حافة، ويبحث عن أقل عدد ألوان. [2] نحتفظ بالصحة ونمنع أيضًا كل دورة ذات لونين؛ المسارات ذات اللونين قد تنجح. في P4 بحواف AB BC CD ينجح 1 2 1 2 بأقل 2 لأنه بلا دورات وتوجد حافة. أضف AD؛ يفشل الشاهد على C4 بسبب الدورة كلها بلونين. أي حل صحيح بلونين فيها يفرض التناوب؛ 1 2 1 3 ينجح بأقل 3 لأن دورتها الوحيدة تحوي ثلاثة ألوان.
• العدد اللادوري هو أقل عدد ألوان يحقق الشرط؛ والنجمي أشد، إذ يفرض نجومًا في كل زوج ألوان، أو ثلاثة ألوان على الأقل لكل مسار رباعي. [3] الغابة قد تحتوي مسارًا طويلًا لا يكون نجمة. P4 يقبل لونين لادوريًا لكنه يحتاج 3 نجميًا. وكل نجمي لادوري، وكل لادوري صحيح؛ لذلك الأقل العادي لا يزيد على الأقل اللادوري، وهذا لا يزيد على الأقل النجمي. تتساوى الصحة واللادورية في الغابة؛ مع حافة يكفي 2 بتناوب مستويات كل شجرة، وبدون حواف يكفي 1. P4 يقبل نجميًا 1 2 1 3، واللونان يفرضان التناوب المرفوض للمسار الرباعي.
• C6 لا تحوي دورة رباعية، لكنها ترفض 1 2 1 2 1 2 لدورتها ذات الستة رؤوس. الشاهد 1 2 1 2 1 3 صحيح ولادوري بأقل 3، لأن الدورة الوحيدة بثلاثة ألوان واللونين يفرضان تناوبًا مرفوضًا. لكنه يفشل نجميًا عبر A B C D بلونين؛ شاهد نجمي آخر 1 2 3 1 2 3 ينجح بثلاثة. C5 تقبل 1 2 1 2 3 لادوريًا بأقل 3، مقابل 4 نجميًا؛ فاللونان يفشلان للصحة في الدورة الفردية. لاستبعاد 3 نجميًا في C5: فئاتها الصحيحة بحجوم 2 و 2 و 1، وحذف فئة الرأس الوحيد يترك P4 بلونين؛1 2 1 3 4 ينجح.
• لا تكفي استقلالية كل فئة لون؛ C4 المتناوبة فئتاها مستقلتان لكن اجتماعهما يحمل الدورة. نفحص الحواف كلها، ثم كل زوج ألوان: إذا أعادت حافة وصل رأسين متصلين بالفعل في ذلك الزوج، اكتشفت دورة. لا نطلب نجمة لكل مكون. K2,3 تقبل 1 2 3 3 3 بأقل 3، و K3,3 تقبل 1 2 3 4 4 4 بأقل 4. في K_p,q حيث p و q حجما الجانبين وموجبان، الأقل min(p,q)+1: إن تكرر لون على كل جانب ظهرت دورة رباعية، فلا بد أن تستعمل رؤوس أحد الجانبين ألوانًا مختلفة؛ نحقق الحد بتفريد الجانب الأصغر ولون واحد للآخر.
• المثلث والماسة يحتاجان 3، و K4 يحتاج 4؛ شواهد 1 2 3 و 2 3 1 1 و 1 2 3 4 تحقق الصحة واللادورية. النجمتان بثلاث وخمس أوراق، و P5 و P6، تحتاج 2 لأنها أشجار ذات حواف؛ الحافتان المنفصلتان وحافة مع معزولين تحتاجان 2، والخالي 1. نثبت الأقل بشاهد واستبعاد كل عدد أصغر، ونميز صلاحية شاهد لادوري من صلاحيته النجميّة؛ العددان قد يتساويان رغم اختلاف الشواهد كما في C6. P5 يقبل نجميًا 1 2 1 3 1، وP6 يقبل 1 2 1 3 1 2، بأقل 3 بفضل مسار P4؛ K2,3 وK3,3 بالشاهدين السابقين نجميان أيضًا لأن كل زوج ألوان نجوم.
• حصر 64 رسمًا رباعيًا أعطى 960 تقسيمًا بعد تجاهل إعادة أسماء الألوان: 337 صحيحًا، و 334 لادوريًا، و 322 نجميًا. بحث الأقل جرب 1048 تعيينًا كاملًا؛ التوزيع 1 في رسم، و 2 في 37، و 3 في 25، و 4 في رسم. زاد اللادوري عن العادي في ثلاث C4 مسماة: 24/8=3 بأربع بدايات واتجاهين؛ وقل عن النجمي في اثني عشر P4: 24/2=12 باتجاهين. على أربعة رؤوس، الثلاثة ألوان الصحيحة تمنع أي دورة بلونين، ولا توجد دورة ثنائية إلا C4. فحص آخر لكل زوج ألوان بكشف اتصال الرؤوس اتفق مع تعداد كل الدورات في 16 مثالًا و 64 رسمًا والقوائم الكاملة للأقل؛ راجع رأسًا واحدًا ورأسين، ومولد التقسيمات مشترك. الأعداد ليست أزمنة تنفيذ، ولا نعمم حد 3، فـ K3,3 خارج الحصر تحتاج 4.

غابة لكل زوج ألوان، مع بقاء صحة الحواف

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

التلوين الصحيح العادي يفرض اختلاف لون طرفي كل حافة، ويبحث عن أقل عدد ألوان. [2] نحتفظ بالصحة ونمنع أيضًا كل دورة ذات لونين؛ المسارات ذات اللونين قد تنجح.

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

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

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

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

إضافة AD تنقل P4 من نجاح اللونين إلى إخفاقهما

ثبت A B C D وحواف P4 وهي AB BC CD. اختر A1 B2 C1 D2؛ كل حافة تصل لونين مختلفين، ولا توجد دورة أصلًا. إذن الشاهد لادوري، والأقل 2 لأن وجود حافة يمنع اللون الواحد.

أضف AD مع إبقاء الرؤوس والشاهد، فيصبح الرسم C4 بحواف AB AD BC CD. ظلت كل حافة صحيحة، لكن الدورة A B C D A تحمل اللونين 1 و 2 فقط؛ فيفشل الشاهد لادوريًا.

كل تلوين صحيح بلونين في C4 يفرض التناوب: بعد اختيار A1، يلزم B2 و D2، ثم C1. لذلك لا ينجح أي حل بلونين، واللون الواحد ممنوع بالحواف أيضًا.

اختر A1 B2 C1 D3. الحواف صحيحة، والدورة البسيطة الوحيدة في C4 تحوي ثلاثة ألوان. ينجح الشاهد بثلاثة، فيثبت الأقل 3. الدورات بالاتجاه المعاكس أو بداية مختلفة هي الدورة نفسها، ولا تغير الحكم.

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

C6 ترفض اللونين رغم غياب دورة رباعية

خذ C6 على A B C D E F، والحواف AB BC CD DE EF FA فقط. التعيين 1 2 1 2 1 2 صحيح، لكنه يجعل الدورة ذات الستة رؤوس بلونين، فيفشل لادوريًا.

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

اختر A1 B2 C1 D2 E1 F3. كل حافة صحيحة، بما فيها EF و FA؛ والدورة الوحيدة تحوي الألوان 1 و 2 و 3. ينجح لادوريًا بأقل 3، لأن أي تلوين صحيح بلونين يفرض التناوب المرفوض، واللون الواحد مستحيل.

في زوج اللونين 1 و 2، حذف F من مجموعة الرؤوس يترك المسار A B C D E؛ غابة مقبولة رغم طوله. وفي زوج 1 و 3، نرى الحافتين FA و FE ومركزهما F، ومعزولًا C. أما زوج 2 و 3 فليس فيه حافة. كل زوج غابة.

الصورة الداخلية تبقي الحواف الست في الجانبين، وتغير F من 2 إلى 3. لا نحتاج منع المسار A B C D ذي اللونين كي نحقق اللادورية؛ هذا شرط آخر أشد، نميز بينه وبين سؤالنا.

الفئة المستقلة لا تكفي، والغابة ليست دائمًا نجمة

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

في C4 المتناوبة، فئة اللون 1 هي A و C، وفئة 2 هي B و D؛ لا حافة داخل أي فئة. ومع ذلك اجتماعهما يحمل دورة. استقلالية كل فئة تحقق الصحة فقط، ولا تكفي لمنع دورة بلونين.

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

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

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

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

K3,3 تحتاج أربعة رغم أن لونين يكفيان عاديًا

في K2,3، الجانب الأول A و B، والآخر C و D و E. كل رأس في الأول متصل بكل رأس في الآخر، ولا حافة داخل الجانب نفسه. الشاهد A1 B2 C3 D3 E3 صحيح، وفي كل زوج ألوان توجد نجمة أو معزول؛ فينجح لادوريًا بثلاثة.

لو استعملنا لونين، فالصحة تضع الأول كله بلون والثاني كله بالآخر؛ اختيار A و B ورأسين من الجانب الآخر يعطي دورة رباعية بلونين. إذن 2 مستحيلة و 1 أيضًا، فيثبت الأقل 3.

في K3,3، الجانب A B C والجانب D E F. الشاهد 1 2 3 4 4 4 صحيح؛ كل زوج يضم 4 وأحد 1 أو 2 أو 3 يعطي نجمة بثلاث أوراق، وأزواج الألوان بين 1 و 2 و 3 بلا حواف. ينجح بأربعة.

لإثبات الحد الأدنى، في أي تلوين صحيح لـ K_p,q حيث p و q حجما الجانبين وموجبان، لا يستعمل أي لون على الجانبين معًا لأن كل زوج من جانبين متجاور. إذا تكرر لون عند رأسين في الأول، وتكرر لون آخر عند رأسين في الثاني، ظهرت بينهما دورة رباعية بلونين.

إذن لا بد أن يكون أحد الجانبين بلا أي لون مكرر: لكل رأس فيه لون مختلف. يلزم لهذا الجانب عدد ألوان يساوي حجمه، ويلزم للآخر لون واحد على الأقل لا يستعمل فيه. لذلك العدد لا يقل عن min(p,q)+1.

نحقق هذا الحد بإعطاء رؤوس الجانب الأصغر ألوانًا مختلفة، وكل الجانب الآخر لونًا جديدًا واحدًا. كل زوج ألوان إما بلا حواف أو نجمة، فلا دورة. الأقل min(p,q)+1 عمومًا؛ يعطي 3 لـ K2,3 و 4 لـ K3,3. لا نقول إن 3 تكفي في كل رسم. البناء نفسه نجمي أيضًا، لأن كل مكون في كل زوج ألوان نجمة أو رأس منفرد؛ والنجمي لا يقل عن اللادوري، فيتساوى الأقلان في K2,3 وK3,3. ليست هذه مساواة عامة لكل رسم.

C5 تقبل ثلاثة، والماسة تحافظ على الحد نفسه

C5 بحواف AB BC CD DE EA تقبل 1 2 1 2 3؛ كل حافة صحيحة، والدورة الوحيدة فيها تحوي ثلاثة ألوان. أي تلوين بلونين لدورة فردية يفشل للصحة عند الإغلاق، فيثبت الأقل 3 لادوريًا. العدد النجمي هنا 4، لكننا لا نستبدل منع الدورة بمنع المسار الرباعي. لإثبات العدد النجمي 4: في تلوين صحيح بثلاثة ألوان، أحجام الفئات 2 و 2 و 1 لأن أكبر مجموعة مستقلة حجمها 2. حذف الرأس الوحيد في لونه يترك مسارًا رباعيًا بلونين، فيفشل نجميًا. الشاهد 1 2 1 3 4 صحيح ونجمي لأنه لا يتكرر فيه سوى لون واحد، بينما المسار الرباعي الصحيح بلونين يكرر كليهما.

المثلث بحواف AB AC BC يحتاج 3 بحكم الصحة، ويقبل 1 2 3 لادوريًا؛ دورته ذات ثلاثة ألوان. K4 يحتاج 4 لأن كل زوج رؤوس متجاور، وتعيين أربعة ألوان مختلفة يمنع أي دورة بلونين؛ الأقل 4.

الماسة بحواف AB AC AD BC BD تقبل A2 B3 C1 D1. صحتها محفوظة، والمثلث ABC يفرض 3. لا يمكن أن تحمل دورة بلونين في هذا الشاهد: الدورة الثنائية الصحيحة طولها زوجي 4 على هذه الرؤوس، فتستعمل الجميع الذين يحملون ثلاثة ألوان؛ يثبت الأقل 3.

P5 يقبل 1 2 1 2 1، و P6 يقبل 1 2 1 2 1 2، بأقل 2. النجمتان بثلاث وخمس أوراق تقبلان المركز 1 وكل الأوراق 2 بأقل 2. هذه أشجار ذات حواف، فالصحة بلونين تكفي للادورية، ولو تشابهت ألوان الجيران أو امتد مسار بلونين. نجميًا، P5 يقبل 1 2 1 3 1، وP6 يقبل 1 2 1 3 1 2؛ كل نافذة رباعية فيها ثلاثة ألوان، ويحتويان P4 الذي يمنع اللونين، فيثبت الأقل 3. النجمتان تقبلان الشاهد ذي اللونين نجميًا أيضًا لغياب مسار رباعي.

الحافتان المنفصلتان AB و CD تقبلان 1 2 1 2، وحافة AB مع معزولين C و D تقبل 1 2 1 1، بأقل 2. الخالي من الحواف يقبل 1 للجميع بأقل 1؛ المعزول لا يحذف من الرؤوس الملونة.

نثبت الأقل بشاهد يحقق الصحة واللادورية، ثم نستبعد كل عدد أصغر. لا يكفي إخفاق شاهد بعينه لرفض عدد الألوان كله، إلا مع برهان يفرض شكله أو يبين أن كل احتمال آخر يخالف. C5 و C6 و K2,3 و K3,3 والمسارات الطويلة والمثلث ونجمة الخمس خارج الحصر الرباعي التالي.

ثلاث دورات فقط تزيد العدد على أربعة رؤوس

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

نجح 337 تقسيمًا للصحة، و 334 للادورية، و 322 للنجميّة. بحث للأقل بزيادة عدد الألوان جرب 1048 تعيينًا كاملًا حتى أول نجاح في كل رسم؛ توزيع الأقل اللادوري 1 في رسم، و 2 في 37، و 3 في 25، و 4 في رسم واحد. لا تعني هذه الأعداد أزمنة تنفيذ أو حجم كل شجرة بحث.

زاد اللادوري عن العادي في ثلاث C4 مسماة؛ تعداد ترتيب الرؤوس يعطي 24، لكن الدورة تعد بأربع بدايات واتجاهين، فينتج 24/8=3. وقل اللادوري عن النجمي في اثني عشر P4 مسمى؛ المسار يعد باتجاهين، فينتج 24/2=12.

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

والفرق عن النجمي يظهر في P4: مساره الرباعي بلونين مقبول لادوريًا ما دام لا توجد الدورة. إضافة الحافة بين الطرفين تعطي C4، فترفض اللادورية اللونين كذلك. لا نعمم من هذا الحصر حد 3؛ K3,3 خارج الأربعة يحتاج 4 كما أثبتنا.

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

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