تلوين الزمر العظمى: لماذا يقبل المثلث لونين؟

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

لأن زمرة المثلث العظمى ABC تحتوي لونين في التعيين 112. الحافة AB بلون واحد ليست عظمى؛ يمكن إضافة C إليها. اللون الواحد للمثلث يفشل، والشاهد ذو اللونين ينجح، فيثبت أن الأقل 2.

• تلوين الزمر يطلب ألا تكون أي زمرة عظمى أحادية اللون، مع استثناء الرؤوس المعزولة من هذا القيد؛ والعدد المطلوب أقل عدد ألوان يحققه. [1] نفحص الزمر ذات رأسين أو أكثر. نعمل على رسم محدود وبسيط وغير موجه وغير فارغ الرؤوس. نلون الجميع، حتى المعزول، ونقلل عدد الألوان المستعملة بأسماء قابلة للتبديل. نستثني المعزول من القيد فقط، ولا نطلب اختلاف كل ألوان رؤوس الزمرة.
• التلوين الصحيح العادي يفرض اختلاف لون طرفي كل حافة، ويبحث عن أقل عدد ألوان. [2] شرط الزمر لا يفرض ذلك على كل حافة؛ يكفي وجود لونين على الأقل داخل كل زمرة عظمى. المثلث 112 ينجح للزمر بأقل 2، لكنه غير صحيح عاديًا بسبب AB؛ الصحيح يحتاج 3. كل تلوين صحيح يحقق شرط الزمر، فلا يزيد أقل الزمر عليه. في K_n ذي n≥2، كل الرؤوس هي الزمرة العظمى الوحيدة؛ لون 1 لرأس ولون 2 للباقين يكفيان بأقل 2، بينما الصحيح يحتاج n.
• العظمى لا تقبل التوسيع، والأكبر حجمًا يبلغ أكبر عدد رؤوس في الرسم؛ كل أكبر عظمى، لا العكس. [3] [4] مثلث AB AC BC مع الحافة CD له زمرتان لا تقبلان التوسيع: ABC بحجم 3 وCD بحجم 2. 1122 ينجح على الأكبر ABC لكنه يفشل على CD أحادية اللون؛ 1121 يصلحه بأقل 2. فحص أكبر حجم وحده لا يكفي.
• تقسيم الرؤوس إلى غابات يطلب أن تستحث كل فئة غابة، ويقلل عدد الفئات. [5] يمنع أي دورة أحادية اللون داخل الفئة؛ تلوين الزمر يختبر الزمر العظمى فقط. K4 بالشاهد 1112 يقبل لونين للزمر، رغم المثلث ABC أحادي اللون؛ ABC ليس عظمى لأن D يوسعها. K5 بالشاهد 11112 يحتاج 2 للزمر و 3 لغابات اللون؛ أي ثلاثة رؤوس في فئة على K5 تصنع مثلثًا. P4 بالعكس يحتاج 2 للزمر و 1 للغابات، لذلك لا ترتيب ثابت بين العددين.
• في رسم بلا مثلثات، كل حافة زمرة عظمى ولا زمرة أكبر؛ شرط الزمر يساوي التلوين الصحيح. P4 وP5 وP6 والنجمتان بثلاث وخمس أوراق وC4 وC6 وK2,3 وK3,3 تحتاج 2. C5 تحتاج 3، بالشاهد 12123؛ التناوب بلونين يفشل عند الإغلاق الفردي. لذلك لا حد عام 2 مستنتج من الرسوم الرباعية.
• الماسة AB AC AD BC BD لها الزمرتان ABC وABD؛ 1122 ينجح بأقل 2، حتى مع AB أحادية اللون غير العظمى. حافتان منفصلتان AB وCD تحتاجان 2 بالتعيين 1212؛ حافة AB ومعزولان C وD تحتاج 2 بالشاهد 1211. الرسم بلا حواف يقبل 1 للجميع بأقل 1 لا 0؛ المعزولات ملونة. أي رسم فيه حافة يحتاج لونين على الأقل، لأن الحافة تتوسع إلى زمرة عظمى غير تافهة.
• حصر 64 رسمًا رباعيًا أعطى 960 تقسيمًا: 518 للزمر، 337 صحيحًا، 902 لغابات اللون. بحث الأقل جرب 313 تعيينًا كاملًا؛ الأقل 1 في الرسم الخالي من الحواف و 2 في 63. قل عن الصحيح في 23 رسمًا يحوي مثلثًا: 4 مع معزول، و 12 مع حافة طرفية، و 6 ماسات، وK4 واحدة، وزاد عن الغابات في 37 غابة غير خالية الحواف؛ لم يقل عنها ضمن الأربعة، لكن K5 يفرق خارجها. فحص آخر للمجموعات المرشحة والجوار راجع كل قائمة زمر عظمى، واتفق في 19 مثالًا و 64 رسمًا والقوائم الكاملة للأقل؛ راجع رأسًا ورأسين، ومولد التقسيمات مشترك. الأعداد ليست أزمنة تنفيذ.

نفحص كل زمرة غير قابلة للتوسيع، لا كل حافة

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

الزمرة العظمى لا تقبل إضافة رأس آخر مع بقاء الاتصال بين كل زوج؛ ليست جزءًا من زمرة أكبر. [3] نعني بعظمى هنا عدم القابلية للتوسيع.

الزمرة مجموعة رؤوس، كل زوج مختلف منها متصل بحافة. لمعرفة هل هي عظمى، اسأل هل يوجد رأس خارجها متصل بكل رؤوسها؛ إن وجد أمكن إضافته، فلا تكون عظمى. عدم اتصال الخارج برأس واحد منها يمنع إضافة ذلك الرأس. [3] [4]

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

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

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

المثلث 112 ينجح، والحافة AB ليست اختبارًا مستقلًا

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

ثبت A B C والحواف AB AC BC. الزمرة العظمى الوحيدة ABC؛ أي حافة من حوافها تتوسع بإضافة الرأس الثالث، فلا تكون عظمى. التعيين 112 يجعل ABC ذا لونين، فينجح للزمر.

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

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

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

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

حافة من حجم 2 تبقى عظمى إلى جانب مثلث أكبر

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

ثبت الرسم AB AC BC CD. الرؤوس A B C مثلث، وD متصل بـC فقط. ABC عظمى لأن D لا يتصل بـA أو B. والحافة CD عظمى لأن A وB لا يتصلان بـD؛ لا يمكن إضافتهما إليها.

الزمر العظمى غير التافهة هي ABC وCD، بينما الأكبر حجمًا ABC فقط. لا يكفي أن نرى حجم 3 ثم نتجاهل الحافة ذات الحجم 2؛ شرط التلوين يخص العظمى مهما اختلفت أحجامها.

التعيين 1122 على A B C D يعطي ABC اللونين 1 و 2، لكنه يعطي CD اللون 2 وحده، فيفشل. تغيير D إلى 1 يعطي 1121؛ ABC تظل متعددة الألوان، وCD تصير بلونين، فينجح بأقل 2.

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

العظمى خاصية احتواء: لا توجد زمرة أوسع تضم هذه المجموعة كلها. الأكبر خاصية حجم: لا توجد زمرة في الرسم بحجم أكبر. كل أكبر عظمى، لكن مثال CD يبين لماذا لا يلزم العكس.

مثلث أحادي اللون قد ينجح إذا لم يكن عظمى

تقسيم الرؤوس إلى غابات يطلب أن تستحث كل فئة غابة، ويقلل عدد الفئات. [5] يمنع أي دورة أحادية اللون داخل الفئة؛ تلوين الزمر يختبر الزمر العظمى فقط.

في K4 على A B C D، الزمرة العظمى الوحيدة ABCD. الشاهد 1112 ينجح بأقل 2 لأن الزمرة كلها تحتوي اللونين. المثلث ABC أحادي اللون، لكنه يتوسع بإضافة D، فلا يدخل قائمة الاختبار.

إذن شرط الزمر لا يمنع كل مثلث أحادي اللون، ولا كل دورة أحادية اللون. في 1112، فئة اللون 1 على ABC مثلث، فتفشل لغابات اللون رغم نجاح الزمر. لا يحول وجود رأس بلون آخر خارج المثلث حوافه إلى غابة.

في K5، الشاهد 11112 يحقق تلوين الزمر بأقل 2، للسبب نفسه. غابات اللون تحتاج 3: أي فئة تضم ثلاثة رؤوس في الكامل تستحث مثلثًا، فتسع الفئة اثنين فقط؛ لونان لا يغطيان خمسة رؤوس، والشاهد 11223 يحقق ثلاث فئات غابات.

على P4 ذي الحواف AB BC CD، كل حافة عظمى، فتلوين الزمر 1212 يحتاج 2. لكن 1111 يجعل فئة اللون طريقًا كاملًا بلا دورة، فينجح للغابات بأقل 1.

في P4 يزيد أقل الزمر على الغابات، وفي K5 يقل عنها؛ فلا ترتيب ثابت بين العددين. قارن شرطًا محددًا على الرسم نفسه بدل افتراض أن كل تلوين يسمح بحافة أحادية اللون يعطي العدد نفسه.

بلا مثلثات يعود شرط اختلاف طرفي كل حافة

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

بذلك ينجح تلوين الزمر إذا وفقط إذا اختلف لون طرفي كل حافة. P4 يقبل 1212 بأقل 2، وP5 يقبل 12121، وP6 يقبل 121212؛ كلها مسارات، والحافة تمنع الواحد.

نجمة AB AC AD تقبل 1222 بأقل 2، ونجمة AB AC AD AE AF تقبل 122222. المركز بلون 1 وكل الأوراق بلون 2؛ كل زمرة عظمى حافة مختلفة الطرفين. عدد الأوراق لا يفرض ألوانًا إضافية هنا.

C4 بالحواف AB BC CD AD تقبل 1212 بأقل 2، وC6 تقبل 121212 بأقل 2. لا مثلث فيهما، والتناوب يختلف على كل حافة، بما فيها حافة الإغلاق.

أما C5 فتحتاج 3. مع لونين، التناوب حول A B C D E يضع A وE في اللون نفسه، فتفشل الحافة AE العظمى. الشاهد 12123 صحيح على الحواف الخمس فينجح للزمر بأقل 3. لا يكفي كون كل زمرة من حجم 2 لاستنتاج أن لونين يكفيان للرسم كله.

في K2,3 وK3,3، كل حافة تعبر بين الجانبين ولا مثلث. نعطي جانبًا اللون 1 والآخر اللون 2، فينجح بأقل 2، لأن وجود حافة يمنع الواحد. لا يشترط أن يكون لون كل رأس مختلفًا عن جميع رؤوس جانبه.

زمرتان في الماسة، والمعزول يبقى ملونًا

خذ الماسة AB AC AD BC BD. الزمرتان العظمى ABC وABD؛ لا حافة CD. الشاهد 1122 يجعل A وB بلون 1، وC وD بلون 2؛ كل مثلث مطلوب يرى اللونين، فينجح بأقل 2.

AB أحادية اللون، لكنها تتوسع إلى ABC أو ABD فلا تكون عظمى. كل الحواف الأخرى أيضًا ضمن إحدى الزمرتين المطلوبتين. ولا تتوسع ABC بإضافة D بسبب غياب CD، وينطبق الأمر على ABD عند محاولة إضافة C.

في الحافتين المنفصلتين AB وCD، كل حافة عظمى، فلا بد من اختلاف طرفيها. الشاهد 1212 ينجح بأقل 2. وفي حافة AB مع معزولين C وD، الشاهد 1211 يحقق القيد على AB؛ C وD مستثنيان من القيد، لكنهما ملونان.

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

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

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

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

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

نجح 518 تقسيمًا للزمر، و 337 صحيحًا عاديًا، و 902 لغابات اللون. بحث الأقل بزيادة عدد الألوان جرب 313 تعيينًا كاملًا حتى أول نجاح لكل رسم. الأقل 1 للخالي من الحواف، و 2 للرسوم الثلاثة والستين الأخرى. هذه ليست أزمنة تنفيذ.

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

إذا وجد مثلث ABC، فالرأس الرابع D له صفر أو جار واحد أو جارَان أو ثلاثة داخل المثلث. نحصل على مثلث ومعزول، أو مثلث مع حافة طرفية، أو ماسة، أو K4. تقبل هذه الأنواع 2 بالشواهد 1121 و 1121 و 1122 و 1112 بعد إعادة أسماء الرؤوس بما يلائم المواضع.

الأقل يقل عن الصحيح في 23 رسمًا، وهي التي تحوي مثلثًا: أربع مثلثات مع معزول، واثنا عشر مثلثًا مع حافة طرفية، وست ماسات، وK4 واحدة. الصحيح يحتاج 3 في الأنواع الثلاثة الأولى و 4 في K4، بينما الزمر تحتاج 2. عدد المثلث مع المعزول 4 باختيار المعزول، والحافة الطرفية 12 باختيار المعزول السابق ثم جاره من المثلث. الماسات 6 باختيار الحافة الوحيدة الغائبة، والكامل واحد؛4+12+6+1=23.

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

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

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

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