جار موافق واحد كحد أقصى: لماذا يقبل المسار ما ترفضه الأغلبية؟

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

لأن سقف الجيران الموافقين ثابت عند 1، بينما الأغلبية تقارنه بنصف الدرجة. في P4 بحواف AB BC CD، الشاهد A1 B1 C2 D2 يوافق فيه كل رأس جارًا واحدًا؛ فينجح هنا، لكن A و D يوافقهما جار من أصل واحد فيفشلان في الأغلبية.

• تسمح قاعدة العيب اللوني بأن تتفق ألوان طرفي حافة، لكنها تضع حدًا أقصى للدرجة داخل كل مكون أحادي اللون. [1] نثبت الحد هنا عند 1: لا يملك أي رأس أكثر من جار واحد بلونه. نموذجنا محدود وبسيط وغير موجه، ورؤوسه غير فارغة وملونة كلها؛ ونبحث عن أقل عدد ألوان مستعملة. الصفر مسموح: المعزول يبقى ملونًا، ولا نشترط جارًا موافقًا بالفعل. الألوان أسماء حرة، والعدد 1 يصف السقف لا رقم اللون.
• التلوين الصحيح العادي يختلف فيه لون طرفي كل حافة، ويبحث عن أقل عدد ألوان. [2] هذا شرط أقوى من السماح بجار موافق واحد؛ الحد 0 يستعيد الصحة العادية، بينما الحد 1 يسمح ببعض الحواف المتفقة. كل مكون بلون واحد يكون رأسًا منفردًا أو حافة، لكن الفئة اللونية كلها قد تحوي أكثر من رأسين في مكونات منفصلة. الحافتان AB و CD تقبلان 1 للجميع بفئة من أربعة ومكونين بحجم 2؛ وحافة مع معزولين والرسم الخالي تقبلان 1 لا 0. اللون الواحد ينجح إذا وفقط إذا كانت أكبر درجة أصلية لا تتجاوز 1.
• الأغلبية تسمح ألا يزيد عدد الجيران بلون الرأس نفسه على نصف عدد جيرانه. [3] أما سؤالنا فيضع سقفًا ثابتًا هو 1 مهما تغيرت الدرجة. في P4 يفشل 1 للجميع عند B و C اللذين يوافقهما جاران؛ وينجح 1 1 2 2 بأقل 2 رغم اتفاق AB و CD، بينما ترفضه الأغلبية عند A و D. الشاهد 1 2 2 1 ينجح في السؤالين؛ صحة شاهد لا تكفي للحكم على شاهد آخر.
• K5 يقبل 1 1 1 2 2 للأغلبية، لكنه يفشل هنا عند الرؤوس الثلاثة الأولى لأن لكل منها جارَين بلونه. الشاهد 1 1 2 2 3 ينجح بأقل 3: في الرسم الكامل لا تتسع فئة اللون لأكثر من رأسين، فلا يغطي لونان خمسة رؤوس. K6 يقبل 1 1 2 2 3 3 بأقل 3 مقابل 6 عاديًا؛ وفي K_n الأقل ceil(n/2)، أي نصف عدد الرؤوس مقربًا إلى العدد الصحيح الأعلى، وليس 2 دائمًا.
• لكل رسم بسيط على n رؤوس، تقسيم الرؤوس إلى مجموعات بحجم 2 أو 1 وإعطاء كل مجموعة لونًا يثبت حدًا أعلى ceil(n/2). هذه طريقة لبناء شاهد، وليست شرطًا على حجم الفئة في كل حل. نثبت الأقل باستبعاد الأعداد الأصغر؛ ونفحص الجيران الموافقين عند كل رأس، لا مجموع الحواف المتفقة أو عدد الألوان في الجوار.
• C4 يقبل 1 1 2 2، والمثلث 1 1 2، و K4 والماسة 1 1 2 2؛ الأقل 2 لها، مقابل 3 للمثلث والماسة و 4 لـK4 عاديًا. C5 يقبل 1 1 2 1 2، و C6 التناوب؛ والنجمتان بثلاث وخمس أوراق تقبلان المركز 1 وكل الأوراق 2، بأقل 2. لا يكفي اللون الواحد لأنها تملك رأسًا درجته أكبر من 1. وإذا رفعنا السقف إلى أكبر درجة أصلية، صار اللون الواحد صالحًا، لكننا نثبت السقف 1 في الأمثلة والحصر.
• حصر 64 رسمًا رباعيًا أعطى 960 تقسيمًا بعد تجاهل إعادة أسماء الألوان:778 تحقق السقف 1، و 337 الصحة العادية، و 544 الأغلبية. بحث آخر للأقل جرب 224 تعيينًا كاملًا. الأقل 1 في 10 رسوم: الخالي وستة رسوم بحافة واحدة وثلاث مطابقات تامة: AB مع CD، و AC مع BD، و AD مع BC، فيكون 1+6+3=10؛ والأقل 2 في 54. كان أقل من العادي في 32، وأقل من الأغلبية في 9 ولم يزد عنها في الحصر فقط؛ K5 خارج الحصر يزيد عنها. فحص آخر بالمكونات راجع 14 مثالًا و 64 رسمًا والقوائم الكاملة، مع مولد تقسيمات مشترك، وحالات من رأس واحد أو رأسين. الأعداد ليست مقياس سرعة؛ لا نعمم حد اللونين من أربعة رؤوس.

سقف واحد لكل رأس، لا اشتراط اتفاق واحد

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

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

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

الحد هو «واحد كحد أقصى»، فيقبل 0 أو 1. المعزول له 0 جيران موافقين فينجح، لكن نعطيه لونًا مع البقية. نستخدم أسماء ألوان قابلة للتبديل، ونحسب عدد الألوان المستعملة لا أكبر رقم بينها.

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

فئة من أربعة رؤوس قد تنجح بلون واحد

ثبت A B C D والحافتين AB و CD فقط. أعط الجميع 1؛ كل رأس له جار واحد بلونه، فيحقق s≤1. الأقل 1 لأن الرسم غير فارغ الرؤوس، وقد عرضنا شاهدًا بلون واحد.

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

على حافة AB مع معزولين C و D، يقبل A1 B1 C1 D1 أيضًا: عند A و B جار موافق واحد، وعند C و D لا جار. والرسم بلا حواف يقبل 1 للجميع كذلك؛ الأقل 1 لا 0 في الحالتين.

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

P4 ينجح بالشاهد الذي ترفضه الأغلبية

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

خذ P4 على A B C D بحواف AB BC CD. درجتا A و D تساويان 1، ودرجتا B و C تساويان 2. إعطاء الجميع 1 يفشل عند B و C لأن لكل منهما جارَين بلونه؛ فلا يكفي لون واحد.

اختر A1 B1 C2 D2. لكل رأس جار موافق واحد: A مع B، و B مع A، و C مع D، و D مع C. نجح السقف 1 عند الأربعة، فيثبت الأقل 2. لم نحذف AB أو CD؛ اتفاق طرفيهما مسموح.

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

التعيين 1 2 2 1 ينجح في السؤالين: عند A و D لا موافق، وعند B و C موافق واحد من اثنين، عبر BC. لا نقول إن كل شاهد مقبول في أحد السؤالين مقبول في الآخر؛ نفحص التعيين المحدد.

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

K5 يحتاج ثلاثة ألوان رغم قبول الأغلبية لونين

خذ K5 على A B C D E، وكل زوج رأسين بينه حافة؛ لكل رأس أربعة جيران. التعيين 1 1 1 2 2 يعطي A و B و C جارَين بلون كل رأس منهم من أربعة، ويعطي D و E جارًا واحدًا بلونهما من أربعة.

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

اختر A1 B1 C2 D2 E3. عند A و B جار موافق واحد، وعند C و D جار موافق واحد، وعند E لا جار موافق. ينجح بثلاثة ألوان.

في رسم كامل، كل رأس داخل فئة لون بحجم q يوافقه q−1 جيران. السقف 1 يفرض q≤2، لذلك لا يغطي لونان إلا أربعة رؤوس. K5 له خمسة، فيستحيل لونان، واللون الواحد مرفوض أيضًا؛ فيثبت الأقل 3.

وفي K6، الشاهد 1 1 2 2 3 3 ينجح بثلاثة، ولونان لا يغطيان إلا أربعة من ستة؛ الأقل 3 مقابل 6 عاديًا. وللرسم الكامل K_n عمومًا، سعة كل فئة 2 تعطي حدًا أدنى ceil(n/2)، أي نصف عدد الرؤوس مقربًا إلى العدد الصحيح الأعلى، وتقسيم الرؤوس إلى أزواج ورأس منفرد عند الحاجة يحققه.

سعة الفئة 2 هنا تأتي من اكتمال الحواف، وليست شرطًا عامًا في كل رسم؛ الحافتان المنفصلتان أعطتا فئة من أربعة ناجحة. الصورة الداخلية تحفظ حواف K5 العشر في الجانبين وتعرض إخفاق 1 1 1 2 2 وإصلاحه بـ1 1 2 2 3.

تقسيم إلى أزواج يعطي حدًا أعلى لكل رسم

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

لا يملك أي رأس أكثر من رأس آخر في مجموعته، لذلك لا يمكن أن يكون له أكثر من جار واحد بلونه. عدد الألوان هو ceil(n/2)، فيثبت حدًا أعلى في نموذجنا. البرهان من إعداد المقال، ولا يحتاج أن يكون الرسم كاملًا.

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

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

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

دورات ونجوم وماسة: الشواهد والأعداد

C4 بحواف AB AD BC CD يقبل 1 1 2 2؛ لكل رأس جار موافق واحد، والأقل 2 لأن اللون الواحد يعطي الجميع جارَين موافقين. المثلث AB AC BC يقبل 1 1 2، بأقل 2 مقابل 3 عاديًا.

K4 يقبل 1 1 2 2 بأقل 2 مقابل 4 عاديًا؛ كل فئة رأسَان فقط، ولا يكفي اللون الواحد لأن كل رأس درجته 3. والماسة AB AC AD BC BD تقبل 1 1 2 2: عند A و B موافق واحد، وعند C و D لا موافق، بأقل 2 مقابل 3 عاديًا.

C5 يقبل 1 1 2 1 2؛ الموافقون عند A و B واحد لكل منهما، وعند C و D و E صفر. C6 يقبل التناوب 1 2 1 2 1 2، وفيه الموافقون صفر عند الجميع. الأقل 2 في الدورتين لأن اللون الواحد يجعل كل رأس يوافقه جارَان.

النجمتان بثلاث وخمس أوراق تقبلان إعطاء المركز 1 وكل الأوراق 2. لا يوجد جار موافق عند أي رأس، فتنجحان بأقل 2؛ اللون الواحد يخالف عند المركز، لأن درجته 3 أو 5.

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

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

عشرة رسوم رباعية تقبل لونًا واحدًا

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

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

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

المطابقات التامة الثلاث هي AB مع CD، و AC مع BD، و AD مع BC. لا توجد حواف أخرى في هذه الرسوم. يثبت العد 1+6+3=10 عدد الحالات التي تقبل اللون الواحد، دون احتساب إعادة أسماء الألوان كحلول مختلفة.

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

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

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