ترتيب الرؤوس يرفع ألوان المسار: كيف نفحص الأسوأ؟

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

على المسار AB BC CD، ترتيب A B C D يعطي 1 2 1 2، بينما A D B C يعطي في ترتيب الرؤوس A B C D الألوان 1 2 3 1. في الخطوة الأخيرة يرى C اللونين 1 و 2 فيأخذ 3. أقصى درجة 2 تمنع أكثر من 3، فيكون عدد غروندي للمسار 3 رغم أن أقل تلوين عادي 2.

• التلوين الصحيح يختلف عند طرفي كل حافة. [2] الاختيار الأول First-fit يعالج الرؤوس بترتيب محدد ويختار أصغر لون متاح؛ Grundy Coloring يسأل عن أكبر عدد يستعمله عبر جميع ترتيبات الرؤوس. [1] نموذجنا محدود وبسيط وغير موجه بلا حلقات أو أوزان، ورؤوسه غير فارغة؛ لكل رأس لون واحد، والحواف اتصالات.
• نستخدم الأعداد الموجبة 1 ثم 2 ثم 3، ونعد المستخدمة فعلًا دون فراغات. عند الدور ننظر إلى الجيران السابقين فقط. على P4، الترتيب A B C D يعطي لونين، وA D B C يعطي A1 D1 B2 C3؛ الدليل خطوة بخطوة، وليس مجرد تعيين صحيح بثلاثة.
• كل رأس بلون i في تلوين ناتج يرى جميع الألوان الأصغر 1 إلى i-1 بين جيرانه، ولا نطلب الأكبر. وبالعكس، تلوين صحيح يحقق هذا الشرط يمكن إنتاجه بمعالجة الرؤوس حسب ألوانها تصاعديًا. رأس باللون i يحتاج على الأقل إلى i-1 من الجيران، فيحد الأكبر أقصى درجة زائد 1 وعدد الرؤوس؛ P4 يحقق 3.
• أرقام الألوان ليست أسماء حرة: تحويل 1 2 3 1 إلى 3 2 1 3 يبقي التلوين صحيحًا، لكن A3 لا يرى 1 وD3 لا يرى 2، فيفشل الشرط. ولا نطلب شاهدًا لكل لون يرى جميع الألوان الأخرى؛ P4 بتلوينه 1 2 3 1 يحقق غروندي 3، لكنه يفشل شهود الفئات للون 1، وأكبرها 2.
• الرباعية C4 عددها 2: ثلاثة ألوان تتكرر فئة متقابلة، وكل احتمال للون المتكرر يترك رأسًا دون لون أصغر مطلوب. النجمة عددها 2 رغم حد أقصى درجة زائد 1 المساوي 4؛ إذا كان المركز 1 أخذت الأوراق 2، وإذا تجاوز 1 لم تسمح الأوراق إلا 1، فيأخذ المركز 2. الحد ضروري وليس شاهد وجود.
• P5 وC5 وC6 عددها 3، والمثلث 3 وK4 أربعة، والماسة دون CD ثلاثة. الحافة مع معزولين وحافتان منفصلتان عددهما 2، والرؤوس بلا حواف 1؛ المعزول يأخذ 1 ولا يُترك بلا لون. الشواهد والبراهين تخص القوائم المحددة، ولا نفرض اتصال ترتيب الرؤوس.
• حصرنا كل 64 رسمًا على أربعة رؤوس:22656 تعيينًا خامًا، منها 4800 تستعمل كل اسم في لوحة مرتبة، و 2849 صحيحة و 267 تحقق شرط الأصغر. اتفق الأكبر مع تجربة كل 1536 ترتيبًا للرؤوس؛12 مدخلًا تتجاوز الأقل العادي. التوزيع 1: واحد،2:28،3:34،4: واحد؛ لا نوحد الأسماء، وC5 وP5 وC6 خارج الحصر.

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

التلوين الصحيح يجعل طرفي كل حافة مختلفين. [2] وفي First-fit يصل كل رأس حسب ترتيب محدد ويأخذ أصغر لون متاح؛ يسأل Grundy Coloring عن أكبر عدد ألوان يحتاجه هذا الاختيار عبر جميع ترتيبات الرؤوس. [1]

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

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

إذا لم نجد جارًا سابقًا ملونًا، نختار 1. إذا رأينا 1 دون 2 نختار 2، وإذا رأينا 1 و 2 دون 3 نختار 3. وجود لون 3 وحده لا يجبر 4؛ ما دام 1 غائبًا فهو الأصغر المتاح.

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

الترتيب قائمة تحتوي كل رأس مرة واحدة. يجوز أن نبدأ برأسين غير متجاورين، ولا نشترط أن يجاور الرأس التالي مجموعة الرؤوس السابقة. لذلك سنستعمل A ثم D في المسار رغم عدم وجود AD.

الألوان المستخدمة تبدأ من 1 بلا فجوات؛ ظهور i يعني أن ألوان 1 إلى i-1 سبق أن ظهرت عند جيرانه. إذن أعلى رقم مستخدم يساوي عدد الألوان المستعملة، ولا نضيف لونًا غير محمول على رأس إلى الحساب.

ترتيبان على المسار نفسه يعطيان لونين وثلاثة

المسار P4 على A B C D له AB BC CD فقط. مع الترتيب A B C D، يأخذ A1 لأنه الأول؛ يرى B عند A اللون 1 فيأخذ 2؛ يرى C عند B اللون 2 فيأخذ 1؛ يرى D عند C اللون 1 فيأخذ 2. الألوان في ترتيب الرؤوس 1 2 1 2.

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

يصل B فيجد A1 جارًا سابقًا، بينما C لم يصل، فيأخذ B2. أخيرًا يصل C وجاراه B2 وD1 سابقان؛ اللونان 1 و 2 محجوبان، فيأخذ C3.

النتيجة بحسب أسماء الرؤوس A B C D هي 1 2 3 1، أما تسلسل ما اختير زمن المعالجة فهو A1 ثم D1 ثم B2 ثم C3. فصل الترتيبين يمنع أن نقرأ 1 2 3 1 بوصفه خطوات الوصول نفسها.

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

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

الصورة الرئيسية تعرض المسار كاملًا في اللوحتين، دون تغيير رؤوسه أو حوافه. تختلف قائمة الوصول فقط، ويبين الجدول خطوات الترتيب A D B C والألوان المحجوبة لحظة كل خطوة.

كل رقم يرى الأرقام الأصغر، وهذا يفسر الأكبر

إذا أخذ رأس اللون i بالاختيار الأول، لم يكن أي لون أصغر متاحًا لحظة وصوله. لذلك له جار سابق بكل لون من 1 إلى i-1؛ وتبقى هذه الألوان عند الجيران في التلوين النهائي.

لا نطلب أن يرى جميع الألوان الأكبر. في توزيع P4 ذي 1 2 3 1، A1 وD1 لا يحتاجان لونًا أصغر أصلًا. B2 يرى 1 عند A، وC3 يرى 2 عند B و 1 عند D. ينجح كل رأس في طلب الألوان الأصغر.

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

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

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

الرأس باللون i يحتاج عددًا من الجيران المختلفين لا يقل عن i-1، لأن كل جار يحمل لونًا واحدًا. إذن i لا يتجاوز درجته زائد 1، وأعلى رقم لا يتجاوز أقصى درجة في الرسم زائد 1. كذلك لا يتجاوز عدد الرؤوس لأن كل لون مستخدم يحتاج رأسًا.

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

تبديل أسماء الألوان قد يفسد إمكان الترتيب

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

بدل 1 و 3 في توزيع المسار 1 2 3 1، واترك 2. تحصل على 3 2 1 3، وهو صحيح عاديًا على AB BC CD، لكن A3 لا يجاور إلا B2 فيفتقد 1، وD3 لا يجاور إلا C1 فيفتقد 2.

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

الفحص هنا يخص كل رأس وكل لون أصغر، لا شاهدًا واحدًا لكل فئة يرى جميع الألوان الأخرى. في 1 2 3 1، فئة 1 تضم A وD، وهما لا يريان 2 و 3 معًا عند رأس واحد. لذلك يفشل شرط شهود الفئات، رغم نجاح شرط غروندي.

المقال السابق أثبت أن أكبر عدد مع شهود الفئات على P4 هو 2؛ هنا أثبتنا غروندي 3 على الرسم نفسه. والتوزيع 1 2 3 1 كامل الأزواج أيضًا، لأن 12 و 23 و 13 موجودة، لكن اكتمال الأزواج وحده لا يضمن طلب كل رقم أصغر عند كل رأس.

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

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

الرباعية والنجمة تكشفان حدًا لا يتحقق

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

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

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

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

النجمة AB AC AD درجتها القصوى 3، فيعطي الحد 4. لكن إن حمل المركز A اللون 1، كانت كل ورقة أعلى منه وترى 1 فقط، فلا تأخذ إلا 2 بالاختيار الأول أو بشرط الألوان الأصغر.

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

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

المعزول والمثلث والدورات تفصل الأمثلة

في P5 على A B C D E بالحواف AB BC CD DE، التوزيع 1 2 3 1 2 صحيح؛ B2 يرى A1، وC3 يرى B2 وD1، وE2 يرى D1. A1 وD1 لا يحتاجان لونًا أصغر. معالجة الفئات بترتيب A D B E C تنتجه، وأقصى درجة 2 تمنع أكثر من 3.

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

السداسية على A B C D E F بحواف AB AF BC CD DE EF تقبل 1 2 3 1 2 3. B2 وE2 يريان 1، وC3 وF3 يريان 1 و 2، وA1 وD1 لا يطلبان أصغر. ترتيب A D B E C F يحققها؛ الدرجة 2 تثبت أن غروندي 3.

المثلث AB AC BC يعطي A1 B2 C3 بالترتيب A B C، لأن كل رأس لاحق يرى كل من سبقه. وكذلك K4 بحواف AB AC AD BC BD CD يعطي 1 2 3 4 بالترتيب A B C D؛ عدد الرؤوس يمنع زيادة العدد.

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

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

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

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

نحصر أرقامًا مرتبة وكل ترتيبات الرؤوس

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

لكل مدخل جربنا الألوان 1 إلى k لكل k من 1 إلى 4 على الرؤوس الأربعة. عدد التعيينات الخام 1+16+81+256=354، وعلى المدخلات 64 بلغ إجمالي التعيينات 22656. يشمل ذلك تعيينات لا تستعمل كل اسم في اللوحة المفترضة، فلا نسميها كلها تلوينات بلوحة k مستخدمة.

بعد اشتراط استعمال جميع الأسماء 1 إلى k، يبقى 75 تعيينًا مرتبًا لكل مدخل، وإجمالي 4800. لا نوحد أسماء الألوان حسب أول ظهور:1 2 3 1 و 3 2 1 3 كلاهما يدخل الفحص مستقلًا لأن أحدهما يحقق شرط الأصغر والآخر لا.

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

وبطريقة مستقلة، جربنا جميع ترتيبات الرؤوس الأربعة، وعددها 24 لكل مدخل وإجمالي 1536. أجرينا الاختيار الأول خطوة بخطوة، واتفق أكبر عدد ألوان مع أكبر عدد استخرجناه من فحص التعيينات المرتبة في كل المدخلات 64.

عدد غروندي موزع هكذا: واحد عدده 1، و 28 عددها 2، و 34 عددها 3، وواحد عدده 4. وفي 12 مدخلًا كان الأكبر أعلى من الأقل العادي؛ المسار P4 المثال الذي شرحنا فجوة 2 إلى 3 عليه.

الأعداد 22656 و 4800 و 2849 و 267 تحصي تعيينات في مراحل مختلفة، بينما 1536 يحصي ترتيبات وصول. ليست عدد تقسيمات بعد حذف أسماء الألوان، ولا عقد بحث جزئية أو ضمان سرعة؛ لا نقارنها مباشرة بحصر المقالات التي وحدت أسماء الألوان.

حفظنا النماذج والأعداد قبل البحث في المراجع، والصور من قوائمنا دون ادعاء ابتكار التعريف أو الأمثلة المعروفة. P5 وC5 بخمسة رؤوس وC6 بستة خارج الحصر الرباعي. براهين التكافؤ والدرجة والرباعية والنجمة منفصلة عن العد، ولم نعتمد نتائج التعقيد أو النسخ الجزئية والمتصلة من التلوين.