تمييز الرؤوس بتكرار ألوان الحواف: لماذا يقبل مسار خمسة رؤوس لونين؟

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

يقبل مسار خمسة رؤوس لونين لأن الحواف بالألوان 1،1،2،2 تعطي المجموعات المتعددة ⟨1⟩ و⟨1,1⟩ و⟨1,2⟩ و⟨2,2⟩ و⟨2⟩ المختلفة جميعًا، بينما اللون الواحد يجعل مجموعتي الطرفين متساويتين.

• نلون الحواف وحدها، ونقارن المجموعة المتعددة لألوان الحواف الملتقية بكل رأس عند جميع أزواج الرؤوس المختلفة؛ نحتفظ بالتكرار ونقلل عدد الألوان. [1]
• شاهد P5 هو AB=1 وBC=1 وCD=2 وDE=2؛ مجموعاته المتعددة ⟨1⟩ و⟨1,1⟩ و⟨1,2⟩ و⟨2,2⟩ و⟨2⟩ تميز الرؤوس الخمسة، واللون الواحد يفشل عند الطرفين.
• الشاهد نفسه يفشل بالمجموعات العادية عند AB وDE، وبالمجاميع العددية عند BE؛ التكرارات ليست مجموعة أسماء بلا تكرار ولا مجموع أرقامها، والعام لا يشترط صحة تلوين الحواف.
• عدد العناصر مع التكرار يساوي درجة الرأس، فتختلف مجموعات الرأسين ذوي الدرجتين المختلفتين تلقائيًا؛ ولدرجة ثابتة نحسب عدد المجموعات المتعددة الممكنة كقيد لازم، لا كضمان للحل.
• مقارنة الجيران وحدهم لا تكفي: في P3 ذي الحافتين باللون 1 تختلف مجموعة الوسط ⟨1,1⟩ عن الطرفين، لكن الطرفين لهما ⟨1⟩، فيفشل الشرط العام.
• مكون الحافة الوحيدة أو أكثر من معزول يمنع الحل؛ عند غيابهما تثبت الألوان الفريدة لكل حافة الوجود، ويقبل الرأس الوحيد بلا حواف لوحة فارغة.
• وافق الفحص المستقل كل التعيينات المسماة حصر الأنماط في 25 نموذجًا و 64 رسمًا من أربعة رؤوس؛ فيها 10 مستحيلة و 42 تحتاج لونين و 12 تحتاج ثلاثة، دون استنتاج صيغة لجميع الرسوم.

المجموعة المتعددة تحفظ مرات ظهور اللون عند الرأس

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

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

نكتب M[A] للمجموعة المتعددة عند A. نستعمل الأقواس ⟨ ⟩ لعرضها، ونكتب الأسماء مرتبة لتسهيل القراءة؛ ترتيب العرض لا يدخل في المقارنة.

مثلًا ⟨1,1,2⟩ و⟨2,1,1⟩ تمثلان المجموعة المتعددة نفسها، لأن كلًا منهما يضم اللون 1 مرتين واللون 2 مرة. أما ⟨1,2,2⟩ فتختلف عنهما في التكرارات.

نطلب M[u]≠M[v] لكل u≠v، بما في ذلك غير المتجاورين وعبر المكونات. لا نضيف حواف بين الرؤوس التي نقارنها، ولا ندخل لون رأس أو ألوان رؤوس مجاورة.

مسار P5 يميز خمسة رؤوس بالحواف 1،1،2،2

خذ المسار A B C D E بالحواف AB BC CD DE، وأعط AB=1 وBC=1 وCD=2 وDE=2.

عند A توجد حافة من اللون 1، فتكون M[A]=⟨1⟩. عند B حافتان كلتاهما من اللون 1، فتكون M[B]=⟨1,1⟩؛ لا نحذف التكرار.

عند C تلتقي حافة من اللون 1 وأخرى من اللون 2، فتكون M[C]=⟨1,2⟩. عند D حافتان من اللون 2، فتكون M[D]=⟨2,2⟩. وعند E حافة واحدة من اللون 2، فتكون M[E]=⟨2⟩.

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

إذا لم تسمح اللوحة إلا بلون واحد، تكون مجموعة كل طرف ⟨1⟩، فيفشل الزوج AE. يستبعد ذلك اللون الواحد، ومع الشاهد يثبت أن الحد الأدنى لونان.

جدول اللوحات يحسب كل تعيينات الحواف، دون حذف الحالات التي تكرر اللون عند رأس. تحت لونين توجد 16 تعيينًا مسمى؛ يميز الجميع تعيينان، ويشكلان نمط أسماء واحدًا.

حذف التكرار أو جمع الأرقام يغير النتيجة

المجموعة العادية في تلوين الحواف العام تجمع أسماء ألوان الحواف عند الرأس دون تكرار، وتطلب اختلاف هذه المجموعات لجميع الرؤوس. [3]

إذا حذفنا التكرار من شاهد P5، حصلنا على {1} و{1} و{1,2} و{2} و{2}. يتساوى A مع B، وD مع E، فيفشل اختبار المجموعات العادية؛ حصر ذلك النموذج أعطى المسار ثلاثة ألوان.

أما جمع أسماء الألوان كأرقام فيعطي A=1 وB=2 وC=3 وD=4 وE=2. يتساوى مجموع B ومجموع E، رغم اختلاف مجموعتيهما المتعددتين ⟨1,1⟩ و⟨2⟩.

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

تلوين الحواف الصحيح يشترط اختلاف لونَي أي حافتين تلتقيان برأس. [2]

شاهد P5 يكرر اللون عند B وعند D، فلا يكون صحيحًا. نحن لا نفرض هذا الشرط في التلوين العام؛ صحة الحواف تشخيص منفصل عن اختلاف المجموعات المتعددة.

أي تعيين يميز المجموعات العادية يميز المتعددة أيضًا؛ فتساوي المتعددة كان سيجعل العادية متساوية. لذلك لا يزيد حد المتعددة عن حد العادية عندما يوجد الحل، وقد يقل كما في P5.

حجم المجموعة المتعددة يساوي الدرجة وتبديل الأسماء يحفظها

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

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

للرؤوس ذات الدرجة 2 تحت لونين، المجموعات المتعددة الممكنة هي ⟨1,1⟩ و⟨1,2⟩ و⟨2,2⟩. هذه ثلاث حالات، وقد استخدمها B وC وD.

لدرجة ثابتة d>0 ولوحة k>0، نوزع d مرات ظهور على k أسماء. بتمثيلها d علامات يفصلها k-1 فاصلًا، يكون عدد التوزيعات binom(k+d-1,d)، أي عدد طرق اختيار d مواضع من k+d-1 موضعًا. كل توزيع يمثل مجموعة متعددة واحدة.

إذا كان عدد رؤوس الدرجة d هو n_d، فيلزم binom(k+d-1,d)≥n_d. القيد لازم لكنه لا يضمن أن الحواف المشتركة تستطيع تحقيق المجموعات المطلوبة؛ مكون الحافة الواحدة يفشل حتى لو أتاحت اللوحة أكثر من مجموعة مفردة.

تبديل أسماء الألوان كلها تبديلًا متقابلًا يحفظ عدد مرات كل اسم، فيحفظ التساوي والاختلاف. تبديل 1 و 2 في شاهد P5 يعطي الحواف 2،2،1،1، ويظل التمييز ناجحًا.

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

في المسار P3، أعط AB=1 وBC=1. تصبح مجموعات A وB وC هي ⟨1⟩ و⟨1,1⟩ و⟨1⟩.

مجموعتا كل زوج متجاور مختلفتان لأن درجتيه مختلفتان، لكن A وC غير متجاورين ولهما المجموعة نفسها. يفشل تمييز الجميع حتى لو نجح فحص الجيران.

إذا كان مكون من الرسم هو الحافة الوحيدة AB ولونها c، فمجموعتا الطرفين كلتاهما ⟨c⟩. لا تصل بهما حافة أخرى تميز أحدهما، فيستحيل النجاح مهما اتسعت اللوحة.

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

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

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

لون فريد لكل حافة يثبت الوجود عند غياب العائقين

افترض عدم وجود مكون من حافة واحدة، ووجود معزول واحد على الأكثر. نعطي كل حافة لونًا فريدًا لا يتكرر على حافة أخرى.

تحدد ألوان المجموعة المتعددة عند كل رأس حوافه الملتقية به بالضبط؛ الأسماء الفريدة لا تترك احتمال خلط حافتين مختلفتين.

إذا تساوت مجموعتا رأسين غير معزولين u وv، فإن كل حافة عند أحدهما يجب أن تكون عند الآخر. في رسم بسيط، الحافة المشتركة الوحيدة الممكنة هي uv.

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

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

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

نقارن التكرارات بعد ترتيبها في فحصين منفصلين

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

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

الحصر الأول يمثل الأسماء بترتيب أول ظهور، ثم يحسب عدد طرق تسمية كل نمط بأسماء اللوحة. لم يستبعد ألوان الحواف المتكررة عند الرأس.

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

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

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

عند لوحات الحدود الدنيا وحدها، جرب 40039 و 1716 تعيينًا؛ نجح تمييز الجميع في 2053 و 648. في رسوم الأربعة يوجد 10 مستحيلة، و 42 تحتاج لونين، و 12 تحتاج ثلاثة.

جدول النماذج يعرض عينة مع شواهدها وحد النموذج السابق بالمجموعات العادية. هذه نتائج محدودة على الرسوم المختبرة، لا صيغة لجميع الرسوم ولا قراءة لنتائج المصدر عن عائلات الدورات؛ المراجعة تحريرية آلية ولا ندعي خبيرًا أو مراجعًا بشريًا.