التلوين الجمعي للرؤوس: لماذا تكفي قيمتان لحافة واحدة؟

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

تكفي قيمتان لحافة AB لأن إعطاء A العدد 1 وB العدد 2 يجعل مجموع جيران A هو 2 ومجموع جيران B هو 1، بينما الحد 1 يجعل المجموعين 1 فيفشل.

• نعطي كل رأس عددًا صحيحًا موجبًا من 1 إلى k، ونطلب اختلاف مجموع أعداد الجيران عند أي رأسين متجاورين، ونقلل الحد k؛ الجمع هنا يستبعد الرأس نفسه. [1]
• على الحافة AB، التعيين A=1 وB=2 يعطي O[A]=2 وO[B]=1، فينجح؛ مع k=1 يكون العددان 1 والمجموعان 1، فيلزم حد 2.
• إضافة عدد الرأس إلى مجموع جيرانه تعطي 3 عند طرفي AB في الشاهد نفسه؛ هذا حساب للجوار المغلق يغير السؤال، فلا نستخدمه للحكم على التلوين الجمعي هنا.
• على المسار AB BC، أعداد الرؤوس كلها 1 تعطي المجاميع 1،2،1، فتنجح الحافتان بحد 1، رغم فشل التلوين الصحيح العادي لأن كل طرفين لهما العدد نفسه.
• في تمييز الجيران بأوزان الحواف، الحافة المنفردة مستحيلة لأن طرفيها يجمعان وزن الحافة نفسه؛ أما هنا فلكل طرف عدد مستقل يراه الطرف الآخر.
• حد 1 ينجح بالضبط عندما تختلف درجتا طرفي كل حافة؛ وكل رسم بسيط له حل بإعطاء الرؤوس قوى مختلفة للعدد 2، مع السماح بأي عدد من المعزولين، واصطلاح حد موجب 1 للرسم الخالي من الحواف.
• حصرنا 25 نموذجًا و 64 رسمًا من أربعة رؤوس؛ الفحص المنفصل جرب 5393 تعيينًا للنماذج و 1477 للرسوم، ووافق الحدود والشواهد؛ توزيع الحدود للرسوم هو 17 بحد 1 و 42 بحد 2 و 4 بحد 3 ورسم واحد بحد 4.

الأعداد على الرؤوس، والمجموع يخص الجيران دون الرأس نفسه

يعرّف المصدر تلوينًا بأعداد صحيحة موجبة من 1 إلى k على الرؤوس، بحيث يختلف مجموع الأعداد المعطاة للجيران عند أي رأسين متجاورين؛ المطلوب أصغر k. [1]

نفترض رسمًا بسيطًا غير موجه، فيه رأس واحد على الأقل. نكتب O[A] لمجموع أعداد الرؤوس المتصلة بـA بحافة، دون إضافة عدد A نفسه؛ هذا هو الجوار المفتوح.

نحسب عدد كل جار مرة، حتى لو حمل جار آخر العدد نفسه. إذا كان لرأس جاران بالعدد 1، فمجموعه 2، ولا نحول الأعداد المتكررة إلى مجموعة تختزلها إلى 1.

نفحص O[u]≠O[v] لكل حافة uv أصلية. لا نضيف شرطًا بين رأسين غير متجاورين أو رأسين من مكونين منفصلين، ولا نضع أوزانًا على الحواف.

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

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

الحافة AB: تبادل رؤية العددين يجعل المجموعين 2 و 1

نبدأ بحافة واحدة AB، ونعطي A=1 وB=2. يمكن إضافة رأسين معزولين C وD بالعدد 1؛ لا يغيران أي جوار عند A أوB.

الجار الوحيد لـA هو B، فيكون O[A]=2. والجار الوحيد لـB هو A، فيكون O[B]=1. حافة AB تقارن 2 مع 1، فتنجح.

مجموع C ومجموع D يساويان 0 لأنهما بلا جيران. تساويهما مسموح: لا توجد حافة CD، ولا حافة منهما إلى A أوB.

مع k=1، يجب أن يحمل A وB العدد 1. عندئذ O[A]=O[B]=1، فيفشل الشرط على الحافة الوحيدة؛ لا يوجد تعيين آخر داخل هذا الحد.

نجح شاهد بحد 2 وفشل الحد الموجب الأصغر 1، إذن الحد الأدنى للحافة الواحدة هو 2، مع المعزولين أو دونهم.

إضافة عدد الرأس تغير المجموعين إلى 3 و 3

في الشاهد A=1 وB=2، الحساب المطلوب يستبعد الذات: A يرى 2 وحده، وB يرى 1 وحده. لذلك المجموعان مختلفان.

إذا أضفنا عدد الرأس نفسه، صار المجموع عند A هو 1+2=3، وعند B هو 2+1=3. هذا حساب للجوار المغلق، وليس مجموع الجيران المفتوح المستخدم هنا.

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

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

المسار يقبل أعدادًا كلها 1، والتلوين الصحيح العادي لا يقبلها

في التلوين الصحيح العادي للرؤوس، يجب أن يختلف لونا كل رأسين متجاورين؛ هذا شرط على لوني الطرفين نفسيهما. [2]

المسار P3 له الحافتان AB وBC فقط. إذا كانت A=1 وB=1 وC=1، فمجاميع الجيران عند A B C هي 1،2،1، لأن B له جاران والرأسان الآخران لكل منهما جار واحد.

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

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

للدورة C4 بحواف AB BC CD DA، التعيين A=1 وB=1 وC=1 وD=2 يعطي المجاميع 3،2،3،2. كل حافة تقارن قيمتين مختلفتين، وتساوي الرأسين المتقابلين مسموح.

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

في الرسم الكامل K4، كل رأس يرى الرؤوس الثلاثة الأخرى. إذا كتبنا T لمجموع أعداد الرؤوس الأربعة، فمجموع جيران كل رأس هو T ناقص عدد ذلك الرأس.

كل رأسين في K4 متجاوران؛ اختلاف مجموعيهما يعادل اختلاف عدديهما. نحتاج أربعة أعداد مختلفة، فيلزم k≥4، والشاهد A=1 وB=2 وC=3 وD=4 يعطي المجاميع 9،8،7،6، فيثبت الحد 4.

أوزان الحواف مسألة أخرى: الحافة المنفردة لا تميز طرفيها

في مسألة أوزان الحواف، نعطي كل حافة عددًا من مجموعة أعداد صحيحة، ونطلب اختلاف مجموع أوزان الحواف الملتقية عند كل رأسين متجاورين؛ نختار للمقارنة المجموعة الموجبة من 1 إلى k. [3]

إذا كانت AB مكونًا وحدها، فوزنها هو الحد الوحيد في مجموع A وفي مجموع B. مهما كان الوزن، يتساوى مجموعا الطرفين، فلا يوجد حل في مسألة أوزان الحواف.

في مقالنا الحالي، العددان المعطيان لـA ولـB مستقلان، والحافة رمادية بلا وزن. A يجمع عدد B، وB يجمع عدد A، فينجح الشاهد 1 و 2.

على المسار P3، تنجح المسألتان بحد 1: أعداد الرؤوس كلها 1 هنا، أو وزنا الحافتين كلاهما 1 هناك، فتكون المجاميع 1،2،1. تشابه النتيجة لا يجعل موضع العدد واحدًا.

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

حد 1 يرتبط بالدرجات، وقوى 2 تعطي شاهد وجود لكل رسم

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

هذا يفسر نجاح P3 وفشل الحافة AB والدورة C4 عند الحد 1. تكرار الدرجة عند رأسين غير متجاورين مسموح، كما لا يفرض المعزول مقارنة جديدة.

لإثبات وجود حل في أي رسم بسيط، نعطي رؤوسه قوى مختلفة للعدد 2، مثل 1 و 2 و 4 و 8. مجموع قوى مختلفة للعدد 2 يحدد المجموعة التي جُمعت تحديدًا فريدًا.

إذا كان u وv متجاورين، فإن u جار لـv، لكنه ليس جارًا لنفسه في الرسم البسيط. لذلك مجموعتا الجيران المفتوحتان مختلفتان، وتكون مجموعاتهما العددية مختلفة تحت تعيين قوى 2.

على الدورة، الأعداد A=1 وB=2 وC=4 وD=8 تعطي المجاميع 10،5،10،5، فتنجح الحواف الأربع. هذا شاهد وجود بحد 8، بينما شاهدنا السابق يحقق الحد الأصغر 2.

المعزولون لا يفسدون البرهان لأننا لا نقارنهم بغيرهم. ولا نستنتج من شاهد الوجود حدًا ثابتًا لجميع الرسوم أو أنه يحقق أقل حد.

الحصر يجرب الأعداد الفعلية على الرؤوس ويحفظ تكرارها في الجمع

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

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

فحص منفصل بطريقة حاصل الضرب جرب 5393 تعيينًا عبر الحدود المختبرة للنماذج؛ 837 منها يحقق الشرط الجمعي، و 266 من هذه التعيينات يحقق التلوين الصحيح العادي أيضًا. الفحص العادي تشخيص إضافي، لا شرط قبول هنا.

من الحواف الست الممكنة على أربعة رؤوس، حصلنا على 64 رسمًا مسمى. الحدود الدنيا هي 1 في 17 رسمًا، و 2 في 42، و 3 في 4، و 4 في رسم واحد؛ لا توجد حالة مستحيلة.

الفحص المنفصل جرب 1477 تعيينًا لهذه الرسوم عبر الحدود المختبرة؛ 383 منها جمعي صالح، و 163 من هذه التعيينات صحيح عادي أيضًا. هذه أعداد تعيينات، لا أعداد رسوم أو أزمنة تنفيذ.

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

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