نصف الجيران يكفي: لماذا يقبل المثلث لونين؟

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

لأن الشرط يسمح بتساوي عدد الجيران الموافقين للون الرأس والمختلفين عنه. في المثلث AB AC BC، التعيين A1 B1 C2 ينجح: عند A و B جار موافق من أصل اثنين، وعند C لا جار موافق؛ الأقل 2 رغم اتفاق طرفي AB.

• في تلوين الأغلبية، لا يزيد عدد جيران أي رأس الذين يحملون لونه هو على نصف عدد جيرانه. ونبحث عن أقل عدد ألوان يحقق ذلك. [1] ندرس رسمًا محدودًا وبسيطًا وغير موجه، بلا حلقات أو أوزان، ورؤوسه غير فارغة وملونة كلها.
• التلوين الصحيح العادي يشترط اختلاف لون طرفي كل حافة، ويبحث عن أقل عدد ألوان. [2] شرط الأغلبية أضعف: قد تتفق ألوان طرفي حافة، ما دام كل رأس يحقق حد النصف في جواره. نكتب الشرط 2s≤d، حيث s عدد الجيران بلون الرأس نفسه و d درجته. لا نحسب الرأس ضمن جيرانه، ولا نختبر كل لون آخر. التعادل مقبول؛ رأس درجته 1 يحتاج اختلاف جاره، والمعزول يحقق 0≤0 لكنه يبقى ملونًا.
• المثلث AB AC BC يرفض 1 للجميع لأن كل رأس يوافقه جاراه، ويقبل 1 1 2 بأقل 2 مقابل 3 عاديًا. في P4 بحواف AB BC CD، التعيين 1 1 2 2 يفشل عند الطرفين ذوي الدرجة 1؛ لكن 1 2 2 1 ينجح رغم اتفاق B و C، والأقل 2.
• في C4 بحواف AB AD BC CD، التعيين 1 1 2 2 يحقق النصف عند كل رأس، وله حافتان مختلفتا اللون. التعيين 1 2 1 2 صحيح عاديًا وله أربع حواف مختلفة. كلاهما صالح للأغلبية بأقل 2؛ قبول الحل لا يثبت أن القطع أعظم.
• في تقسيم إلى لونين، نقل رأس يوافقه أكثر من نصف جيرانه يزيد عدد الحواف المختلفة بمقدار الموافقين ناقص المختلفين. لذلك أي قطع أعظم في رسم محدود غير موجه يحقق الشرط عند كل رأس. وجود حافة يمنع اللون الواحد، فيكون الأقل 2 لكل رسم فيه حافة؛ والرسم بلا حواف يقبل 1 لا 0. لا نعمم البرهان على الرسم الموجه أو اللانهائي أو لعبة التلوين.
• يمكن تبديل رأس مخالف ثم إعادة العد؛ عدد الحواف المختلفة يزيد عددًا صحيحًا، فلا يتجاوز عدد التبديلات عدد الحواف. نتوقف عند غياب المخالف، لكن الحل قد لا يحقق القطع الأعظم، كما في C4. في K4 الشاهد 1 1 2 2 يوافق فيه كل رأس جارًا من ثلاثة؛ وفي K5 الشاهد 1 1 1 2 2 يحقق 2 من 4 أو 1 من 4؛ الأقل 2 مقابل 4 و 5 عاديًا. C5 يقبل 1 1 2 1 2 مقابل 3 عاديًا؛ C6 و P5 يقبلان التناوب. النجمتان بثلاث وخمس أوراق تقبلان المركز 1 والأوراق 2؛ الماسة تقبل 1 1 2 2 مقابل 3 عاديًا. الحافة مع المعزولين تقبل 1 2 1 1، والحافتان المنفصلتان 1 2 1 2. الأقل 2 لهذه الرسوم، والمعزول لا يفسد الحل.
• على 64 رسمًا رباعيًا، فحصنا 960 تقسيمًا بعد تجاهل إعادة أسماء الألوان؛ نجح 544 للأغلبية و 337 للصحة العادية. بحث آخر للأقل جرب 306 تعيينات كاملة. الأقل 1 في الرسم الخالي وحده و 2 في 63 رسمًا؛ كان أقل من العادي في 23 ولم يزد. فحص آخر بمساهمات الحواف راجع القوائم في 14 مثالًا و 64 رسمًا، وكل القطوع الأعظم و 1024 بداية ثنائية ومسارات التبديل؛ مولد تقسيمات الألوان مشترك. الأحجام الأخرى خارج الحصر الرباعي. هذه أعداد محدودة، وليست مقياس سرعة؛ برهان اللونين منفصل. راجع شرط كل رأس، ولا تخلط نجاح الأغلبية بصحة كل حافة أو بأعظم قطع.

نعد الجيران بلون الرأس نفسه

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

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

اكتب d لدرجة الرأس، و s لعدد جيرانه الذين يتفقون معه في اللون. الشرط 2s≤d يعبر عن عدم تجاوز النصف دون تقريب الكسور. فإذا كانت الدرجة 3، لا يسمح إلا بجار موافق واحد؛ جارَان من ثلاثة يتجاوزان النصف.

الدرجة 2 تسمح بجار موافق واحد، لأن التعادل مقبول. لا نستبدل «لا أكثر من النصف» بعبارة «أكثر من النصف مختلفون»؛ الثانية تستبعد التعادل وتغير المسألة.

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

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

المثلث يقبل لونين مع حافة متفقة

ثبت المثلث A B C بحواف AB AC BC. إذا أعطينا الجميع 1، فإن كل رأس يوافقه جاراه؛ 2 من 2 أكثر من النصف، فيفشل عند الثلاثة.

اختر A1 B1 C2. عند A الجاران B1 و C2، فيوافقه واحد من اثنين. وعند B الجاران A1 و C2، فتتكرر النتيجة. عند C لا جار بلونه 2، فيكون العدد 0 من 2.

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

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

الطرف ذو الجار الواحد لا يقبل التعادل

خذ P4 على A B C D بحواف AB BC CD. درجتا A و D تساويان 1، ودرجتا B و C تساويان 2. اختلاف الدرجة يغير العدد المسموح من الجيران الموافقين.

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

اختر بدلًا منه 1 2 2 1. عند A و D لا جار موافق؛ وعند B و C جار موافق واحد من اثنين، هو الطرف الآخر للحافة BC. ينجح عند الأربعة، ويحتاج 2 لأن الحافة تمنع لونًا واحدًا.

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

حل مقبول في C4 لا يحقق القطع الأعظم

خذ C4 بحواف AB AD BC CD. التعيين A1 B1 C2 D2 يجعل AB و CD متفقتي اللون، و AD و BC مختلفتي اللون. عند كل رأس جار موافق وآخر مختلف؛ فيحقق النصف.

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

التعيين A1 B2 C1 D2 يجعل الحواف الأربع مختلفة، فيكون حجم القطع 4. لا يمكن تجاوز 4 لأن الرسم لا يملك غيرها؛ إذًا هذا قطع أعظم. كلا التعيينين صالح للأغلبية بأقل 2.

الصورة الداخلية تقارن حلين مقبولين على الحواف الأصلية الأربع نفسها. الحل الأول يثبت أن التوقف دون رأس مخالف لا يضمن أعظم قطع، ولا يعني أقل عدد ألوان تعظيم الحواف المختلفة.

برهان اللونين بتبديل رأس مخالف

قسم الرؤوس إلى لونين، واحسب عدد الحواف المختلفة. عند رأس معين، اكتب s لعدد جيرانه بلونه و t لعدد جيرانه باللون الآخر؛ درجته s+t. إذا كان مخالفًا، فإن 2s>s+t، أي s>t.

بتبديل لونه وحده، تتحول الحواف الموافقة وعددها s إلى مختلفة، والمختلفة وعددها t إلى موافقة. لا تتغير حافة لا تمس هذا الرأس. الزيادة في حجم القطع هي s−t، وهي موجبة.

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

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

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

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

رسوم كثيفة ومعزولون: الأقل لا يزيد على 2

في K4 كل رأس له ثلاثة جيران. الشاهد 1 1 2 2 يجعل لكل رأس جارًا واحدًا بلونه، فيحقق 2×1≤3. الأقل 2 مقابل 4 عاديًا؛ الكثافة وحدها لا تفرض ألوانًا إضافية في سؤال الأغلبية.

في K5 الشاهد 1 1 1 2 2 يعطي كل رأس من الثلاثة الأولى جارَين موافقين من أربعة، وكل رأس من الاثنين الآخرين جارًا موافقًا من أربعة. كلاهما يحقق النصف، فيثبت الأقل 2 مقابل 5 عاديًا.

C5 يقبل 1 1 2 1 2 بأقل 2 رغم حاجته إلى 3 عاديًا. C6 و P5 يقبلان التناوب 1 2 1 2 1 2 أو 1 2 1 2 1. في كل شاهد صحيح عاديًا عدد الموافقين 0، لذلك يحقق الأغلبية أيضًا.

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

حافة AB مع معزولين C و D تقبل 1 2 1 1؛ طرفا الحافة مختلفان، والمعزولان يحققان 0≤0. الحافتان AB و CD تقبلان 1 2 1 2. والأربعة بلا حواف تقبل 1 للجميع بأقل 1.

K5 و C5 و C6 و P5 ونجمة الخمس والمثلث خارج الحصر الرباعي الآتي. أمثلتها فحوص منفصلة؛ وبرهان اللونين العام لا يعتمد على الحصر.

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

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

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

بحث بزيادة عدد الألوان جرب 306 تعيينات كاملة قبل العثور على أول شاهد للأقل في كل رسم. اتفق الأقل مع الحصر: 1 في الرسم الخالي وحده و 2 في 63 رسمًا. كان أقل من العادي في 23 ولم يزد؛ هذه المقارنة العددية تخص الحصر الرباعي.

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

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

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

لمراجعة شاهد، اكتب درجة كل رأس وعدد جيرانه بلونه، ثم افحص 2s≤d عند الجميع. انتبه للدرجة 1 والمعزول والتعادل. لإثبات الأقل، اعرض شاهدًا واستبعد الأصغر؛ ولإثبات القطع الأعظم تحتاج سببًا إضافيًا، لا مجرد نجاح الأغلبية.