الرأس يشهد لنفسه: لماذا يتغير الحل عند ضمه إلى الجوار؟

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

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

• في التلوين الصحيح يختلف لون طرفي كل حافة. [2] أما CF-CN فيطلب عند كل رأس لونًا يظهر مرة واحدة في جواره المغلق، الذي يضم الرأس نفسه وجيرانه؛ العدد اللوني هو أقل عدد ألوان يحقق الشرط، دون إضافة صحة الحواف. [1] نموذجنا محدود وبسيط وغير موجه، بلا حلقات أو أوزان، ورؤوسه غير فارغة.
• نلون كل الرؤوس مرة واحدة، ونحسب الرأس نفسه مرة واحدة في جواره المغلق. قد يشهد لنفسه أو يشهد له جار؛ لا نفرض شاهدًا ذاتيًا للجميع أو لونًا موحدًا للشاهد. التفرد محلي، وقد يتكرر اللون خارج الجوار. الألوان حرة وتبديل الأسماء يحفظ الشرط؛ لا نطلب اختلاف جميع الألوان. المعزول يرى نفسه مرة واحدة فينجح فعليًا، ولا يحتاج إعفاء.
• في K4 بحواف AB AC AD BC BD CD، الجوار المغلق لكل رأس هو الرؤوس الأربعة. A1 B1 C2 D2 يعطي تكراري 2 و 2 فيفشل الجميع، رغم نجاحه في الجوار المفتوح. A1 B2 C2 D2 يعطي تكراري 1 و 3، فيشهد A لنفسه ولجيرانه ويثبت الأقل 2؛ اللون الواحد يفشل بتكرار 4. اتفاق B و C و D مسموح، والصحة العادية تحتاج 4.
• حافة AB مع معزولين C و D بالتلوين A1 B1 C1 D1 تفشل عند طرفي الحافة بتكرار 2، وينجح المعزولان لأن كلًا منهما يرى نفسه مرة. A1 B2 C1 D1 ينجح بأقل 2، والمعزولان يعيدان استخدام 1. أربعة رؤوس بلا حواف تقبل 1 للجميع بأقل 1 لا 0. حافتان منفصلتان AB و CD تقبلان A1 B2 C1 D2 بأقل 2، مقابل 1 للجميع في الجوار المفتوح؛ الحافة مع معزولين لا حل لها في المفتوح.
• أي تلوين صحيح يعطي كل رأس لونَه مرة واحدة في جواره المغلق، لأن جيرانه لا يحملونه؛ لذلك لا يزيد أقل CF-CN على الأقل العادي. لا نضيف الصحة إلى السؤال، وقد يشهد جار بدل الرأس. ولا يوجد ترتيب ثابت للأقل المغلق والمفتوح: المثلث يحتاج 2 مغلقًا و 3 مفتوحًا، وحافتان منفصلتان 2 مغلقًا و 1 مفتوحًا؛ حالات المفتوح بلا حل تفصل عن المقارنة.
• المثلث AB AC BC يقبل 1 1 2 بأقل 2، و C4 يقبل 1 1 2 2، و C5 يقبل 1 1 2 1 2، و C6 يقبل 1 2 1 2 1 2، و P4 يقبل 1 2 2 1، و P5 يقبل 1 2 1 2 1؛ الأقل 2 لكل منها. الماسة AB AC AD BC BD تقبل A1 B2 C2 D2 بأقل 2. النجمة بمركز 1 وكل الأوراق 2 تقبل 2 سواء كان لها ورقتان أو ثلاث أو أربع أو خمس. وجود حافة يستبعد اللون الواحد لأن الجوار المغلق عند طرفها أكبر من 1، لكن نجاح أمثلة اللونين ليس حدًا عامًا.
• حصرنا 64 رسمًا رباعيًا و 960 تقسيمًا بعد تجاهل إعادة أسماء الألوان: 515 تحقق الشاهد المغلق، و 332 المفتوح، و 337 الصحة العادية. اتفق الأقل مع بحث مستقل جرب 309 تعيينات كاملة. كل الرسوم 64 قابلة للحل مغلقًا: رسم بلا حواف يحتاج 1 والبقية 63 تحتاج 2. الأقل أقل من العادي في 23. المفتوح بلا حل في 23، وعلى 41 رسمًا قابلًا للحل فيه لم يقل الأقل المغلق عنه وزاد في 3 رسوم تمثل حافتين منفصلتين باختلاف أزواج الأسماء؛ لا نعمم هذا لأن المثلث الأصغر يبين الاتجاه الآخر. أمثلة الخمسة والستة والمثلث الأصغر خارج الحصر، ونثبت الأقل بشاهد واستبعاد كل عدد أصغر.

الجوار المغلق يضم الرأس نفسه مرة واحدة

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

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

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

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

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

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

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

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

K4 يرفض توزيع 2 و 2 ويقبل 1 و 3

K4 على A B C D له الحواف AB AC AD BC BD CD. كل رأس يجاور الرؤوس الثلاثة الأخرى، فجواره المغلق هو A B C D كاملًا. لا توجد فروق بين مجموعات الجوار المغلق للرؤوس الأربعة.

اختر A1 B1 C2 D2. في الجوار المغلق يظهر 1 مرتين و 2 مرتين. لا لون بتكرار 1، فيفشل كل رأس. الصورة الرئيسية تعرض الرسم كاملًا بحوافه الستة، وتعلن الإخفاق عند الجميع.

كان هذا الشاهد ينجح للجوار المفتوح: عند A و B يظهر 1 مرة و 2 مرتين، وعند C و D يظهر 2 مرة و 1 مرتين. إضافة الرأس نفسه كررت لونه بدل أن تتركه منفردًا، فحوّلت النجاح إلى فشل.

غيّر B إلى 2، فيصبح A1 B2 C2 D2. كل جوار مغلق يرى 1 مرة واحدة عند A، و 2 ثلاث مرات عند البقية. يشهد اللون 1 عند الرؤوس الأربعة؛ A يشهد لنفسه، و B و C و D يجدون الشاهد عند جارهم A.

ثبت الأقل 2: اللون الواحد للجميع يكرر اللون 4 مرات في كل جوار مغلق، فلا شاهد، بينما التعيين السابق ينجح بلونين. لا نعد عدد الرؤوس التي تحمل اللون 2 عائقًا إذا وجد لون آخر بتكرار 1.

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

وليس لازمًا أن يشهد كل رأس بلونه: لون B نفسه يتكرر 3 مرات في جواره المغلق، لكنه ينجح بفضل A1. الصور تلون الرؤوس فقط، والحواف رمادية؛ شرط الشاهد لا يلون الحواف ولا يحذفها.

المعزول ينجح والطرفان يحتاجان لونين

خذ حافة AB ومعزولين C و D. اختر A1 B1 C1 D1. جوار A المغلق هو A1 B1، فيتكرر 1 مرتين ويفشل؛ جوار B هو المجموعة نفسها ويفشل أيضًا.

أما C، فجواره المغلق C1 وحده، فيظهر 1 مرة واحدة ويشهد لنفسه. وكذلك D1 في جواره المنفرد. وجود أربعة رؤوس باللون 1 في الرسم كله لا يفسد تفرد 1 داخل جوار كل معزول.

اختر A1 B2 C1 D1. عند طرفي الحافة يظهر 1 مرة و 2 مرة، وعند كل معزول يظهر 1 مرة واحدة. نجح الجميع؛ لا نحتاج لونًا جديدًا لكل معزول لأنه لا يرى الرؤوس الأخرى.

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

على أربعة رؤوس بلا حواف، يقبل 1 للجميع لأن كل جوار مغلق يتكون من رأس واحد. الأقل 1 لا 0: الرؤوس غير فارغة وكل منها يحتاج لونًا، ووجودها بلا حواف لا يلغي التلوين.

في حافتين منفصلتين AB و CD، ينجح A1 B2 C1 D2 مغلقًا. كل جوار هو طرفا حافة بلونين مختلفين. اللون الواحد يعطي كل رأس تكرار 2 فيفشل، فالأقل 2.

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

كل تلوين صحيح يعطي شاهدًا ذاتيًا

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

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

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

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

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

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

المثلث والدورات تبين أثر ضم النفس

المثلث AB AC BC له جوار مغلق من الرؤوس الثلاثة عند الجميع. الشاهد A1 B1 C2 يعطي تكراري 2 و 1، فيشهد C باللون 2 للجميع، بما فيه نفسه. اللون الواحد يكرر 3 فيفشل، فالأقل 2. في المفتوح، درجة 2 تفرض اختلاف الجارين عند كل رأس، فتختلف الأزواج الثلاثة ويلزم 3.

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

C5 بحواف AB AE BC CD DE يقبل 1 1 2 1 2. عند A و B و C و E يظهر 1 مرتين و 2 مرة، وعند D يظهر 1 مرة و 2 مرتين؛ المهم أن أي ثلاثية من الرأس وجاريه ليست متفقة اللون. نعد الرأس مع الجارين، لا الجارين وحدهما.

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

C6 بحواف AB AF BC CD DE EF يقبل 1 2 1 2 1 2. هذا تلوين صحيح، فيشهد كل رأس بلونه الذي يظهر مرة واحدة في جواره المغلق، واللون الآخر مرتين. الأقل 2 بسبب وجود حافة، مقابل 3 للجوار المفتوح.

P4 بحواف AB BC CD يقبل 1 2 2 1: الجوار عند كل طرف هو لونان مختلفان، وعند كل رأس داخلي تكرارا 2 و 1. ينجح رغم اتفاق BC. P5 بحواف AB BC CD DE يقبل 1 2 1 2 1، وهو صحيح وله شاهد ذاتي عند الجميع؛ الأقل 2 في المسارين بسبب الحافة.

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

تكرار لون الأوراق لا يمنع شاهد المركز

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

في نجمة بورقتين AB AC يقبل A1 B2 C2، وفي ثلاث أوراق AB AC AD يقبل A1 B2 C2 D2. أربعة أوراق AB AC AD AE تقبل A1 B2 C2 D2 E2، وخمس أوراق AB AC AD AE AF تقبل A1 B2 C2 D2 E2 F2.

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

الماسة على A B C D لها AB AC AD BC BD، ولا توجد CD. اختر A1 B2 C2 D2. جوار A و B المغلق هو الرؤوس الأربعة بتكراري 1 و 3، وجوار كل من C و D هو نفسه مع A و B بتكراري 1 و 2. يشهد A1 عند الجميع.

اللون الواحد يفشل بسبب وجود حافة، والشاهد يستعمل 2، فالأقل 2 للماسة مقابل 3 للتلوين الصحيح العادي. هذا الشاهد لا يحقق الصحة لأن BC و BD متفقتان؛ نجاحه يأتي من لون 1 المنفرد في كل جوار مغلق.

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

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

أربعة رؤوس: كل الرسوم لها شاهد مغلق

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

عدّينا ألوان كل جوار مغلق مع الرأس نفسه مرة واحدة، واشترطنا وجود تكرار 1 عند كل رأس؛ نجح 515 تقسيمًا. وللمقارنة على التعيينات نفسها، نجح 332 في الشاهد المفتوح و 337 في صحة الحواف. هذه أعداد تقسيمات، لا أعداد الرسوم أو حلول الأقل فقط.

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

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

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

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

الشاهد المفتوح بلا حل في 23 رسمًا بسبب المعزولات. بين الرسوم 41 القابلة للحل مفتوحًا، لم يقل الأقل المغلق عنه وزاد في 3 رسوم، وهي الحافتان المنفصلتان باختلاف الأزواج المسماة. هذا وصف لحصر الأربعة فقط؛ المثلث يعطي الاتجاه الآخر خارج الحصر.

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