لونان بين الجيران: لماذا تحتاج الرباعية أربعة ألوان؟

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

في الرباعية AB AD BC CD، التوزيع 1 2 1 2 صحيح عند أطراف الحواف، لكن جارَي كل رأس لهما اللون نفسه. القاعدة الديناميكية تجبر A وC على الاختلاف، وكذلك B وD؛ مع اختلاف الجيران الأصليين تصبح الرؤوس الأربعة مختلفة، فتحتاج 4. أما النجمة فتقبل A1 B2 C3 D2 لأن المركز يرى لونين، والورقة ذات الجار الواحد لا تطلب اثنين.

• التلوين الصحيح يختلف عند طرفي كل حافة. [2] نأخذ حالة r=2 من التلوين الديناميكي: لكل رأس عدد ألوان جيران لا يقل عن الأصغر بين 2 ودرجته، ونبحث عن أقل عدد ألوان يحقق ذلك. [1] نموذجنا محدود وبسيط وغير موجه بلا حلقات أو أوزان، ورؤوسه غير فارغة؛ كل رأس له لون واحد.
• نعد ألوان الجيران المباشرين المختلفة، لا الجيران أنفسهم ولا لون الرأس معهم. درجة 0 تطلب 0، ودرجة 1 تطلب 1، ودرجة 2 أو أكثر تطلب لونين على الأقل؛ لا نطلب كل الألوان المستخدمة أو اختلاف جميع الجيران. الفئات غير فارغة، وتبديل أسماء الألوان يحفظ القاعدة؛ لا ترتيب معالجة للرؤوس هنا.
• في C4، الصحيح 1 2 1 2 يفشل عند الرؤوس الأربعة. جارَا B يجبران A وC على الاختلاف، وجارَا A يجبران B وD؛ ومع الحواف الأصلية تختلف كل الأزواج الستة. التوزيع 1 2 3 4 يحقق القاعدة، فالأقل 4 رغم أن الأقل العادي 2.
• النجمة AB AC AD تحتاج 3: A1 B2 C3 D2 يجعل المركز يرى 2 و 3، والورقة ترى 1 فقط وهذا يكفي لدرجتها 1. التلوين الصحيح بلونين يجعله يرى لونًا واحدًا فيفشل. قوة الرسم تصل طرفين بطريق لا يزيد على الأس، [3] ومربعه قوته الثانية. [4] تلوين المربع يطلب اختلاف كل زوج أوراق، فيحتاج 4؛ القاعدة الحالية تسمح تكرار 2.
• C5 تحتاج 5 لأن كل زوج مختلف إما حافة أو جارَان لرأس، فتجبر القاعدة اختلاف الجميع. لذلك أقصى درجة زائد 1 ليس حدًا لها: الدرجة 2 والجواب 5. C6 وP4 وP5 تحتاج 3؛ اللونان يجعلان جيران رأس داخلي متماثلين، والتوزيعات 1 2 3 1 2 3 و 1 2 3 1 و 1 2 3 1 2 تحقق 3.
• المثلث والماسة دون CD تحتاجان 3، وK4 أربعة. الحافة مع معزولين وحافتان منفصلتان تحتاجان 2، والرؤوس بلا حواف 1؛ نلون المعزول ولا نطلب منه جارًا. هذا أقل عدد مع تنوع الجوار، لا أكبر عدد مع اختيار جشع أو شاهد لكل فئة؛ الرباعية عدد غروندي وشهودها الأقصى 2، لكن الأقل الديناميكي 4.
• حصرنا 64 رسمًا رباعيًا:960 تقسيمًا، منها 337 صحيحة و 252 ديناميكية. اتفق فحص الجوار والفئات في 960 حالة، والبحث المستقل للأقل جرب 1985 تعيينًا مسمى كاملًا. في 31 رسمًا يزيد الأقل الديناميكي عن الأقل العادي، وفي 22 يزيد أقل تلوين المربع عن الأقل الديناميكي. التوزيع 1: واحد،2:9،3:50،4: أربعة؛ C5 وP5 وC6 خارج الحصر، ولا نخلط التعيينات بالرسوم.

لونان مختلفان عند الجيران، مع استثناء الدرجة الصغيرة

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

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

الجيران هم الرؤوس التي تصلها بالرأس حافة مباشرة. نجمع الألوان المختلفة التي يحملونها، دون إضافة لون الرأس نفسه أو رأس أبعد. ثلاثة جيران باللون 2 يعدون لونًا واحدًا، لا ثلاثة ألوان.

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

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

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

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

الرباعية تجبر اختلاف جميع الأزواج الستة

C4 على A B C D لها AB AD BC CD. التناوب 1 2 1 2 صحيح عاديًا، لأن طرفي كل حافة مختلفان. لكن B وD يريان A وC باللون 1 نفسه، وA وC يريان B وD باللون 2 نفسه؛ كل رأس درجته 2 ويرى لونًا واحدًا فقط.

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

الحواف الأصلية تجبر اختلاف AB وAD وBC وCD. مع AC وBD المطلوبين من الجوار، صارت كل الأزواج الستة بين الرؤوس الأربعة مختلفة الألوان، فلا يكفي ثلاثة أو أقل.

أعطِ الرؤوس 1 2 3 4. كل حافة مختلفة الطرفين، وعند A نرى B2 وD4، وعند B نرى A1 وC3، وعند C نرى B2 وD4، وعند D نرى A1 وC3. تحقق اللونان عند كل رأس، فيثبت الأقل 4.

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

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

النجمة تحتاج ثلاثة وتسمح بتكرار لون ورقتين

النجمة على A B C D لها AB AC AD، والمركز A درجته 3 والأوراق درجتها 1. مع A1 B2 C2 D2، كل الحواف صحيحة، لكن المركز يرى لونًا واحدًا 2 بين ثلاثة جيران، فيفشل طلبه.

لا يوجد تلوين صحيح بلونين يصلح: لون المركز واحد، وكل أوراقه المتجاورة معه يجب أن تحمل اللون الآخر الوحيد. مهما بدلنا الاسمين، تبقى مجموعة ألوان الجيران عند المركز من عنصر واحد.

بدل لون C إلى 3، واترك A1 B2 D2. الآن يرى المركز 2 و 3 بين B وC وD، ويظل كل طرفي حافة مختلفين. كل ورقة ترى 1 عند جارها الوحيد، وهذا يكفي لأن المطلوب عند الدرجة 1 لون واحد.

إذن A1 B2 C3 D2 شاهد بثلاثة، واستبعاد اللونين مع الحافة التي تمنع 1 يثبت الأقل 3. B وD باللون 2 نفسه ولا حافة بينهما في الأصل؛ تكرارهما لا يفسد القاعدة.

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

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

تلوين مربع الرسم أقوى عند رأس كثير الجيران

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

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

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

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

في نجمتنا كل زوج من الأوراق B وC وD يصل بطريق طوله 2 عبر A، فتضاف BC وBD وCD في المربع، وتبقى AB وAC وAD. يصبح المربع K4، فيحتاج 4 ألوان؛ الأصل يحقق التنوع بثلاثة مع تكرار لون B وD.

وفي الرباعية يضيف المربع AC وBD إلى الحواف الأربع، فيصبح K4 أيضًا، وهذا يطابق برهان اختلاف الأزواج الستة. لا نستنتج من هذا التطابق أن تلوين المربع يساوي القاعدة في جميع الرسوم؛ النجمة ترفض التعميم.

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

الخماسية تحتاج خمسة، والسداسية والمساران ثلاثة

في C5 على A B C D E بالحواف AB AE BC CD DE، أي رأسين مختلفين متجاوران أو تفصلهما خطوتان. يمكن رؤية ذلك من القائمة: بعد الحواف الخمس، الأزواج الباقية AC وAD وBD وBE وCE، ولكل منها جار وسيط في الدورة.

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

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

في C6 على A B C D E F بالحواف AB AF BC CD DE EF، التوزيع 1 2 3 1 2 3 صحيح. عند كل رأس اللونان في جاريه هما اللونان الآخران: A يرى 2 و 3، وB يرى 1 و 3، وC يرى 2 و 1، ويتكرر الفحص عند D وE وF.

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

المسار P4 على AB BC CD يقبل 1 2 3 1؛ B يرى 1 و 3، وC يرى 2 و 1، والطرفان درجتهما 1 فيكفي لون جار كل منهما. والمسار P5 على AB BC CD DE يقبل 1 2 3 1 2؛ عند B وC وD لونان مختلفان بين الجيران، والطرفان مستثنيان من طلب اثنين.

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

المعزول والمثلث والماسة يضبطون الطلب

المثلث AB AC BC يقبل A1 B2 C3؛ كل رأس يرى اللونين الآخرين بين جاريه. التلوين الصحيح نفسه يحتاج 3 بسبب الحواف الثلاث، فيكون الأقل الديناميكي 3.

الماسة هنا AB AC AD BC BD دون CD. أعطِ A1 B2 C3 D3. عند A تظهر 2 و 3، وعند B تظهر 1 و 3، وعند C وD نجد 1 و 2. تكرار 3 عند C وD مسموح؛ المثلث ABC يفرض 3 عاديًا والشاهد يحققه ديناميكيًا.

مربع الماسة يضيف CD لأن C وD يشتركان في A أو B، فيحتاج 4. لكن المركزين ذوي الدرجة 3 لا يطلبان اختلاف كل جيران، بل لونين على الأقل. هذه فجوة أخرى بين أقل التنوع وأقل تلوين المربع.

على K4 بحواف AB AC AD BC BD CD، أربعة ألوان مختلفة صحيحة، وكل رأس يرى ثلاثة ألوان بين جيرانه، أي أكثر من الحد الأدنى 2. صحة الحواف تحتاج 4، فيكون الأقل 4.

مع AB وحدها على A B C D، لون A1 B2 C1 D1. A وB درجتهما 1 فيرى كل منهما لونًا واحدًا، وC وD درجتهما 0 فلا يطلبان أي لون عند الجيران. الشاهد صحيح وديناميكي بلونين، والحافة تمنع 1.

حافتان منفصلتان AB وCD تقبلان A1 B2 C1 D2 كذلك بلونين. وإذا لم توجد أي حافة على الرؤوس الأربعة، فالجميع 1 صحيح والطلب عند الجوار 0؛ الأقل 1 لأن الرؤوس غير فارغة ولا نتركها بلا لون.

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

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

الحصر يفصل التعيينات عن الرسوم وعن الفجوات

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

لكل مدخل حصرنا 15 تقسيمًا إلى فئات ألوان غير فارغة، ووحدنا الأسماء حسب أول ظهور. يجوز هذا هنا لأن الطلب يحصي الألوان المختلفة ولا يقارن أرقامها. بلغ المجموع 960 مرشحًا، منها 337 صحيحًا و 252 يحقق التنوع.

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

الأقل الديناميكي موزع هكذا: رسم واحد عدده 1، وتسعة عددها 2، وخمسون عددها 3، وأربعة عددها 4. مجموع الرسوم 64؛ أما 252 فهو عدد التقسيمات الديناميكية بعد توحيد الأسماء، وقد يملك الرسم عدة تقسيمات.

في 31 مدخلًا تجاوز الأقل الديناميكي الأقل العادي. وفي 22 مدخلًا تجاوز أقل تلوين المربع الأقل الديناميكي. كلاهما عد رسوم، وليس عدد الألوان الزائدة أو عدد التعيينات المرفوضة؛ راجعنا في كل مدخل اتجاه المقارنة.

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

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

النماذج والأعداد حُفظت قبل البحث في المراجع، والصور من قوائمنا دون ادعاء ابتكار التعريف أو الأمثلة المعروفة. C5 وP5 بخمسة رؤوس وC6 بستة خارج الحصر الرباعي. براهين اختلاف الأزواج والنجمة وتكافؤ المربع عند درجة قصوى 2 منفصلة عن العد، ولم نعتمد حدود الرسوم المنتظمة أو نتائج قيم r الأخرى.