تلوين الحواف القوي: لماذا لا يكفي اختلاف لون الحواف المتجاورة؟

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

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

• في تلوين الحواف القوي، تكون حواف كل لون مطابقة مستحثة؛ وأقل عدد من الألوان هو المؤشر اللوني القوي. [1] نلون كل حافة مرة، ولا نختار مجموعة واحدة ونترك البقية بلا لون. نفترض رسمًا محدودًا وبسيطًا وغير موجه، بلا حلقات أو أوزان، وبقائمة رؤوس غير فارغة.
• تلوين الحواف العادي يفرض اختلاف اللون عند كل حافتين تلتقيان في رأس، ويبحث عن أقل عدد من الألوان. [2] القوي يضيف منع الحواف الأصلية بين أطراف حافتين مختلفتين من اللون نفسه. تبديل لون الحافة الواصلة لا يزيلها من الأصل.
• في المسار AB BC CD، التلوين العادي 1 2 1 صالح بلونين، لكنه يفشل قويًا. الحواف الثلاث تتعارض زوجيًا وفق الشرط القوي، فيلزم ثلاثة ألوان، وتعيين 1 2 3 يحققها.
• في C4 بحواف AB AD BC CD يكفي لونان عاديان، لكن كل حافتين تتعارضان قويًا، فيلزم أربعة. في C6 يكفي لونان عاديان وثلاثة قوية: الفئات AB DE، وAF CD، وBC EF؛ ثلاث حواف متتالية تفرض الحد الأدنى 3.
• في النجمة AB AC AD يلزم ثلاثة في الحالين، وفي الزوجين المنفصلين AB CD يكفي لون واحد. الكامل على أربعة يحتاج 3 عادية و 6 قوية. الرسم بلا حواف يحتاج 0 ألوان وله تعيين فارغ واحد؛ المعزول لا يغير ألوان الحواف.
• يمكن اختبار كل فئة لون باستقلال الأطراف والاحتفاظ بكل الحواف الأصلية بينها، أو اختبار كل زوج من حواف اللون نفسه. الطريقتان متكافئتان داخل النموذج، والقوي لا يحتاج ألوانًا أقل من العادي، لكنه قد يساويه.
• حصرنا 64 قائمة حواف على أربعة أسماء و 877 تقسيمًا بعد توحيد أسماء الألوان:125 تلوينًا عاديًا و 67 قويًا، وظهر فرق الأقلين في 34 مدخلًا. راجعنا 877 تقسيمًا بطريقتين، والأقلين بتعيينات ألوان مسماة مستقلة؛ هذه أعداد محدودة، لا صيغة عامة أو ادعاء سرعة.

كل حافة ملونة، وكل لون مجموعة حواف

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

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

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

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

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

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

الحافة الوسطى تمنع لونًا واحدًا للحافتين الخارجيتين

تلوين الحواف العادي يفرض اختلاف اللون عند كل حافتين تلتقيان في رأس، ويبحث عن أقل عدد من الألوان. [2]

المسار A-B-C-D له AB وBC وCD فقط. لو أعطينا AB اللون 1، وBC اللون 2، وCD اللون 1، لوجدنا عند B لونين مختلفين، وعند C كذلك. لا تتلاقى AB وCD، لذا يقبل التلوين العادي تكرار اللون 1 لهما.

لكنهما ليستا مطابقة مستحثة. أطراف فئة اللون 1 هي A B C D، وبينها توجد BC أيضًا. لون BC المختلف لا يغير وجودها، ولا يزيلها من الرسم المستحث على أطراف فئة اللون 1.

التعارض القوي يشمل كل زوج هنا: AB مع BC تتلاقيان عند B، وBC مع CD عند C، وAB مع CD تصل بين أطرافهما BC. لذلك لا يجوز أن يشترك أي زوج من الثلاث في لون قوي.

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

إذن أقل العادي 2، لأن التلوين 1 2 1 صالح ولأن التقاء AB وBC يمنع لونًا واحدًا. وأقل القوي 3، لأن التعارض الثلاثي يمنع أقل من 3 والتعيين 1 2 3 صالح. الصورة الرئيسية تعرض الشاهدين على المسار نفسه.

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

اختبار فئات الألوان يكافئ اختبار أزواجها

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

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

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

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

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

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

الدورة الرباعية تحتاج لونًا قويًا لكل حافة

الدورة A-B-C-D-A لها AB وAD وBC وCD. للتلوين العادي، أعطِ AB وCD اللون 1، وAD وBC اللون 2. عند كل رأس حافتان مختلفتا اللون، ويلزم لونان على الأقل لأنهما متلاقيتان.

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

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

لاحظ أن اللون المختلف للحافتين الواصلتين لا يحل المشكلة. عند تكرار لون AB على CD، يكفي وجود AD أوBC في الأصل لرفض الفئة، سواء كان لونهما 2 أو 3 أو غير ذلك.

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

الدورة السداسية تجمع كل زوج متقابل في لون

خذ الدورة A-B-C-D-E-F-A كاملة بحواف AB AF BC CD DE EF. للتلوين العادي استعمل اللون 1 للحواف AB وCD وEF، واللون 2 للحواف AF وBC وDE. تتناوب الألوان حول الدورة، فيكفي اثنان ويلزم اثنان عند كل رأس.

للتلوين القوي استعمل ثلاث فئات: اللون 1 للحافتين AB وDE، واللون 2 لـAF وCD، واللون 3 لـBC وEF. القوائم تغطي الحواف الست مرة واحدة، وتختلف عن التناوب العادي السابق.

على أطراف AB وDE، أي A B D E، لا توجد إلا AB وDE. بقية الحواف لها طرف في C أوF خارج المجموعة. وهكذا تكون فئة اللون 1 مستحثة؛ ينطبق الفحص نفسه على الفئتين الأخريين.

إذن ثلاثة ألوان قوية تكفي. ولإثبات أنها الأقل، انظر إلى AB وBC وCD: الأولى والثانية تتلاقيان، والثانية والثالثة تتلاقيان، والأولى والثالثة تصل بين أطرافهما BC. تحتاج هذه الثلاثة إلى ثلاثة ألوان مختلفة مهما لونا بقية الدورة.

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

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

النجمة والزوجان والكامل تضبط الفرق

في النجمة AB AC AD، الحواف الثلاث تتلاقى كلها عند A، فتحتاج ثلاثة ألوان عادية وثلاثة قوية. كل فئة ستكون حافة واحدة؛ لا يظهر فرق العددين لمجرد استعمال كلمة «قوي».

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

أما الكامل على A B C D، فحوافه AB AC AD BC BD CD. للتلوين العادي استعمل الفئات AB CD، وAC BD، وAD BC؛ كل منها مطابقة. تكفي 3، وتحتاج حواف أي رأس الثلاثة إلى 3، فيثبت الأقل 3.

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

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

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

تبديل أسماء الألوان لا يصنع تقسيمًا جديدًا

للمراجعة المحدودة، ثبتنا الأسماء A B C D وأخذنا كل واحدة من 2^6=64 قائمة حواف. رتبنا حواف كل قائمة، وحصرنا تقسيماتها إلى فئات غير فارغة. لا نفرض استعمال ثلاثة ألوان مثلًا قبل معرفة الأقل.

وحدنا أسماء الفئات حسب أول ظهور في قائمة الحواف. التعيين 1 2 1 والتعيين 2 1 2 للمسار يصفان التقسيم نفسه: AB CD في فئة وBC في أخرى. إعادة تسمية اللونين لا تضيف تقسيمًا ثانيًا في هذا الحصر.

بلغ مجموع مرشحات التقسيم 877 عبر المدخلات الأربعة والستين. اجتاز شرط المطابقة العادية 125 تقسيمًا، واجتاز شرط المطابقة المستحثة 67. يضم العددان التلوينات الصالحة التي تستخدم أكثر من العدد الأقل، لا التلوينات الدنيا وحدها.

بلغ إجمالي التقسيمات التي تحقق الأقل العادي 64، وكذلك الأقل القوي 64؛ هذا مجموع عبر المدخلات، مع تعيين فارغ واحد في المدخل بلا حواف. لا يعني تساوي المجموعين تساوي العدد الأقل من الألوان؛ اختلف الأقلان في 34 مدخلًا.

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

بلغ مرشحو هذه الطريقة 4143 للعادي و 99821 للقوي؛ تلك أعداد تعيينات بأسماء ألوان وتجارب حدود مختلفة، فلا تساوي مرشحات التقسيم 877 ولا تقارن بها بوصفها عدد حلول واحدًا. اتفق الأقل الناتج بالطريقتين في 64 مدخلًا.

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