تلوين الرؤوس المتناغم: لماذا لا يكفي اختلاف طرفي الحافة؟

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

التلوين المتناغم للرؤوس يشترط اختلاف طرفي كل حافة وعدم تكرار زوج ألوان طرفيها على أي حافة أخرى. المسار A-B-C-D يقبل التعيين 1 2 3 1 بثلاثة، بينما يحتاج C4 أربعة وC6 خمسة. نعد زوج 1 و 2 مثل زوج 2 و 1، لأن الرسم غير موجه.

• التلوين العادي للرؤوس يختلف عند طرفي كل حافة. [2] والمتناغم يضيف ظهور كل زوج ألوان على حافة واحدة على الأكثر، ونبحث عن أقل عدد لألوانه. [1] نموذجنا محدود وبسيط وغير موجه، بلا حلقات أو أوزان، ورؤوسه غير فارغة؛ نلون كل رأس مرة واحدة.
• في P4، التعيين 1 2 1 2 صحيح عاديًا لكنه يكرر الزوج 1 و 2 على AB وBC وCD. التعيين 1 2 3 1 يعطي الأزواج 12 و 23 و 13 دون تكرار؛ عند الرأس ذي الدرجة 2 يجب اختلافه عن جاريه واختلاف الجارين، فيثبت الأقل المتناغم 3 مقابل العادي 2.
• نكتب 12 اختصارًا للزوج 1 و 2؛ الأزواج غير مرتبة، و اتجاه قراءة الحافة لا يصنع زوجًا جديدًا. في كل فئة لون، الرؤوس مستقلة، وبين كل فئتين حافة واحدة على الأكثر؛ قد يغيب زوج بالكامل. في C4، تساوي لون رأسين متقابلين يكرر زوجًا على حافتين، فتحتاج الرؤوس الأربعة ألوانًا مختلفة.
• مع k ألوان لدينا k(k-1)/2 زوجًا مختلفًا، فيجب ألا تتجاوزها الحواف. لذلك P5 ذات أربع حواف تحتاج أربعة، ويحققها 1 2 3 1 4. الحد العددي ضروري لكنه غير كافٍ: ست حواف C6 لا تقبل أربعة رغم وجود ستة أزواج ممكنة.
• لو قبلت C6 أربعة لاستعملت الأزواج الستة مرة واحدة، ولكان لكل لون ثلاث نهايات حواف. لكن كل ظهور للون على رأس الدورة يضيف نهايتين، فيجب أن يكون المجموع زوجيًا. هذا يناقض 3؛ التعيين 1 2 3 1 4 5 يحقق خمسة، فتثبت الأقل 5.
• الشرط يشمل الحواف في المكونات المنفصلة: AB وCD تحتاجان ثلاثة لأن زوج اللونين الوحيد كان سيتكرر؛ A1 B2 C1 D3 شاهد صالح. النجمة بثلاث أوراق تحتاج أربعة والمثلث ثلاثة، والحافة مع رأسين معزولين تحتاج اثنين. بلا حواف ومع أربعة رؤوس نحتاج واحدًا، وكل رأس يظل ملونًا.
• حصرنا 64 رسمًا على أربعة أسماء:960 تقسيمًا مرشحًا و 337 عاديًا و 204 متناغمًا و 123 يحقق الأقل المتناغم؛ ظهر فرق الأقلين في 52 مدخلًا. اتفق فحص الأزواج والفئات في 960 حالة، وراجع البحث المستقل الأقل بتجربة 4179 تعيينًا مسمى كاملًا. احتاج رسم واحد لونًا واحدًا، وستة رسوم لونين، و 31 رسمًا ثلاثة، و 26 رسمًا أربعة. الحصر محدود، وP5 وC6 خارج المجموعة الرباعية.

نلون الرؤوس ونمنع تكرار زوج على حافتين

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

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

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

الأرقام 1 و 2 و 3 أسماء للألوان. إذا تبادلنا أسماءها في جميع المواضع، لم تتغير صحة القيود. والزوج 1 و 2 هو الزوج 2 و 1 نفسه؛ لا نميز بداية ونهاية لأن AB غير موجهة.

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

نختصر زوج اللونين 1 و 2 بالكتابة 12 في قوائم الأزواج، وزوج 2 و 3 بالكتابة 23، وهكذا. هذه كتابة لاسمَي لونين، لا لون اسمه اثنا عشر؛ وعلى الخطوط في الصور تظهر الأرقام مفصولة لتوضيح الزوج.

المسار القصير يكشف فشل التناوب العادي

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

لكن AB تصل 1 و 2، وBC تصل 2 و 1، وCD تصل 1 و 2. الأزواج الثلاثة واحدة بعد إهمال الترتيب؛ لذلك التلوين ليس متناغمًا. لا ينقذنا قلب اسم الحافة BC أو قراءتها من C إلى B.

جرب A باللون 1 وB باللون 2 وC باللون 3 وD باللون 1. تعطي AB الزوج 1 و 2، وBC الزوج 2 و 3، وCD الزوج 1 و 3. جميع الأزواج مختلفة، وجميع الحواف تصل رأسين مختلفين، فيكون التعيين متناغمًا بثلاثة.

لماذا الثلاثة لازمة؟ عند B يوجد الجاران A وC. لو كانا باللون نفسه، لكررت AB وBC الزوج نفسه مع لون B. لذلك يلزم اختلاف A وC، وهما يختلفان أيضًا عن B بالتلوين الصحيح؛ ثلاثة ألوان على الأقل.

مع شاهد الثلاثة ثبت الأقل المتناغم 3 مقابل العادي 2. يجوز أن يشترك A وD في 1: لا توجد AD، والأزواج التي تظهر على الحواف الثلاثة لا تتكرر. فحص تساوي لونين بعيدين يتطلب قائمة الحواف كاملة، لا مجرد طول المسافة بين الاسمين.

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

فئات الألوان تعطي فحصًا مكافئًا

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

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

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

في شاهد المسار ذي الثلاثة، فئة 1 هي A وD، وفئة 2 هي B، وفئة 3 هي C. بين 1 و 2 توجد AB فقط، وبين 2 و 3 توجد BC فقط، وبين 1 و 3 توجد CD فقط. استقلال فئة 1 ووجود الحواف الثلاث المختلفة يجعلان الفحص ناجحًا.

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

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

الدرجة وعدد الأزواج يعطيان حدين ضروريين

عند رأس درجته d، تختلف ألوان جيرانه كلها: تساوي لون جارَين يعيد الزوج نفسه مع لون الرأس على حافتين. وكل جار يختلف عن الرأس نفسه. لذلك تحتاج هذه المجموعة إلى d+1 لونًا على الأقل.

هذا برهان محلي لا يفترض أن الجيران متجاورون فيما بينهم. في النجمة AB AC AD، الأوراق B وC وD غير متجاورة، لكن تكرار لون ورقتين ممنوع بسبب الزوج الذي يظهر مع A.

هناك حد آخر من عدد الحواف: مع k ألوان يساوي عدد الأزواج المختلفة غير المرتبة k(k-1)/2. بما أن كل حافة تستعمل زوجًا مختلفًا، فإن عدد الحواف لا يجوز أن يتجاوز هذا العدد.

على المسار A-B-C-D-E، الحواف AB BC CD DE أربع. ثلاثة ألوان تعطي ثلاثة أزواج فقط، فلا تستوعب أربع حواف متناغمة. أما A1 B2 C3 D1 E4 فتنتج الأزواج 12 و 23 و 13 و 14، وكلها مختلفة؛ فيثبت الأقل 4.

المساران P4 وP5 لهما درجة قصوى 2، لكن الأول يحقق 3 والثاني يحتاج 4. الحد المحلي وحده لا يميز بينهما؛ إضافة حافة واحدة إلى قائمة المسار جعلت حد عدد الأزواج أقوى.

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

الرباعية أربعة والسداسية خمسة

الدورة C4 على A B C D لها AB AD BC CD. إذا كان A وC باللون نفسه، لكررت AB وBC الزوج نفسه. وإذا كان B وD باللون نفسه، لكررت AB وAD الزوج نفسه. المتجاوران مختلفان أصلًا، فتحتاج الرؤوس الأربعة ألوانًا مختلفة.

أعطِ A اللون 1 وB اللون 2 وC اللون 3 وD اللون 4. الأزواج على AB AD BC CD هي 12 و 14 و 23 و 34، ولا يتكرر أي زوج. ثبت الأقل المتناغم 4، بينما التلوين العادي يتناوب 1 2 1 2 بلونين فقط.

السداسية A-B-C-D-E-F-A لها AB AF BC CD DE EF. أقل من أربعة ألوان لا يوفر ستة أزواج مختلفة، لأن ثلاثة تعطي ثلاثة فقط. يبقى السؤال: هل تكفي أربعة التي تتيح ستة أزواج بالضبط؟

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

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

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

لشاهد الخمسة، لون A B C D E F بالترتيب 1 2 3 1 4 5. الأزواج على AB AF BC CD DE EF هي 12 و 15 و 23 و 13 و 14 و 45، وهي ستة مختلفة. أطراف كل حافة مختلفة أيضًا، فيكون التعيين متناغمًا وتثبت الأقل 5.

الصورة الداخلية تعرض C4 مع شاهد أربعة وC6 مع شاهد خمسة، وكل الحواف ظاهرة. تساوي درجات الرؤوس 2 وكون الدورتين زوجيتين لا يحدد الأقل المتناغم وحده؛ نراجع تفرد الأزواج وحدود العد وبنية الدورة.

الحواف المنفصلة تشارك دفتر الأزواج نفسه

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

أعطِ A اللون 1 وB اللون 2 وC اللون 1 وD اللون 3. تستعمل AB الزوج 12 وCD الزوج 13، فيكون التعيين متناغمًا بثلاثة. لونان مستحيلان والشاهد يحقق ثلاثة، فيثبت الأقل 3.

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

في النجمة ذات ثلاث أوراق، أعطِ A اللون 1 وB اللون 2 وC اللون 3 وD اللون 4، فتظهر 12 و 13 و 14 مرة واحدة. المركز وجيرانه يحتاجون أربعة بالبرهان المحلي، فيثبت الأقل 4 مقابل العادي 2.

وفي المثلث AB AC BC، الرؤوس الثلاثة متجاورة اثنين اثنين، فتحتاج 3. التعيين A1 B2 C3 يعطي 12 و 13 و 23 دون تكرار، فيكون الأقل المتناغم والعادي 3.

مع AB وحدها ورأسين C وD معزولين، نختار A1 B2 C1 D1. لا يظهر إلا الزوج 12، فيكفي لونان وهما لازمان عند AB. الرؤوس المعزولة تظل ملونة لكنها لا تضيف ظهورًا لزوج.

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

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

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

لكل مدخل حصرنا تقسيمات الرؤوس إلى فئات غير فارغة، مع توحيد أسماء الألوان حسب أول ظهور. للرؤوس الأربعة 15 تقسيمًا مرشحًا؛ لذلك بلغ المجموع 960 عبر 64 مدخلًا. أسماء ألوان مختلفة للفئات نفسها لا تضيف تقسيمًا آخر.

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

بلغ مجموع التلوينات التي تحقق الأقل المتناغم 123، وظهر فرق الأقل العادي والمتناغم في 52 مدخلًا. تلك أعداد حلول ورسوم مجمعة، لا 123 لونًا في رسم واحد أو 52 حافة في مثالنا.

توزيع المدخلات حسب أقل عدد متناغم هو: رسم واحد يحتاج 1، وستة تحتاج 2، و 31 تحتاج 3، و 26 تحتاج 4. المجموع 64؛ التوزيع يصف هذه القوائم الرباعية المحددة ولا يزعم عد الرسوم غير المتشابهة حتى إعادة تسمية الرؤوس.

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

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

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