جار مشترك يفرض لونين: لماذا قد يتساوى طرفا الحافة؟

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

الحافة وحدها لا تجبر اختلاف الطرفين في شرط الجار المشترك. في الرباعية AB AD BC CD، الأزواج المطلوبة AC وBD فقط؛ الشاهد A1 B1 C2 D2 يفرقها ويستعمل أقل 2، رغم اتفاق طرفي AB وCD. أما في المثلث، فطرفا أي حافة يشتركان في الرأس الثالث، فيجب اختلافهما. القرار يأتي من وجود الجار المشترك، لا من الحافة وحدها.

• في Injective Coloring، يجب أن يختلف لون أي رأسين لهما جار مشترك؛ أقل عدد ألوان يحقق ذلك هو العدد اللوني لهذا الشرط. [1] لا نضيف شرط اختلاف طرفي كل حافة، وهو شرط التلوين الصحيح العادي. [2] نموذجنا محدود وبسيط وغير موجه بلا حلقات أو أوزان، ورؤوسه غير فارغة.
• الشرط مكافئ لاختلاف ألوان كل جيران أي رأس بعضها عن بعض. لا نطلب اختلاف لون الرأس نفسه عن جيرانه إلا إذا دخل زوج منهما في قيد جار مشترك آخر. الدرجة 0 أو 1 لا تولد زوجًا من الجيران، لكن كل رأس يلون مرة واحدة. الألوان حرة، وتبديل أسمائها لا يغير القبول.
• في C4 ذي AB AD BC CD، أزواج الجار المشترك هي AC وBD فقط. التناوب 1 2 1 2 صحيح عاديًا لكنه يفشل لأن A وC يتساويان، وكذلك B وD. الشاهد 1 1 2 2 يفرق الزوجين فينجح بأقل 2، رغم اتفاق طرفي AB وCD. لا يكفي فحص الحواف الأصلية.
• في النجمة AB AC AD، كل زوج من الأوراق B وC وD له المركز A جارًا مشتركًا، فيلزم ثلاثة ألوان للأوراق. A1 B1 C2 D3 يحقق ذلك بأقل 3؛ المركز يمكنه لون B نفسه لأن A وB لا يملكان جارًا مشتركًا. التلوين العادي A1 B2 C2 D2 يفشل لهذا الشرط.
• يميز المصدر بين اختلاف الرأسين عند المسافة 2 تحديدًا، واختلافهما عند وجود جار مشترك، وتلوين المربع الذي يفرق كل رأسين عند مسافة لا تتجاوز 2. [3] قد يتجاور رأسان ولهما جار مشترك أيضًا؛ المثلث مثال، فلا نحذف ذلك الزوج من الفحص.
• تلوين المربع يضيف اختلاف طرفي كل حافة أصلية إلى أزواج الجار المشترك. لذلك يحتاج مربع الرباعية والنجمة 4، بينما شرطنا يحتاج 2 و 3؛ المثلث يحتاج 3 للجار المشترك، والماسة بلا CD تحتاج 4 رغم كفاية 3 عاديًا. C5 يحتاج 3 بالشاهد 1 1 2 2 3، لأن أزواج AC AD BD BE CE تشكل دورة فردية. C6 يحتاج 3 بالشاهد 1 1 2 2 3 3، لأن القيود مثلثان على ACE وBDF. P4 يحتاج 2 بالشاهد 1 1 2 2، وP5 يحتاج 2 بالشاهد 1 1 2 2 1. حافة مع معزولين وحافتان منفصلتان بلا زوج جار مشترك، فيكفي 1 رغم الأقل العادي 2؛ أربعة رؤوس بلا حواف تحتاج 1، وK4 يحتاج 4.
• حصرنا 64 رسمًا رباعيًا و 960 تقسيمًا بعد تجاهل إعادة أسماء الألوان:337 صحيحًا عاديًا، و 438 تحقق الجار المشترك، و 210 تحقق المربع. اتفق الأقل مع بحث مستقل في كل جيران الرأس جرب 1611 تعيينات كاملة مسماة. في 9 رسوم كان الأقل هنا دون العادي، وفي 10 فوقه، وفي 52 دون المربع؛ التوزيع 1:10،2:27،3:20،4:7. P5 وC5 وC6 خارج الحصر الرباعي.

الجار المشترك يحدد الزوج المطلوب

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

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

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

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

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

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

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

الرباعية تسمح بتساوي طرفي حافتين

C4 على A B C D له AB AD BC CD. الرأس A له الجاران B وD، فيجبر اختلاف B وD. والرأس B له A وC، فيجبر اختلاف A وC. يعيد C وD الزوجين نفسيهما، فلا نضيف قيودًا جديدة.

إذن أزواج الجار المشترك هي AC وBD فقط. A وB المتجاوران لا يملكان جارًا مشتركًا هنا: جيران A هم B وD، وجيران B هم A وC، ولا رأس في التقاطع. لذلك لا تلزم الحافة AB باختلافهما لهذا السؤال.

التلوين 1 2 1 2 صحيح عاديًا؛ كل حافة مختلفة الطرفين. لكنه يجعل A وC باللون 1، وهما يشتركان في B وD، ويجعل B وD باللون 2، وهما يشتركان في A وC. يفشل الزوجان المطلوبان.

اختر بدلًا منه A1 B1 C2 D2. يختلف A وC، ويختلف B وD. عند A ترى الجارين B1 وD2، وعند B ترى A1 وC2، وعند C ترى B1 وD2، وعند D ترى A1 وC2؛ كل جوار متعدد الرأسين مميز الألوان.

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

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

ثلاث أوراق تحتاج ثلاثة ألوان والمركز قد يشاركها

النجمة على A B C D لها AB AC AD. كل زوج من B وC وD له A جارًا مشتركًا، فتظهر القيود BC BD CD. الأوراق لا تتجاور أصلًا، لكن شرط الجار المشترك يفرق ألوانها جميعًا.

هذه ثلاثة رؤوس يجب أن يختلف كل زوج منها، فيلزم ثلاثة ألوان على الأقل. إعطاء الأوراق اللون 2 جميعًا في A1 B2 C2 D2 ينجح عاديًا على الحواف، لكنه يفشل عند المركز لأن ثلاثة جيران أخذوا اللون نفسه.

اختر A1 B1 C2 D3. جيران A يحملون 1 و 2 و 3، وكل ورقة لها جار واحد فقط هو A1؛ لا يوجد زوج داخل جوار الورقة يكرر اللون. تحقق الشرط عند الرؤوس الأربعة.

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

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

لا تستبدل اختلاف الجميع بمجرد أن ترى بين ثلاثة جيران لونين. A1 B2 C3 D2 يكرر لون B وD عند المركز، فيفشل هنا رغم وجود اللونين 2 و 3 بين الجيران؛ العدد المختلف يجب أن يساوي عدد الجيران.

الجار المشترك ليس شرط المسافة الأقصر 2

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

في المثلث AB AC BC، A وB متجاوران والمسافة بينهما 1، لكنهما يشتركان في C. وينطبق الأمر على الزوجين الآخرين. لذلك يجبر شرط الجار المشترك الألوان الثلاثة، حتى لو لم يوجد زوج مسافته الأقصر 2.

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

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

في الرباعية، الحواف AB AD BC CD مع القيود AC BD تغطي الأزواج الستة، فيحتاج المربع 4. وفي النجمة، حواف المركز مع القيود BC BD CD تفعل الشيء نفسه؛ المربع يحتاج 4، بينما سؤالنا سمح للمركز بلون ورقة واحتاج 3.

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

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

الدورة الفردية تظهر في قيود الخماسية

C5 على A B C D E له AB AE BC CD DE. أزواج الجار المشترك AC AD BD BE CE، وهي دورة على الترتيب A C E B D A. يمكن قراءة كل زوج مباشرة من جاري رأس في الدورة الأصلية.

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

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

C6 بحواف AB AF BC CD DE EF يعطي القيود AC AE BD BF CE DF. تتكون مثلثات القيود على A C E وعلى B D F؛ لا زوج مطلوب بين المجموعتين. كل مثلث يجبر 3، ويمكن استعمال الأسماء الثلاثة نفسها في كليهما.

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

P4 بحواف AB BC CD له القيود AC BD فقط، فيقبل 1 1 2 2 ويحتاج 2 بسبب وجود قيد. وP5 بحواف AB BC CD DE له AC BD CE، فيقبل 1 1 2 2 1؛ قيوده مسار على A C E وحافة على B D، فتحتاج 2.

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

الحافة وحدها قد لا تفرض لونين

خذ حافة AB ورأسين معزولين C وD. كل جوار حجمه 0 أو 1، فلا يوجد زوج رأسين يشتركان في جار. إذن إعطاء الجميع 1 يحقق الشرط، والأقل 1 لأن الرؤوس غير فارغة.

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

وحافتان منفصلتان AB وCD لا تولدان زوج جار مشترك أيضًا؛ كل رأس له جار واحد. اللون 1 للجميع صالح لهذا الشرط، مع أن التلوين العادي يحتاج 2.

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

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

تجبر الماسة 4 لهذا الشرط، بينما عاديًا يكفي A1 B2 C3 D3 بأقل 3؛ الزوج غير المتجاور CD لا يختلف عاديًا لكنه يجبر الاختلاف هنا. وفي K4 الكامل، كل زوج له جار مشترك أيضًا، فيلزم 4.

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

قارنا أزواج الجار المشترك بفحص كل الجيران

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

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

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

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

حسب الأقل، عشرة رسوم تحتاج 1، و 27 تحتاج 2، و 20 تحتاج 3، و 7 تحتاج 4؛ المجموع 64. في 9 رسوم كان الأقل دون العادي، وفي 10 فوقه. هذا يؤكد غياب ترتيب ثابت بين العددين داخل الأمثلة نفسها.

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

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

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