تمييز جميع الرؤوس بألوان الحواف: لماذا تحتاج الدورة السداسية خمسة ألوان؟

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

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

• نلون الحواف تلوينًا صحيحًا، ونطلب اختلاف مجموعتي ألوان الحواف الملتقية عند كل رأسين مختلفين، ونقلل عدد الألوان؛ المقارنة تشمل غير المتجاورين والمكونات المنفصلة، بخلاف شرط مقارنة طرفي كل حافة فقط. [1] [3]
• على C6، ألوان الحواف 1،2،3،1،2،3 تميز طرفي كل حافة، لكنها تعطي الأزواج A D وB E وC F مجموعات متساوية. ألوان 1،2،3،1،4،5 تعطي الرؤوس الستة مجموعات مختلفة وتحقق خمسة أسماء.
• لكل رأس في C6 حافتان مختلفتا اللون. ست مجموعات مختلفة من لونين تتطلب أربعة أسماء على الأقل؛ مع أربعة، يجب استعمال الأزواج الستة كلها. يظهر كل اسم في ثلاثة أزواج، لكن كل حافة بلونه تضيف ظهورين، فيستحيل ذلك؛ خمسة هي الأقل.
• مساران P3 منفصلان يقبلان إعادة اللونين 1 و 2 عند مقارنة المتجاورين، لكن مجموعات الرؤوس تتكرر بين المكونين. الأوراق الأربع تحتاج أسماء حواف مختلفة، فيلزم أربعة ويحققها التعيين 1،2،3،4.
• الحافة التي تشكل مكونًا وحدها تمنع الحل، وكذلك رأسان معزولان لأن مجموعتيهما فارغتان. إذا غابت الحافة المنفردة وكان المعزولون واحدًا أو لا أحد، فإن اسمًا خاصًا لكل حافة يضمن حلًا؛ الرسم ذو رأس واحد بلا حواف يحتاج صفر ألوان.
• المجموعات تقارن أسماء الألوان لا ترتيبها ولا تكرارها أو مجموع أرقامها. {1,4} و{2,3} مختلفتان رغم أن مجموع الأرقام في كل منهما 5؛ تبديل أسماء اللوحة كلها يحفظ الحكم.
• راجعنا 25 نموذجًا و 64 رسمًا من أربعة رؤوس. عشرة رسوم بلا حل، وفي البقية الأقل 2 في 12، و 3 في 32، و 4 في 9، و 5 في رسم واحد. الحصر المقيد يراجع الأمثلة، والبراهين تبين سبب الحدود الدنيا.

كل زوج رؤوس يدخل المقارنة، حتى خارج المكون نفسه

في التلوين العادي للحواف، تأخذ كل حافة لونًا واحدًا وتختلف ألوان الحواف التي تلتقي عند رأس واحد، مع تقليل عدد الألوان المستخدمة. [2]

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

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

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

شرط تمييز المتجاورين وحده يطلب اختلاف مجموعتي ألوان الحواف عند طرفي كل حافة، مع التلوين الصحيح وتقليل عدد الألوان. [3]

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

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

C6: ثلاثة أسماء تكرر المجموعات، وخمسة تعطي شاهدًا

حواف الدورة هي AB BC CD DE EF FA بهذا الترتيب. أعطها الألوان 1،2،3،1،2،3. أي حافتين تلتقيان مختلفتان، فيكون التلوين صحيحًا.

المجموعات هي S[A]={1,3} وS[B]={1,2} وS[C]={2,3}، ثم S[D]={1,3} وS[E]={1,2} وS[F]={2,3}.

عند طرفي كل حافة، تختلف المجموعتان. لكن S[A]=S[D] وS[B]=S[E] وS[C]=S[F]؛ هذه أزواج غير متجاورة، فتفشل قاعدة جميع الرؤوس. لا نضيف حواف بينها عند الرسم.

اللونان على C6 يتناوبان حول الدورة، فيرى كل رأس {1,2}، فلا يكفيان حتى لتمييز المتجاورين. ثلاثة هي الأقل لذلك الشرط، لكنها لا تكفي للشرط العام هنا.

أعط الحواف الألوان 1،2،3،1،4،5 بالترتيب نفسه: AB=1 وBC=2 وCD=3 وDE=1 وEF=4 وFA=5. تظل ألوان كل حافتين تلتقيان مختلفة.

صارت المجموعات S[A]={1,5} وS[B]={1,2} وS[C]={2,3} وS[D]={1,3} وS[E]={1,4} وS[F]={4,5}. الست مختلفة زوجيًا، فيصح التعيين بخمسة أسماء.

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

ستة أزواج ممكنة بأربعة أسماء، لكن عد الظهور يرفضها

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

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

أربعة أسماء تعطي ستة أزواج ممكنة بالضبط: {1,2} و{1,3} و{1,4} و{2,3} و{2,4} و{3,4}. إذا تمايزت المجموعات الستة، وجب استعمال هذه الأزواج الستة كلها، مرة واحدة لكل زوج.

انظر إلى الاسم 1؛ يظهر في {1,2} و{1,3} و{1,4}، أي في ثلاث مجموعات. وبالمثل يظهر كل اسم من الأسماء الأربعة في ثلاث مجموعات.

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

إذن عدد المجموعات التي تحتوي الاسم 1 يساوي ضعف عدد الحواف الملونة 1، فهو زوجي. يستحيل أن يساوي الثلاثة التي فرضها استعمال الأزواج الستة.

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

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

مساران منفصلان: أسماء مشتركة تكرر مجموعات الرؤوس

خذ مساري الحواف AB BC وDE EF، دون أي حافة بين المكونين. أعط AB=1 وBC=2 وDE=1 وEF=2. يصح التلوين عند كل رأس.

مجموعات الأول {1} و{1,2} و{2}، ومجموعات الثاني هي نفسها. لا تتساوى المجموعتان عند طرفي أي حافة، لكن الأزواج A D وB E وC F تفشل في المقارنة العامة.

الأوراق A وC وD وF لكل منها حافة واحدة؛ مجموعة كل ورقة اسم حافتها وحده. لكي تختلف المجموعات الأربع، يجب أن تختلف أسماء الحواف الأربع جميعًا.

الألوان AB=1 وBC=2 وDE=3 وEF=4 تعطي الأوراق {1} و{2} و{3} و{4}، والمركزين {1,2} و{3,4}. المجموعات الست مختلفة، فيصح التعيين بأربعة أسماء، ويثبت حد الأوراق أنها الأقل.

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

معزول واحد مسموح، ومعزولان يمنعان الحل

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

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

معزول واحد مسموح: مجموعته فارغة، ومجموعة أي رأس غير معزول غير فارغة. مثلث AB=1 وBC=2 وCA=3 مع رأس معزول D له مجموعات {1,3} و{1,2} و{2,3} و{}، وكلها مختلفة؛ ثلاثة هي الأقل بحكم حواف المثلث المتلاقية.

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

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

لو تساوت مجموعتا الحواف الملتقية عند رأسين مختلفين، فإما أن تكونا فارغتين، فيكون الرأسان معزولين، أو أن تشتركا في حافة تجمع الرأسين.

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

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

قارن مجموعات الأسماء، لا مجموع أرقامها

المجموعة {1,2} مساوية لـ{2,1}، فالترتيب لا يميز الرأسين. والمجموعتان {1,4} و{2,3} مختلفتان رغم أن لكل منهما اسمين، ومجموع الأرقام في كل منهما 5.

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

على المسارين المنفصلين، الألوان AB=1 وBC=4 وDE=2 وEF=3 تعطي مجموعات الأوراق {1} و{4} و{2} و{3}، ومجموعتي المركزين {1,4} و{2,3}. الست مختلفة رغم تساوي مجموع الأرقام عند المركزين.

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

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

25 نموذجًا و 64 رسمًا: الفرق بين عدد التعيينات وعدد الرسوم

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

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

في أربعة رؤوس، ست حواف ممكنة تعطي 64 رسمًا مسمى. هناك 125 تقسيمًا صحيحًا عاديًا، و 82 تميز المتجاورين، و 81 تميز جميع الرؤوس؛ الشرط العام يفرض الشرط المقصور على المتجاورين أيضًا.

عشرة رسوم من الأربعة رؤوس بلا حل. في البقية الأقل 2 في 12، و 3 في 32، و 4 في 9، و 5 في رسم واحد؛ مجموعها مع العشرة 64. لا يوجد رسم من أربعة رؤوس يقبل صفرًا، لأن الرسم الفارغ له أربعة معزولين.

الفحص ذو الأسماء المحددة جرب 69853 تعيينًا، منها 7663 صحيحة عاديًا، و 5833 تميز المتجاورين، و 5832 تميز جميع الرؤوس. هذه أعداد تعيينات لا أعداد رسوم أو أزمنة تنفيذ.

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

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