التلوين النجمي للرؤوس: لماذا تحتاج C4 ثلاثة ألوان؟

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

لأن التناوب 1 2 1 2 في C4 صحيح على الحواف، لكنه يخالف شرط أن يستخدم كل مسار من أربعة رؤوس ثلاثة ألوان على الأقل. الشاهد A1 B2 C1 D3 ينجح بأقل 3؛ وإغلاق الدورة بالحافة AD لا يلغي المسار A B C D.

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

أربعة رؤوس مختلفة، لا أربع حواف

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

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

نطلب اختلاف لون طرفي كل حافة أصلية، ثم نفحص كل مسار A B C D على أربعة رؤوس مختلفة: AB و BC و CD حواف، ولا يجوز أن يحمل الرؤوس الأربعة لونين فقط. الصحة تمنع لونًا واحدًا عليه، فيلزم ثلاثة ألوان أو أربعة.

وجود AD أو AC أو BD لا يحذف المسار. لا نطلب أن يكون الرسم على الرؤوس الأربعة مسارًا مستحثًا بلا حواف إضافية؛ نطلب وجود الحواف الثلاث المتتابعة فقط.

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

C4: لماذا يفشل التناوب الصحيح؟

ثبت A B C D والحواف AB AD BC CD. التعيين A1 B2 C1 D2 صحيح: كل حافة تصل لونين مختلفين. لكنه يجعل المسار A B C D بلونين فقط، فيفشل نجميًا.

أي تلوين صحيح بلونين في C4 يفرض هذا التناوب، بعد تبديل أسماء الألوان. إذا كان A بلون 1، وجب أن يكون B و D بلون 2، وأن يكون C بلون 1. لذلك لا يكفي لونان، واللون الواحد ممنوع أصلًا بالحواف.

اختر A1 B2 C1 D3. كل حافة تصل لونين مختلفين؛ وكل مسار رباعي في هذا الرسم يستخدم الرؤوس الأربعة جميعًا، ويحوي الألوان 1 و 2 و 3. إذن ينجح بثلاثة، فيثبت الأقل 3 مقابل 2 عاديًا.

A و C يحملان 1 وبينهما مسافة 2، وهذا لا يفسد الحل. لا نفرض اختلاف كل زوج رؤوس يشتركان في جار، ولا تلوين مربع الرسم. القيد على المسار كله مع الصحة، لا على كل زوج عند المسافة 2.

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

النجمة تقبل أوراقًا بلون واحد

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

خذ نجمة مركزها A وأوراقها B و C و D، وحوافها AB AC AD فقط. أعط المركز 1 والأوراق 2. كل حافة صحيحة، ولا يوجد مسار على أربعة رؤوس مختلفة: من ورقة إلى أخرى نمر بالمركز، ثم يتوقف المسار قبل تكراره.

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

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

P4 يفرض الثالث، والمساران الأطول يقبلانه

على P4 بحواف AB BC CD، يفشل التناوب 1 2 1 2 بسبب المسار الوحيد على الرؤوس الأربعة. كل تلوين صحيح بلونين فيه يفرض التناوب، لذلك لا يكفي 2؛ واللون الواحد ممنوع بحواف الرسم.

الشاهد 1 2 1 3 صحيح ونجمي، فيثبت الأقل 3. اتفاق A و C ليس إخفاقًا: المسار كله يحوي ثلاثة ألوان. لا نستنتج فشل تعيين من وجود رأسين متماثلي اللون وحده.

P5 يقبل 1 2 1 3 1. النافذتان الرباعيتان على المسار هما 1 2 1 3 و 2 1 3 1؛ كلتاهما بثلاثة ألوان، وكل حافة صحيحة. P6 يقبل 1 2 1 3 1 2؛ النافذة الإضافية 1 3 1 2 تحوي ثلاثة ألوان كذلك.

في كل مسار خطي، كل مسار من أربعة رؤوس هو أربعة رؤوس متتابعة، أو ترتيبها المعكوس. لذلك يكفي فحص هذه النوافذ، مع فحص الحواف. P5 و P6 يحتويان P4، فيرثان استحالة اللونين، والشواهد تحقق 3؛ الأقل 3 في الثلاثة.

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

C5 تحتاج الرابع، و C6 تكتفي بثلاثة

في C5 على A B C D E والحواف AB BC CD DE EA، كل فئة لون في تلوين صحيح مستقلة. لا تتسع فئة لأكثر من رأسين: اختيار ثلاثة رؤوس في دورة بخمسة يجعل اثنين منها متجاورين.

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

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

الشاهد A1 B2 C1 D3 E4 صحيح؛ لا يتكرر فيه سوى اللون 1. لكي يحمل مسار صحيح رباعي لونين فقط، لا بد أن يتناوبا مرتين لكل منهما. هنا لا يوجد لون ثانٍ مكرر، فلا يظهر هذا النمط. ينجح الشاهد بأربعة، فيثبت الأقل 4.

في C6، اختر 1 2 3 1 2 3 على A B C D E F. الحواف صحيحة بما فيها FA، وكل نافذة من أربعة رؤوس حول الدورة تحوي ثلاثة ألوان، حتى عند عبور موضع الإغلاق. إذن ينجح بثلاثة.

أي تلوين صحيح بلونين في C6 يفرض التناوب، فيخالف أي مسار رباعي منها؛ فيثبت الأقل 3. لا تقارن دورتي 5 و 6 بمجرد عدد الرؤوس: القيود والشاهد والحد الأدنى تحسم العدد.

الماسة وثلاثة الألوان: شواهد للمقارنة

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

الماسة بحواف AB AC AD BC BD تقبل A2 B3 C1 D1. كل حافة صحيحة؛ C و D غير متجاورين فيحملان 1. كل مسار رباعي فيها يستخدم الجميع وثلاثة ألوان، فينجح نجميًا. وجود المثلث ABC يفرض 3 عاديًا، فيثبت الأقل 3 نجميًا كذلك.

الحافتان المنفصلتان AB و CD تقبلان 1 2 1 2، وحافة AB مع معزولين C و D تقبل 1 2 1 1. لا يوجد مسار رباعي فيهما، والحافة تفرض لونين، فيثبت الأقل 2. الرسم بلا حواف يقبل 1 للجميع، بأقل 1 لأن رؤوسه غير فارغة.

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

C5 و C6 و P5 و P6 ونجمة الخمس والمثلث أمثلة خارج الحصر الرباعي التالي. فحوصها لا تحول نتيجة 64 رسمًا إلى قاعدة لكل رسم؛ C5 نفسها تمنع تعميم حد 3.

خمسة عشر رسمًا رباعيًا يزيد فيها العدد

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

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

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

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

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

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

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