شاهد لوني في الجوار: لماذا يقبل K4 لونين دون صحة الحواف؟

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

في K4، يعطي A1 B1 C2 D2 كل رأس جارًا واحدًا بلونه وجارين باللون الآخر؛ يرى لونًا مرة واحدة في جواره المفتوح، فينجح بأقل 2. اللون الواحد يفشل بتكرار 3 عند الجميع. اتفاق طرفي AB وCD مسموح لهذا السؤال، بينما طلب صحة الحواف يفرض 4. إذا وجد رأس معزول، فلا جار ولا شاهد، ويستحيل الحل تحت شرط كل رأس.

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

شاهد الجوار لا يفرض صحة الحواف

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

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

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

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

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

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

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

K4 يقبل لونين لأن كل رأس يرى شريكه مرة

الرسم الكامل على A B C D له AB AC AD BC BD CD؛ كل رأس يجاور الثلاثة الآخرين. إذا أعطينا الجميع 1، رأى كل رأس اللون 1 ثلاث مرات بلا شاهد وحيد. يفشل اللون الواحد عند الرؤوس الأربعة، لا عند رأس واحد فقط.

اختر A1 B1 C2 D2. جوار A هو B1 C2 D2، فيظهر 1 مرة واحدة و 2 مرتين، فيشهد B باللون 1. وجوار B هو A1 C2 D2، فيشهد A باللون 1 كذلك. اتفاق A و B لا يضيف نسخة ثانية من 1 إلى جوار أحدهما لأننا لا نحسب الرأس نفسه.

وجوار C هو A1 B1 D2، فيظهر 1 مرتين و 2 مرة واحدة، فيشهد D باللون 2. جوار D هو A1 B1 C2، فيشهد C باللون 2. لكل رأس شاهد، رغم اختلاف لون الشاهد بين الزوجين.

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

لكن هذا التلوين ليس صحيحًا بالمعنى المعتاد: طرفا AB كلاهما 1 وطرفا CD كلاهما 2. لو أضفنا صحة الحواف، لأجبرت الأزواج الستة اختلاف ألوان الرؤوس الأربعة، فيلزم 4، ويصلح 1 2 3 4 مع شاهد عند الجميع.

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

ورقة بلون المركز تصلح النجمة بلونين

النجمة على A B C D لها AB AC AD، ولا حواف بين الأوراق. اختر 1 للجميع. كل ورقة ترى جارها A باللون 1 مرة واحدة فتنجح، لكن A يرى 1 ثلاث مرات فيفشل. اتفاق طرفي الحواف ليس وحده سبب الرفض؛ السبب تكرار 3 دون أي 1 عند المركز.

اختر A1 B1 C2 D2. عند A تظهر 1 مرة واحدة عند B، و 2 مرتين عند C وD. يشهد اللون 1 للمركز، وكل ورقة ترى 1 مرة واحدة عند جارها الوحيد A. نجح الشرط عند الرؤوس الأربعة.

اتفاق A و B مسموح هنا. لا نعد A ضمن جواره، فلا يكرر لونَه عند نفسه؛ الجار B وحده يحمل 1 داخل ذلك الجوار. الصورة الداخلية تعرض النجمة كاملة، وتقارنها بشاهد اللون الواحد الفاشل.

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

في نجمة بورقتين AB AC، يقبل A1 B1 C2: عند المركز 1 و 2 مرة واحدة لكل منهما، وكل ورقة ترى 1 مرة واحدة. اللون الواحد يعطي المركز تكرار 2 فيفشل، فيكون الأقل 2، لا 3 كما عند إضافة صحة الحافتين.

في نجمة الأربع أوراق AB AC AD AE، ينجح A1 B1 C2 D2 E2: المركز يرى 1 مرة و 2 ثلاث مرات. وفي نجمة الخمس أوراق AB AC AD AE AF، ينجح A1 B1 C2 D2 E2 F2: المركز يرى 1 مرة و 2 أربع مرات. جميع الأوراق ناجحة.

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

شاهد واحد لا يعني اختلاف جميع الجيران

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

في نجمة الثلاث أوراق، الشاهد 1 1 2 2 يكرر 2 مرتين عند A، فلا يحقق اختلاف كل الجيران. يكفي 1 مرة واحدة في الشاهد الحالي، فيحتاج 2 بدل 3 لتمييز الأوراق الثلاث. لا نخلط وجود لون فريد باشتراط أن تكون كل الألوان فريدة.

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

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

لا نستنتج من ذلك أن مقارنة الأقل مع التلوين الصحيح العادي لها حكم عام لجميع الرسوم. في حافتين منفصلتين، لون واحد ينجح لشاهد الجوار بينما التلوين الصحيح يحتاج 2. نتائج حصر أربعة رؤوس لاحقًا محدودة بذلك الحصر.

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

رأس له جاران: اختلاف الجارين دون الحافتين

عند الدرجة 1 ينجح لون الجار الوحيد تلقائيًا، ولو وافق لون الرأس. عند الدرجة 2، إذا اتفق الجاران ظهر لون واحد مرتين وفشل؛ وإذا اختلفا ظهر كل لون مرة واحدة فنجح. لا يفرض ذلك اختلاف الرأس عن جارَيه.

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

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

P4 بحواف AB BC CD يفرض اختلاف AC وBD، فيقبل 1 1 2 2 بأقل 2. P5 بحواف AB BC CD DE يفرض AC و BD وCE، فيقبل 1 1 2 2 1 بأقل 2؛ الأطراف ذات الدرجة 1 ناجحة، وأي رأس داخلي يستبعد اللون الواحد.

C5 بحواف AB AE BC CD DE يفرض AC AD BD BE CE. هذه القيود تشكل دورة من خمسة رؤوس أيضًا: A C E B D A. لونان يتناوبان حولها ثم يعود اللون نفسه إلى طرفي القيد الأخير؛ لا يكفيان. الشاهد 1 1 2 2 3 يحقق اختلاف الجارين في كل موضع، فيثبت الأقل 3.

C6 بحواف AB AF BC CD DE EF يفرض AC AE BD BF CE DF، فتظهر مجموعتا ACE و BDF كمثلثين في قيود اختلاف الجيران. كل منهما يجبر 3، ويصلح 1 1 2 2 3 3؛ كل رأس يرى لونين مختلفين، رغم اتفاق أزواج متجاورة.

C5 و C6 و P5 والنجمتان من خمسة وستة رؤوس خارج حصر الأربعة. P4 و C4 داخله، ونجمة الورقتين مثال أصغر. هذا التطابق عند الدرجة 2 لا يمتد لدرجة 3: في K4 وافقنا تكرارًا آخر 2 مع شاهد 1.

الماسة تنجح والمعزول يمنع أي حل

المثلث AB AC BC يحتاج 3: عند كل رأس بدرجة 2 يجب اختلاف الجارين، فتختلف الأزواج الثلاثة. الشاهد 1 2 3 يحقق ذلك؛ لم نستنتج الثلاثة من صحة الحواف، وإن تطابقت القيود هنا.

الماسة على A B C D لها AB AC AD BC BD، ولا توجد CD. اختر A1 B2 C1 D2. عند A، الجوار B2 C1 D2 يعطي 1 مرة و 2 مرتين؛ وعند B، الجوار A1 C1 D2 يعطي 2 مرة و 1 مرتين، فيوجد شاهد عند المركزين.

كل من C و D له الجاران A1 وB2 المختلفان، فيظهر كل لون مرة واحدة. نجح الجميع بلونين، رغم اتفاق AC وBD. اللون الواحد يفشل عند رأسي الدرجة 2، فيثبت الأقل 2. إضافة صحة الحواف تمنع هذا الشاهد وتحتاج 3.

في حافتين منفصلتين AB وCD، أعطِ 1 لكل الرؤوس. كل رأس له جار واحد فقط يحمل 1 مرة واحدة، فينجح الجميع. أقل الألوان 1، لا 0 لأن الرؤوس كلها ملونة والرسم غير فارغ. صحة الحواف العادية لو طلبناها لاحتاجت 2.

أما حافة AB مع معزولين C وD، فلا حل لشاهد كل رأس. قد ينجح A و B بأي لون للجار الوحيد، لكن C و D لا يريان أحدًا، ولا يظهر لون بتكرار 1 في جوارهما. زيادة الألوان أو إعطاء المعزول لونًا جديدًا لا تخلق جارًا.

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

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

الحصر يميز عدد الحلول عن الرسوم المستحيلة

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

عدّينا تكرارات ألوان الجوار واشترطنا وجود 1 عند كل رأس دون إعفاء، فنجح 332 تقسيمًا. للمقارنة، نجح 337 في صحة الحواف العادية، و 438 في اختلاف كل الجيران، و 113 في صحة الحواف مع شاهد وحيد عند كل رأس دون إعفاء المعزول. لا نساوي عدد التقسيمات بعدد الرسوم.

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

في الرسم القابل للحل، توقف البحث عند أول شاهد لأقل عدد، بعد استنفاد الأعداد الأصغر. وفي الرسم غير القابل للحل، استنفد أعداد الألوان من 1 إلى 4 دون شاهد. لا يلزم أكثر من أربعة أسماء لتمثيل أي تعيين على أربعة رؤوس؛ إعادة الأسماء تحفظ الشرط.

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

وجدنا 41 رسمًا قابلًا للحل و 23 بلا حل، وكل حالة بلا حل لها رأس معزول. التوزيع: ثلاثة رسوم تحتاج 1، و 38 تحتاج 2، ولا رسم رباعي قابل للحل يحتاج 3 في هذا الحصر. المثلث على ثلاثة رؤوس و C5 و C6 تبين لماذا لا نعمم ذلك.

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

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