قيد المسافة 3: كيف تخلق الحافة زوجًا ثم تمحوه؟

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

لأن القيد يعتمد على أقصر مسافة في الرسم الحالي. الحافتان AB و CD تقبلان 1 للجميع؛ إضافة BC تجعل A و D بمسافة 3، فيحتاجان لونين مختلفين. إضافة AD بعدها تختصر مسافتهما إلى 1، ويصبح C4 بلا أي زوج بمسافة 3 فيعود اللون الواحد صالحًا. نحن نلون أزواج المسافة 3 بالضبط، دون اشتراط اختلاف طرفي كل حافة أصلية.

• ننشئ رسم قيود H بالرؤوس نفسها في الرسم الأصلي G، ونربط فيه رأسين إذا وفقط إذا كانت المسافة بينهما في G تساوي 3 بالضبط. [1] نلون H بحيث يختلف لون طرفي كل حافة فيه، ونبحث عن أقل عدد ألوان يحقق ذلك. [2] نموذجنا محدود وبسيط وغير موجه، بلا حلقات أو أوزان، ورؤوسه غير فارغة وملونة كلها.
• المسافة هي طول أقصر طريق يصل الرأسين؛ وعندما لا يوجد طريق بينهما في مكونين منفصلين تكون المسافة لا نهائية. [3] في نموذجنا غير الموزون نعد حواف الطريق، لا طول الخط في الصورة. المطلوب أقصر مسافة 3، وليس وجود طريق أو سير بطول 3، ولا كل المسافات من 1 إلى 3. في C4 الطريق A B C D طوله 3، لكن الحافة AD تجعل مسافة طرفيه 1 فلا يفرض اختلاف اللون. الألوان أسماء حرة؛ تبديلها يحفظ الشرط، بخلاف عتبة تعتمد على رقم اللون.
• على A B C D، الحافتان AB و CD لا تعطيان زوجًا بمسافة 3؛ H بلا حواف، و 1 للجميع يثبت الأقل 1. إضافة BC تعطي P4 بحواف AB BC CD؛ H يحوي AD فقط، فيفشل 1 للجميع، ويقبل 1 1 1 2 بأقل 2. إضافة AD تعطي C4 بحواف AB AD BC CD وكل المسافات لا تتجاوز 2، فيختفي القيد ويعود الأقل 1. الحواف تزداد، لكن الأقل يتغير 1 ثم 2 ثم 1.
• نميز إضافة حافة إلى G، التي تعيد حساب المسافات، عن إضافة قيد إلى H مع إبقاء القديم. قد تتفق ألوان طرفي حافة أصلية؛ في P4 الشاهد A1 B1 C1 D2 يوافق AB و BC، ويختلف عند AD فقط. والمعزول في H ليس بالضرورة معزولًا في G: B و C في هذا المثال يجاوران في الأصل ولا يملكان قيدًا في H. رقم اللون لا يغير المسافة المطلوبة، ولا تفرض المسافة 0 عند الرأس نفسه قيدًا.
• C6 بحواف AB AF BC CD DE EF له قيود AD BE CF فقط؛1 للجميع يفشل عند الأزواج الثلاثة، و 1 1 1 2 2 2 يحقق الأقل 2. في P5 القيود AD BE مع C بلا قيد، والشاهد 1 1 1 2 2؛ وفي P6 القيود AD BE CF والشاهد 1 1 1 2 2 2؛ وفي P7 نضيف DG ويقبل 1 1 1 2 2 2 1. الأقل 2 لكل منها لأن H يملك حافة؛ لا نضيف أزواج H إلى الحواف الرمادية للرسم الأصلي.
• C7 يعطي H دورة فردية بالترتيب A D G C F B E A؛ التناوب بلونين يفشل، و 1 2 2 2 3 1 1 بالترتيب A إلى G يثبت الأقل 3. C8 يعطي دورة قيود من ثمانية رؤوس، ويقبل 1 2 1 2 1 2 1 2 بأقل 2. C4 و C5 والمثلث والماسة و K4 والنجمتان بثلاث وخمس أوراق لا مسافة 3 فيها، فالأقل 1 رغم الحواف الأصلية. حافة مع معزولين والحافتان المنفصلتان والرسم الخالي تقبل 1 للجميع؛ الأقل 1 لا 0، ولا نخلط غياب القيد بإلغاء تلوين الرؤوس.
• حصرنا 64 رسمًا رباعيًا و 960 تقسيمًا بعد تجاهل إعادة أسماء الألوان؛900 تحقق قيد المسافة 3 و 337 صحة الحواف الأصلية. اتفق الأقل مع بحث منفصل جرب 98 تعيينات كاملة. ترتيبات الرؤوس الأربعة 24، وكل مسار وعكسه يعطيان الحواف نفسها؛ لذلك لدينا 12 مسارًا P4 مسمى، فيها قيد واحد وأقل 2؛ والبقية 52 بلا قيد وأقل 1. كان الأقل أقل من العادي في 51 ولم يزد في هذا الحصر، دون تعميم المقارنة. تحقق المسافات والقوائم بفحص آخر؛ أمثلة الأحجام الأخرى خارج الحصر، ومنها C7 الذي يحتاج 3. لإثبات الأقل نعرض شاهدًا ونستبعد كل عدد أصغر، مع إعادة حساب H عند تغيير G.

نلون رسم القيود بعد حساب أقصر المسافات

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

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

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

نلون الرؤوس كلها مرة واحدة، حتى الرأس الذي لا ينتهي عنده أي قيد في H. ونحسب عدد الألوان المستعملة، لا أكبر رقم مكتوب على لون. الأسماء قابلة للتبديل لأن الشرط يفحص اتفاقها واختلافها فقط؛ الرقم 3 يصف المسافة، وليس عتبة لون يحمل الرقم 3.

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

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

حافتان ثم مسار ثم دورة: الأقل 1 ثم 2 ثم 1

ثبت الرؤوس A B C D، وابدأ بالحافتين AB و CD فقط. داخل كل مكون مسافة الطرفين 1، وبين المكونين لا يوجد طريق. لا زوج بمسافة 3، لذلك H بلا حواف، ويقبل A1 B1 C1 D1. الأقل 1 لأن الرؤوس غير فارغة وملونة.

أضف BC، دون حذف AB أو CD. صار الرسم المسار P4 بحواف AB BC CD. مسافة A إلى D هي 3 عبر A B C D، ولا طريق أقصر. الأزواج AB و BC و CD مسافتها 1، و AC و BD مسافتها 2؛ إذًا القيد الوحيد هو AD.

إعطاء الجميع 1 يفشل عند AD. اختر A1 B1 C1 D2: طرفا القيد مختلفان، فينجح. القيد الواحد يمنع لونًا واحدًا، والشاهد يعطي لونين، فيثبت الأقل 2؛ لا نحتاج اختلافًا بين A و B أو B و C في هذا السؤال.

أضف AD إلى الحواف الثلاث. صار C4 بحواف AB AD BC CD؛ الأزواج المتجاورة مسافتها 1 والمتقابلان AC و BD مسافتهما 2. لا مسافة 3 بعد الإضافة، فيصبح H بلا حواف ويقبل 1 للجميع بأقل 1.

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

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

طريق بثلاث حواف لا يكفي إذا وجد اختصار

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

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

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

إضافة قيد إلى H مع إبقاء قيوده القديمة لا تجعل حلًا مرفوضًا ينجح: الحل الجديد يحقق القيود القديمة كذلك. أما إضافة حافة أصلية إلى G فتعيد حساب H، وقد تزيل قيدًا قديمًا، كما رأينا مع AD.

في P4 الرأس B بلا حواف في H، لكنه يجاور A و C في G. والرأس C كذلك يجاور B و D في الأصل ولا ينتهي عنده قيد المسافة 3. نقول إنه بلا قيد في H، ولا نسميه معزولًا في الرسم الأصلي.

قد يتساوى الأقل في سؤالين وتختلف التعيينات المسموحة. P4 العادي يحتاج 2 أيضًا، لكنه لا يقبل A1 B1 C1 D2 بسبب AB و BC. شاهد المسافة 3 ينجح لأنه يختلف عند AD؛ تساوي العددين لا يثبت تساوي الشرطين.

C6 يطلب اختلاف ثلاثة أزواج متقابلة

خذ C6 على A B C D E F بحواف AB AF BC CD DE EF. الجاران مسافتهما 1، ومن بين كل رأسين تفصل بينهما خطوة إضافية تكون المسافة 2، أما المتقابلان فتفصل بينهما 3 خطوات في الاتجاهين حول الدورة.

أزواج المسافة 3 هي AD و BE و CF فقط. لذلك H يتكون من ثلاث حواف منفصلة على الرؤوس الستة نفسها، ولا نطلب أن تختلف كل مجموعة من الجيران أو أن يظهر لون منفرد في جوار رأس.

التعيين 1 1 1 1 1 1 يفشل عند الأزواج الثلاثة. الشاهد 1 1 1 2 2 2 ينجح: A و D مختلفان، و B و E مختلفان، و C و F مختلفان. وجود قيد يمنع اللون الواحد، والشاهد يعطي لونين، فيثبت الأقل 2.

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

P5 بحواف AB BC CD DE يعطي القيود AD و BE فقط، و C بلا قيد. الشاهد 1 1 1 2 2 ينجح بأقل 2. في P6 بحواف AB BC CD DE EF تكون القيود AD BE CF، ويقبل 1 1 1 2 2 2 بأقل 2.

P7 بحواف AB BC CD DE EF FG يضيف القيد DG إلى AD BE CF. الشاهد 1 1 1 2 2 2 1 ينجح: A و D مختلفان و D و G مختلفان، والزوجان BE و CF مختلفان. الأقل 2 هنا أيضًا بسبب وجود حافة في H.

C7 يحتاج ثلاثة رغم أن الحصر الرباعي لا يطلبها

C7 بحواف AB AG BC CD DE EF FG له أزواج المسافة 3 التالية: AD AE BE BF CF CG DG. يمكن ترتيبها دورة في H بهذا المسار المغلق: A D G C F B E A. هذه دورة من سبع حواف، لا ترتيب الحواف الأصلية حول C7.

لو استعملنا لونين صحيحين في H، لتناوب اللون عند عبور كل حافة. بعد السبع يعود السير إلى A بلون مخالف للون بدايته، وهذا مستحيل للرأس نفسه. فلا يكفي لونان، واللون الواحد مرفوض بالحافة أيضًا.

بالترتيب A B C D E F G، اختر 1 2 2 2 3 1 1. على ترتيب دورة H تصبح الألوان 1 2 1 2 1 2 3، ثم يعود الطرف إلى 1؛ يختلف طرفا كل قيد. نجح بثلاثة واستبعدنا الأصغر، فالأقل 3.

C8 بحواف AB AH BC CD DE EF FG GH له قيود AD AF BE BG CF CH DG EH. تتصل كدورة من ثمانية رؤوس عند تتبع القفز ثلاث مواضع. الشاهد 1 2 1 2 1 2 1 2 يختلف عند كل زوج منها، ويثبت الأقل 2 لأن H يملك حافة.

هذه الدورات ليست حصرًا عامًا لكل حجم أو لكل رسم. C7 يبين تحديدًا أن نجاح لون أو لونين على أربعة رؤوس لا يجعل لونين حدًا عامًا. C5 و C6 و C7 و C8 والمسارات الأكبر ليست ضمن الرسوم الرباعية التي سنعدها.

الحواف الكثيرة قد تترك H بلا قيد

C5 بحواف AB AE BC CD DE لا تتجاوز أي مسافة فيه 2، لذلك لا زوج بمسافة 3 ويكفي 1 للجميع. والمثلث AB AC BC كل مسافاته بين الرؤوس المختلفة 1، فيقبل 1 في سؤالنا رغم حاجة التلوين العادي إلى 3.

K4 بحواف AB AC AD BC BD CD له ست حواف أصلية وكل زوج مسافته 1. H بلا حواف، فالأقل 1 هنا مقابل 4 للصحة العادية. وفي الماسة AB AC AD BC BD، دون CD، الزوج CD مسافته 2 والبقية 1؛ الأقل 1 كذلك مقابل 3 عاديًا.

النجمة ذات المركز A والثلاث أوراق بحواف AB AC AD لها مسافة 1 بين المركز والورقة ومسافة 2 بين كل ورقتين. لا مسافة 3، فيقبل 1 للجميع. ونجمة الخمس AB AC AD AE AF لها القاعدة نفسها، فالأقل 1 رغم كثرة الأوراق.

على حافة AB مع معزولين C و D، الزوج AB مسافته 1 والأزواج بين المكونات بلا طريق. لا يوجد قيد في H، فيقبل A1 B1 C1 D1 بأقل 1. لا نطالب المعزول بجار أو بشاهد لون؛ نلونه مع البقية بالفعل.

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

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

اثنا عشر مسارًا رباعيًا تعطي القيد الوحيد

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

جربنا 15 تقسيمًا لألوان الرؤوس في كل رسم بعد تجاهل إعادة أسماء الألوان، فكان المجموع 960. التبديل يحفظ الاتفاق والاختلاف هنا لأن رقم اللون لا يحدد عتبة؛ لا نستخدم قاعدة تلوين التعبئة التي تعتمد على رقم كل لون.

نجح 900 تقسيم في شروط H، و 337 في صحة الحواف الأصلية G على التعيينات نفسها. هذه أعداد تقسيمات صالحة، لا عدد الرسوم ولا عدد حلول الأقل وحده. لا نبدل موضع القيد من H إلى G عند إجراء المقارنة.

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

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

هناك اثنا عشر مسارًا P4 على الأسماء الأربعة: ترتيبات الرؤوس الأربعة 24، لكن كل طريق وعكس ترتيبه يعطيان الحواف نفسها، فنقسم على 2. كل منها يملك قيدًا واحدًا وأقل 2؛ الرسوم 52 الباقية H فيها بلا حواف وأقل 1.

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

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