التلوين الدائري: لماذا قد يفسد تبديل مواضع الألوان الحل؟

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

قد يفسد تبديل مواضع الألوان الحل لأن اختلاف الموضعين لا يضمن فصلًا 1 على كل حافة؛ على C5، تبديل A وB يجعل المسافة الدائرية BC=1/2، فيفشل. [1]

• موضع واحد لكل رأس على دائرة محيطها Z؛ أقصر مسافة حولها بين طرفي كل حافة 1 على الأقل. نريد أقل محيط، ونقتصر على رسوم بسيطة غير موجهة فيها حافة. [1]
• على C5، المواضع A=0 وB=1 وC=2 وD=1/2 وE=3/2 على دائرة محيطها 5/2 تحقق أقصر مسافة 1 لكل حافة. خمسة مواضع لا تعني أن القيمة خمسة.
• التبديل بين A وB يجعل أقصر مسافة BC نصف وحدة، فيفشل. أما تدوير جميع المواضع معًا فيحفظ المسافات؛ تغيير الأسماء فقط مع إبقاء المواضع يحفظ الحل أيضًا.
• كل نافذة دائرية بطول 1 تضم رؤوسًا مستقلة، بشرط أن تشمل بدايتها وتستثني نهايتها. على C5 تسع رأسين على الأكثر؛ عد أطوال ظهور الرؤوس فيها يعطي 5≤2Z، فيثبت أن 5/2 هو الأقل.
• تجميع المواضع في الفترات [0,1) و[1,2) وما بعدها يعطي تلوينًا عاديًا صحيحًا بعدد لا يتجاوز تقريب Z إلى الأعلى. هذا شاهد، وليس ضمانًا أن كل دائرة صحيحة تعطي أقل عدد عادي؛ على أمثلتنا المثلى تتساوى القيم بعد التقريب.
• C7 تعطي محيطًا 7/3 وأقل عادي 3. والتلوين الكسري يوزع أوزانًا على مجموعات مستقلة، بينما الدائري يعطي كل رأس موضعًا واحدًا؛ التلوين الدوري للوجوه مسألة ثالثة مختلفة. [3] [4]
• راجعنا 22 نموذجًا و 63 رسمًا من أربعة رؤوس فيها حواف، مع 466 قيدًا لأسعار المجموعات المستقلة. في هذا الحصر، القيمة 2 في 40 رسمًا، 3 في 22، 4 في واحد. الفحص المقيد لا يثبت مساواة الدائري والعادي لكل رسم.

نقيس المسافة على دائرة الألوان، لا داخل الرسم

التلوين العادي للرؤوس يشترط اختلاف لونَي طرفي كل حافة، ويقلل عدد الألوان. [2]

في التلوين الدائري، نختار موضعًا لكل رأس ضمن الفترة [0,Z)، ونطلب على كل حافة أن يكون الفرق المطلق بين الموضعين بين 1 وZ-1. نبحث عن أصغر محيط Z. [1]

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

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

نقتصر على رسوم بسيطة غير موجهة فيها حافة على الأقل. تلك الحافة وحدها تفرض Z≥2، لأن مسافتيها حول الدائرة كل منهما 1 على الأقل. نحتفظ بالرؤوس المعزولة ونعطيها مواضع، لكنها لا تضيف قيد حافة. لا نقرر هنا اصطلاح قيمة الرسم الذي بلا حواف.

على C5: كل حافة تفصلها وحدة، والمحيط خمسة على اثنين

خذ الدورة بالحواف AB BC CD DE AE فقط. ضع A عند 0، وB عند 1، وC عند 2، وD عند 1/2، وE عند 3/2، على دائرة محيطها 5/2. كل المواضع داخل [0,5/2).

في AB وBC وDE الفرق المباشر 1، والمسافة الأخرى 3/2. في CD وAE الفرق المباشر 3/2، لكن الطريق الذي يعبر نهاية الدائرة طوله 1. لذلك أقصر المسافتين 1 على الحواف الخمس كلها.

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

يمكن كتابة المثال بأعداد صحيحة على دائرة طولها k=5، مع فصل d=2: الأرقام عند A B C D E هي 0،2،4،1،3. بقسمة الأرقام وطول الدائرة على 2 نحصل على المواضع السابقة ومحيط k/d=5/2.

إذا ضاعفنا k وd وكل الأرقام معًا، نحصل على 10 و 4 والأرقام 0،4،8،2،6. النسبة 10/4=5/2 والمواضع بعد القسمة لم تتغير. لا تضاعف طول الدائرة وحده ثم تدع الفصل والأرقام ثابتة وتدعي أنه الوصف نفسه.

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

بدل موضعي A وB: الحافة BC تفشل

بعد التبديل، يصبح A عند 1 وB عند 0، ويبقى C عند 2 وD عند 1/2 وE عند 3/2. لا تزال المواضع الخمسة مختلفة، ولذلك لا يوجد تساوٍ في الألوان على أي حافة.

لكن على BC، المسافة المباشرة 2، والمسافة عبر إغلاق الدائرة 1/2. أقصرهما 1/2، وهي دون الفصل المطلوب 1. وعلى AE المسافة الأقصر 1/2 أيضًا. إذن التعيين عادي صحيح بأسماء مختلفة، لكنه ليس حلًا دائريًا صحيحًا بالمحيط نفسه.

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

تدوير جميع المواضع بمقدار واحد، مع رد النتائج إلى [0,Z)، يحفظ المسافتين بين كل زوج. مثلًا إضافة 1/2 في المثال تعطي A=1/2 وB=3/2 وC=0 وD=1 وE=2؛ لا يزال الحل صحيحًا.

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

نافذة طولها وحدة تمنع أي محيط أصغر

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

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

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

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

إذن 5≤2Z، ومنه Z≥5/2. هذا يمنع كل محيط حقيقي أصغر، وليس فقط بضعة كسور اخترنا تجربتها. وبالترتيب الصحيح السابق، تثبت القيمة 5/2.

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

على C5 ضع السعر 1/2 عند كل رأس؛ كل مجموعة مستقلة تسع اثنين، فأسعارها لا تتجاوز 1، ومجموع الأسعار 5/2. الأسعار شهادة حد أدنى؛ لا تحل محل مواضع الألوان، ولا تعني أن كل رأس يقع عند 1/2.

الفترات الصحيحة تعطينا ألوانًا عادية

من أي ترتيب دائري صحيح، اجمع الرؤوس التي مواضعها في [0,1)، ثم [1,2)، وهكذا حتى نهاية الدائرة. الرؤوس في الفئة نفسها فرق مواضعها أقل من 1، فلا تتجاور. إذن كل فئة لون عادي صحيح.

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

على المثال الخماسي، تقع A وD في الفئة الأولى، وB وE في الثانية، وC في الثالثة. الألوان عند A B C D E هي 1،2،3،1،2؛ تختلف على كل حافة. أقل عدد عادي 3، لأن التناوب بلونين يفشل عند إغلاق الدورة الفردية.

لا تعني القاعدة أن تقريب أي محيط صحيح يعطي الأقل العادي. ضع الرؤوس الخمسة عند 0،1،2،3،4 على دائرة محيطها 5؛ هذه دائرة صحيحة، وتقريب محيطها 5، لكن الأقل العادي للدورة 3. يجب تمييز شاهد صالح من شاهد أمثل.

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

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

C7 تعطي سبعة على ثلاثة، والتعريف الكسري مختلف

على C7 بالحواف AB BC CD DE EF FG AG، استخدم دائرة طولها 7 وفصلًا 3، والأرقام 0،3،6،2،5،1،4 عند A B C D E F G. بقسمتها على 3 يكون المحيط 7/3؛ أقصر مسافة على كل حافة 1.

أي مجموعة مستقلة على C7 تسع ثلاثة رؤوس على الأكثر: أربعة رؤوس مستقلة تحتاج أربعة فواصل حول الدورة، أي ثمانية رؤوس. السعر 1/3 عند كل رأس يعطي مجموع 7/3، ويصح على كل مجموعة مستقلة؛ حجة النافذة تثبت أن المحيط 7/3 هو الأقل. والتلوين العادي يحتاج 3.

في الجدول نتائج 22 رسمًا فيها حواف. لكل رسم مواضع صحيحة وشهادة أسعار مستقلة تساوي محيطها. المثلث قيمته 3، والنجمة ثلاثية الأوراق 2، وK4 قيمته 4. الرؤوس المعزولة في الأمثلة باقية في التعيين، وليست حواف جديدة.

التلوين الكسري يضع أوزانًا حقيقية غير سالبة على مجموعات مستقلة، ويغطي كل رأس بوزن 1 على الأقل مع تقليل المجموع. [3]

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

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

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

الحصر المقيد يراجع الشواهد، ولا يستبدل البرهان

في أربعة رؤوس، هناك ست حواف ممكنة، فينتج 2^6=64 رسمًا مسمى. استبعدنا الرسم بلا حواف من نطاق المقال، فبقي 63. القيمة 2 في 40 رسمًا، 3 في 22، 4 في K4 وحده؛ مجموع قيود المجموعات المستقلة غير الفارغة 466.

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

راجعنا دوران الأرقام بكل إزاحة صحيحة ممكنة في أوصاف الدوائر، ومضاعفة الأرقام والطول والفصل معًا. وفحصنا تبديل A وB على C5: أقصر مسافة BC تنخفض إلى نصف وحدة.

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

حصرنا أيضًا 3125 تعيينًا على C5 مع طول 5 وفصل 2؛ المقبول 10. وعلى C7 مع طول 7 وفصل 3، حصرنا 823543 تعيينًا، والمقبول 14. وعلى C5 مع طول 4 وفصل 2، لا حل بين 1024 تعيينًا. هذه أعداد تعيينات، وليست أزمنة تنفيذ.

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

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