فئات ألوان متوازنة: لماذا قد تفشل زيادة عدد الألوان؟

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

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

• في التلوين الصحيح يختلف لون طرفي كل حافة. [2] ويكون تلوين الرؤوس متوازنًا إذا اختلف حجما أي فئتي لون بواحد على الأكثر؛ العدد اللوني المتوازن هو أقل k يسمح بذلك. [1] نموذجنا محدود وبسيط وغير موجه بلا حلقات أو أوزان، ورؤوسه غير فارغة.
• لكل رأس لون واحد، ونحسب الفئات المستخدمة غير الفارغة فقط. التوازن لا يطلب التساوي التام: أحجام 2 و 2 و 1 متوازنة، وأحجام 3 و 1 ليست كذلك. عند طلب k فئات على n رأسًا، تكون أحجامها أكبر عدد صحيح لا يتجاوز n/k أو أصغر عدد صحيح لا يقل عنه؛ إذا قسم k العدد n، لزم تساويها كلها.
• في النجمة AB AC AD، يفرض التلوين العادي بلونين A1 B2 C2 D2 وأحجام 1 و 3، فيفشل التوازن. الشاهد A1 B2 C2 D3 يعطي أحجام 1 و 2 و 1 ويثبت الأقل المتوازن 3، مقابل العادي 2. صحة الحواف وحدها لا تفحص أحجام الفئات.
• في نجمة من خمسة رؤوس يكفي 3 متوازنًا، ومن ستة يلزم 4. فئة المركز مفردة، وكل فئة أخرى يجب ألا تزيد على 2، فيلزم n≤2k−1. على الستة، A1 B2 C2 D3 E3 F4 يحقق 1 و 2 و 2 و 1؛ ثلاثة ألوان لا تتسع للأوراق الخمس مع التوازن.
• في K3,3 على جزأي ABC وDEF، تصل كل حافة رأسًا من الجزء الأول بكل رأس من الثاني. لونان يعطيان 3 و 3 فينجحان؛ ثلاثة على ستة رؤوس تفرض فئات حجمها 2، وكل فئة داخل جزء واحد، فلا يمكن تقسيم جزء حجمه 3 إلى فئات ثنائية. أربعة ممكنة بالشاهد 1 1 2 3 3 4؛ الأعداد الممكنة 2 و 4 و 5 و 6، فالنجاح عند k لا يضمن k+1.
• المسار P4 يحتاج 2 متوازنًا بأحجام 2 و 2، وP5 يحتاج 2 بأحجام 3 و 2، وC5 يحتاج 3 بأحجام 2 و 2 و 1، وC6 يحتاج 2 ويقبل 3 أيضًا. المثلث يحتاج 3 وK4 يحتاج 4. حافة AB مع المعزولين C وD تقبل A1 B2 C1 D2 بأحجام 2 و 2؛ المعزول يلون وقد يساعد التوازن. أربعة رؤوس بلا حواف تحتاج 1، لا 0.
• حصرنا 64 رسمًا رباعيًا و 960 تقسيمًا بعد تجاهل إعادة أسماء الألوان:337 صحيحًا، منها 305 متوازنًا. اتفقت مجموعات أعداد الألوان الممكنة مع بحث مستقل جرب 3188 تعيينات كاملة مسماة. أربع حالات رفعت الأقل فوق العادي؛ التوزيع 1:1،2:36،3:26،4:1. لا توجد فجوة في الأعداد الممكنة ضمن الأربعة، لكن مثال K3,3 ذو الستة خارج هذا الحصر.

الصحة والتوازن شرطان مختلفان

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

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

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

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

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

نبحث عن أقل عدد مستخدم يحقق الشرطين، لا أكبر عدد فئات ولا أسوأ ترتيب وصول للرؤوس. ويمكن أن نسأل سؤالًا آخر: هل يوجد حل بعدد محدد k؟ العثور على الأقل لا يعطينا تلقائيًا جواب كل عدد أكبر.

فرق واحد يسمح بأحجام غير متساوية

خذ فئات أحجامها 2 و 2 و 1. الفرق بين أكبرها وأصغرها 1، فهي متوازنة. أما أحجام 3 و 1 فالفرق 2، فتفشل. ولا يكفي أن يكون الفرق صغيرًا في زوج واحد إذا وجد زوج آخر يتجاوز 1.

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

عندما نطلب k فئات غير فارغة على n رأسًا، يساوي مجموع أحجامها n. إذا كان أصغر حجم q، فكل حجم هو q أو q+1. لذلك تكون الأحجام floor(n/k) أو ceil(n/k)، مع عدد الفئات الكبيرة الذي يكمل المجموع.

إذا كان n قابلًا للقسمة على k، صارت الأحجام كلها n/k. لهذا يحتاج التلوين المتوازن بثلاث فئات على ستة رؤوس إلى 2 و 2 و 2، وبفئتين على خمسة إلى 3 و 2؛ لا يطلب المثال الثاني مساواة مستحيلة.

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

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

النجمة صحيحة بلونين لكنها غير متوازنة

النجمة على A B C D لها AB AC AD فقط. المركز A يجاور الأوراق الثلاث، ولا تتجاور الأوراق. يعطي A1 B2 C2 D2 تلوينًا صحيحًا: طرفا كل حافة مختلفان.

لكن فئة 1 هي{A} وحجمها 1، وفئة 2 هي{B,C,D} وحجمها 3. الفرق 2، فلا تتوازن الفئتان. اللونان كافيان عاديًا، لأن الرسم يملك حافة تمنع لونًا واحدًا ويملك الشاهد السابق بلونين.

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

أعطِ A اللون 1، وB وC اللون 2، وD اللون 3. التعيين A1 B2 C2 D3 صحيح، لأن المركز يختلف عن كل ورقة، وتكرار 2 بين B وC مسموح إذ لا توجد BC.

فئات هذا الشاهد{A} و{B,C} و{D} بأحجام 1 و 2 و 1، وأكبر فرق 1. إذن ثلاثة ألوان تكفي متوازنًا؛ مع استبعاد الواحد والاثنين ثبت الأقل 3. الصورة الرئيسية تقارن الشاهدين على الرسم الكامل نفسه.

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

فئة المركز المفردة تحد حجم كل فئة أخرى

في نجمة من n رؤوس، يجاور المركز كل رأس آخر، فتظل فئته مفردة في أي تلوين صحيح. عند التوازن، لا تزيد أي فئة أخرى على 2، وإلا زاد الفرق مع فئة المركز على 1.

إذا استعملنا k فئات، يستوعب المركز رأسًا واحدًا، وتستوعب الفئات k−1 الباقية رأسين لكل منها على الأكثر. لذلك يلزم n≤1+2(k−1)=2k−1. هذا استبعاد نابع من النجمة، وليس حدًا عامًا لكل رسم.

على نجمة من خمسة رؤوس A B C D E وحواف AB AC AD AE، ينجح A1 B2 C2 D3 E3. الأحجام 1 و 2 و 2 متوازنة، بينما لونان يفرضان 1 و 4، فيكون الأقل 3.

على نجمة من ستة رؤوس A B C D E F وحواف AB AC AD AE AF، ثلاثة ألوان لا تستوعب أكثر من 1+2+2=5 رؤوس مع التوازن. لذلك تفشل الثلاثة رغم أن التلوين العادي بلونين ما زال ممكنًا.

الشاهد A1 B2 C2 D3 E3 F4 يعطي أحجام 1 و 2 و 2 و 1، وكل حافة مختلفة الطرفين. أربعة تكفي، وما دونها استبعدناه، فالأقل المتوازن 4.

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

نجاح لونين لا يضمن نجاح ثلاثة

خذ K3,3 بجزأين A B C وD E F. الحواف التسع هي AD AE AF BD BE BF CD CE CF؛ تصل كل رأس في الجزء الأول بكل رأس في الثاني، ولا توجد حواف داخل أي جزء.

التعيين A1 B1 C1 D2 E2 F2 صحيح ومتوازن بأحجام 3 و 3. وجود حافة يمنع لونًا واحدًا، فيكون الأقل المتوازن 2، وهو الأقل العادي أيضًا.

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

لكن كل جزء له 3 رؤوس، ولا يمكن تقسيم الثلاثة إلى فئات كلها بحجم 2. لا تتسع فئة لجزأين، ولا يجوز ترك رأس غير ملون، فثلاثة ألوان متوازنة مستحيلة. برهنّا على كل التلوينات، لا على فشل محاولة واحدة.

الأربعة ممكنة بالشاهد A1 B1 C2 D3 E3 F4. كل لون داخل جزء واحد، والأحجام 2 و 1 و 2 و 1، فالفرق 1. الصورة الداخلية تقارن حل اللونين بحل الأربعة، ولا تدعي وجود حل للثلاثة.

خمسة ممكنة مثل A1 B1 C2 D3 E4 F5 بأحجام 2 و 1 و 1 و 1 و 1، وستة ممكنة بإعطاء كل رأس لونًا مستقلًا. إذن مجموعة الأعداد الممكنة هي{2,4,5,6}، وفيها فجوة عند 3.

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

المعزول يدخل في أحجام الفئات

P4 على A B C D وحوافه AB BC CD يقبل 1 2 1 2 بأحجام 2 و 2، والأقل 2 بسبب الحافة. P5 بحواف AB BC CD DE يقبل 1 2 1 2 1 بأحجام 3 و 2؛ الفرق 1 يكفي، والأقل 2 أيضًا.

C5 بحواف AB AE BC CD DE يقبل 1 2 3 1 2 بأحجام 2 و 2 و 1. لا يقبل لونين عاديًا لأن التناوب حول دورة فردية يعود إلى حافة متفقة الطرفين؛ فالأقل المتوازن 3.

C6 بحواف AB AF BC CD DE EF يقبل 1 2 1 2 1 2 بأحجام 3 و 3، ويقبل 1 2 3 1 2 3 بأحجام 2 و 2 و 2. هذا الرسم يقبل الاثنين والثلاثة، بخلاف K3,3؛ تساوي عدد الرؤوس لا يجعل مجموعات الأعداد الممكنة متطابقة.

المثلث AB AC BC يحتاج ثلاثة ألوان لأن كل زوج متجاور، والفئات المفردة متوازنة. وفي K4 ذي AB AC AD BC BD CD يلزم أربعة بالطريقة نفسها؛ يعطي كل رأس فئة مفردة.

في حافة AB ومعزولين C وD، يمكن أن نعطي A1 B2 C1 D2. الأحجام 2 و 2 صحيحة ومتوازنة؛ لا يفرض المعزول لونًا جديدًا ولا يختفي من عد الفئات. الشاهد يثبت الأقل 2 بسبب الحافة.

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

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

راجعنا كل أعداد الألوان داخل الحصر المعلن

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

يوجد 15 تقسيمًا للرؤوس الأربعة في كل مدخل، والمجموع 960. منها 337 تقسيمًا صحيحًا تختلف فيه أطراف كل حافة، ومنها 305 تتوازن أحجام الفئات أيضًا. عدد التقسيمات غير عدد الرسوم أو عدد ألوان الشاهد.

حسب أقل عدد متوازن، يوجد رسم واحد يحتاج 1، و 36 تحتاج 2، و 26 تحتاج 3، ورسم واحد يحتاج 4؛ المجموع 64. في أربعة رسوم ارتفع الأقل المتوازن فوق العادي؛ كلها نجوم بثلاث أوراق باختيارات مختلفة للمركز بين الأسماء الأربعة.

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

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

لم تظهر فجوة بين الأقل و 4 في الرسوم الرباعية 64. لكن K3,3 ذو الستة يظهر فجوة عند 3، وهو خارج الحصر؛ لا نجعل النتيجة المحدودة برهانًا على رتابة النجاح في كل الرسوم.

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

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