لونان لكل رأس لا يعنيان تكرار تلوين عادي مرتين: على الدورة الخماسية، يمكن الاكتفاء بخمسة أسماء بدل ستة. نختار لكل رأس مجموعة من لونين مختلفين، ونمنع أي اسم مشترك بين رأسي كل حافة. سنكتب المجموعات، ثم نعد مواضع ظهور الأسماء لنثبت أن خمسة هي الأقل. [1]
الخلاصة السريعة
تحتاج الدورة الخماسية خمسة أسماء عند طلب لونين مختلفين لكل رأس، لأن كل اسم يظهر على رأسين على الأكثر، بينما يلزم عشرة ظهورات، ويوجد تعيين صحيح يستخدم خمسة أسماء.
- التلوين المتعدد يعطي كل رأس b أسماء مختلفة من مجموعة مشتركة، حيث b عدد صحيح موجب ثابت، ويمنع أي اسم مشترك بين رأسي كل حافة؛ نريد أقل عدد صحيح k من الأسماء. [1]
- على C5، نعطي A المجموعة {1,2}، وB {3,4}، وC {1,5}، وD {2,3}، وE {4,5}. لا يشترك متجاوران في اسم، وكل رأس يأخذ اسمين بالضبط.
- أكبر مجموعة مستقلة على C5 فيها رأسان؛ لذلك خمسة أسماء ضرورية لعشرة ظهورات. تكرار تلوين عادي ذي ثلاثة أسماء مرتين يعطي ستة، وهو صحيح لكنه ليس الأقل.
- عند طلب ثلاثة أسماء لكل رأس في C5، نضيف إلى المثال أسماء جديدة للمجموعات AC وBD وE، فنستخدم ثمانية؛ الحد الأدنى هو تقريب 15/2 إلى الأعلى.
- على C7، اللونان لكل رأس يحتاجان خمسة أسماء أيضًا، والثلاثة لكل رأس تحتاج سبعة؛ في الدورتين نعطي بناءً وحدًا أدنى لأي b موجب، لا للأعداد الصغيرة فقط.
- عدد الأسماء k يختلف عن النسبة k/b، والتلوين الكسري يستخدم أوزانًا حقيقية للمجموعات المستقلة؛ تلوين b المسيطر تلوين عادي يطلب شاهدًا لكل فئة ويعظم عدد الألوان. [3] [4]
- فحصنا 23 نموذجًا مع الطلب من 1 إلى 6، و 64 رسمًا من أربعة رؤوس مع الطلب نفسه. الفحوص تراجع مجموعات الأسماء والحواف وشهادات الأقل، ولا تثبت صيغة عامة لكل رسم.
كل رأس يأخذ b أسماء مختلفة، ولا يشترك المتجاوران في أي اسم
التلوين المتعدد يختار لكل رأس مجموعة فيها b أسماء من لوحة مشتركة، ويشترط أن تكون مجموعتا رأسي كل حافة منفصلتين؛ يسمى أيضًا b-fold أو (a:b) إذا كان حجم اللوحة a. [1]
نثبت b مسبقًا بوصفه عددًا صحيحًا موجبًا، ثم نبحث عن أصغر عدد صحيح k من أسماء الألوان. أمثلتنا رسوم بسيطة غير موجهة ولها رأس واحد على الأقل؛ كل رأس يأخذ b أسماء مختلفة بالضبط، لا اسمًا مكررًا b مرات.
في التلوين العادي، يأخذ كل رأس لونًا واحدًا، ويختلف لونَا طرفي كل حافة مع تقليل عدد الألوان. [2]
عندما b=1، يعود نموذجنا إلى هذا الشرط. وعندما b=2، قد يشترك رأسان غير متجاورين في اسم أو اسمين، لكن وجود اسم واحد مشترك على حافة يكفي لإفساد التعيين.
نعد الأسماء المستخدمة في الرسم كله، لا عدد خانات الألوان على الرؤوس. يمكن إعادة استعمال الاسم عند رؤوس مستقلة، ولا يزيد k بكل ظهور جديد للاسم نفسه.
ليس ترتيب الأسماء على دائرة جزءًا من القيد؛ تبديل أسماء اللوحة كلها تبديلًا واحدًا يحفظ انفصال المجموعات. كما أننا لا نفرض لكل رأس قائمة مسبقة بأسماء مسموحة: مجموعته هي ما نختاره له من اللوحة المشتركة.
الرأس المعزول يأخذ b أسماء أيضًا. إذا خلا الرسم من الحواف، نعطي جميع الرؤوس المجموعة نفسها ونحتاج b أسماء؛ لا تصبح القيمة صفرًا لمجرد غياب الحواف.
خمسة أسماء تكفي للونين على الدورة الخماسية
خذ الرؤوس A B C D E والحواف AB BC CD DE AE فقط. التعيين هو A={1,2} وB={3,4} وC={1,5} وD={2,3} وE={4,5}.
لكل رأس اسمان مختلفان. على AB لا يوجد اسم مشترك بين {1,2} و{3,4}؛ وعلى BC تنفصل {3,4} عن {1,5}. تنفصل المجموعات أيضًا على CD وDE وAE، كما يبين جدول الحواف.
يمكن قراءة التعيين من جهة الأسماء: الاسم 1 يظهر على AC، و 2 على AD، و 3 على BD، و 4 على BE، و 5 على CE. الأزواج الخمسة مجموعات مستقلة، ويظهر كل رأس في اثنين منها بالضبط.
ظهور الاسم 2 عند A وD لا يضيف الحافة AD إلى الدورة. كذلك ظهور الاسم 3 عند B وD لا يضيف BD؛ هذه مجموعات استعمال للألوان، وليست حواف جديدة في الرسم.
التعيين يثبت أن خمسة أسماء تكفي. لإثبات أنها الأقل، لا تكفي تجربة عدة لوحات أصغر؛ نحتاج حجة تستبعد كل تعيين بأربعة أسماء.
أكبر مجموعة مستقلة على دورة خماسية فيها رأسان: ثلاث رؤوس مستقلة تحتاج بعد كل رأس رأسًا فاصلًا، فتحتاج الدورة ستة رؤوس على الأقل. لذلك يظهر كل اسم على رأسين على الأكثر.
يلزم خمسة رؤوس مضروبة في اسمين، أي عشرة ظهورات. أربعة أسماء توفر ثمانية ظهورات على الأكثر؛ فلا تكفي. خمسة أسماء توفر عشرة، والتعيين السابق يحققها، فثبت الأقل.
| الحافة | مجموعة الطرف الأول | مجموعة الطرف الثاني | الأسماء المشتركة |
|---|---|---|---|
| AB | {1,2} | {3,4} | لا يوجد |
| BC | {3,4} | {1,5} | لا يوجد |
| CD | {1,5} | {2,3} | لا يوجد |
| DE | {2,3} | {4,5} | لا يوجد |
| AE | {1,2} | {4,5} | لا يوجد |
نسختان من تلوين عادي تعطيان ستة، لكن خمسة تكفي
تلوين عادي للدورة الخماسية يقسمها إلى AC وBD وE، بثلاثة أسماء. لونان لا يكفيان: التناوب حول دورة ذات طول فردي يعيد اللون نفسه إلى طرفي حافة الإغلاق.
إذا كررنا التقسيم مرتين مع أسماء جديدة في النسخة الثانية، أخذ كل رأس اسمين مختلفين، وبقي المتجاوران منفصلين. هذا بناء صحيح يستخدم ستة أسماء.
البناء السابق ذو خمسة أسماء أفضل: لا يطلب النموذج أن نقسم الأسماء إلى تلوينين عاديين منفصلين؛ المطلوب هو انفصال مجموعتي المتجاورين فقط. إعادة ترتيب مجموعات استعمال الأسماء تتيح مشاركة أكثر كفاءة.
عند b=3، نبدأ بالتعيين ذي خمسة أسماء واسمين لكل رأس، ثم نعطي الاسم 6 للمجموعة AC، و 7 للمجموعة BD، و 8 للرأس E وحده.
تصبح المجموعات A={1,2,6} وB={3,4,7} وC={1,5,6} وD={2,3,7} وE={4,5,8}. كل رأس يأخذ ثلاثة أسماء، ولا يظهر اسم جديد عند طرفي حافة.
الأسماء الثمانية تكفي. يلزم خمسة عشر ظهورًا، والاسم الواحد يغطي رأسين على الأكثر؛ لذلك k لا يقل عن تقريب 15/2 إلى الأعلى، أي ثمانية. تكرار التلوين العادي ثلاث مرات يعطي تسعة، وهي زيادة يمكن تجنبها.
نستخدم أسماء جديدة عند جمع البناءين: لو أعدنا استعمال اسم قديم في المجموعة المضافة، فقد يحصل رأس على أقل من ثلاثة أسماء مختلفة، أو يشترك متجاوران في اسم. عد الخانات وحده لا يضمن صحة المجموعة.
أي طلب موجب على C5 وC7: عد الظهورات وابنِ المجموعات
على C5، اكتب b=2t+r حيث r يساوي 0 أو 1. خذ t نسخ من الأزواج AC AD BD BE CE، بأسماء جديدة لكل نسخة. تعطي كل نسخة اسمين لكل رأس وتستخدم خمسة أسماء.
إذا بقي r=1، أضف ثلاثة أسماء للمجموعات AC وBD وE. يحصل كل رأس على b أسماء، ويصبح عدد الأسماء k=5t+3r، وهو تقريب 5b/2 إلى الأعلى.
الحد الأدنى يأتي من 5b ظهورًا ومن حد رأسين لكل اسم. لذلك البناء يحقق الأقل لأي b صحيح موجب، بما فيه الطلب الفردي الذي يحتاج التقريب إلى الأعلى.
على C7، الحواف AB BC CD DE EF FG AG. أكبر مجموعة مستقلة فيها ثلاثة رؤوس: أربعة مستقلة تحتاج أربعة رؤوس فاصلة، أي ثمانية رؤوس. لذا k لا يقل عن تقريب 7b/3 إلى الأعلى.
هناك سبع مجموعات مستقلة من ثلاثة رؤوس: ACE ACF ADF BDF BDG BEG CEG. كل رأس يظهر في ثلاث منها بالضبط؛ تخصيص اسم جديد لكل مجموعة يعطي ثلاثة أسماء لكل رأس وسبعة أسماء في اللوحة.
للونين لكل رأس على C7، استخدم ACF وADF وBDG وBEG وCE. لكل رأس ظهوران بالضبط، وكل مجموعة مستقلة؛ أربعة مجموعات من ثلاثة رؤوس ومجموعة من رأسين توفر أربعة عشر ظهورًا بخمسة أسماء.
للون الواحد على C7، استخدم ACE وBDF وG، بثلاثة أسماء. اكتب b=3t+r حيث r يساوي 0 أو 1 أو 2: اجمع t نسخ من بناء السبعة، ثم أضف بناء الثلاثة إذا r=1 أو بناء الخمسة إذا r=2، بأسماء جديدة.
عدد الأسماء يصبح 7t عند r=0، أو 7t+3 عند r=1، أو 7t+5 عند r=2؛ في الحالات الثلاث يساوي تقريب 7b/3 إلى الأعلى. انفصال الأسماء بين النسخ يحفظ العدد المطلوب لكل رأس، واستقلال كل مجموعة يحفظ شرط الحواف.
| الطلب b | أقل أسماء C5 | أقل أسماء C7 |
|---|---|---|
| 1 | 3 | 3 |
| 2 | 5 | 5 |
| 3 | 8 | 7 |
| 4 | 10 | 10 |
| 5 | 13 | 12 |
| 6 | 15 | 14 |
شهادة أسعار تثبت الأقل في الأمثلة الأخرى
عد الظهورات وحده يعطي حدًا مفيدًا للدورات، لكنه قد يكون ضعيفًا في رسم غير متجانس. نضع عند كل رأس سعرًا غير سالب، ونطلب أن يكون مجموع الأسعار في كل مجموعة مستقلة 1 على الأكثر.
كل اسم يظهر على مجموعة مستقلة، فيحمل سعرًا مجموعُه 1 على الأكثر. إذا استخدمنا k أسماء، فمجموع أسعار كل الظهورات لا يتجاوز k. ومن جهة الرؤوس، كل رأس يظهر b مرات بالضبط؛ فالمجموع نفسه يساوي b مضروبًا في مجموع أسعار الرؤوس.
إذن k لا يقل عن b مضروبًا في مجموع الأسعار، ثم عن تقريب هذا الحد إلى الأعلى لأن k عدد صحيح. إذا قدمنا تعيينًا صحيحًا بعدد يساوي الحد الصحيح، ثبت أنه الأقل.
على C5، السعر 1/2 عند كل رأس يحقق شرط كل مجموعة مستقلة، ويعطي الحد 5b/2. وعلى C7، السعر 1/3 عند كل رأس يعطي 7b/3. البناءان السابقان يطابقان تقريب هذين الحدين لأي b موجب.
على نجمة بثلاث أوراق، ضع السعر 1 عند المركز و 1 عند ورقة واحدة، وصفرًا عند الورقتين الأخريين. لا تجمع مجموعة مستقلة المركز وتلك الورقة؛ فالحد 2b.
أعط المركز مجموعة من b أسماء، وجميع الأوراق مجموعة أخرى من b أسماء لا تشترك معها. يستخدم الرسم 2b اسمًا ويحقق الحد؛ لا تعطي كل ورقة مجموعة جديدة بلا حاجة.
على K4، لا تضم مجموعة مستقلة أكثر من رأس. ضع السعر 1 عند كل رأس؛ تحتاج 4b أسماء، وتحققها بإعطاء كل رأس مجموعة خاصة. وفي رسم بلا حواف، سعر 1 عند رأس واحد يعطي الحد b الذي يحققه استعمال المجموعة نفسها عند الجميع.
شهادة الأسعار أداة لحد أدنى، وليست قاعدة عامة بأن تقريب b مضروبًا في القيمة الكسرية يعطي الجواب لكل رسم. في الجداول قدمنا مجموعات أسماء صريحة تطابق الحد؛ المساواة هنا مثبتة لهذه النماذج.
في العمود الأخير من جدول النماذج، يسبق النقطتين الطلب b، ويتلوهما أقل عدد للأسماء k؛ مثلًا 2:5 يعني أن لونين لكل رأس يحتاجان خمسة أسماء. كل مدخل يربط طلبًا واحدًا بعدده، ولا يعتمد على اتجاه قراءة سلسلة أعداد.
| النموذج | رؤوس | حواف | الطلب: أقل الأسماء |
|---|---|---|---|
| دورة C4 | 4 | 4 | 1:2؛ 2:4؛ 3:6؛ 4:8؛ 5:10؛ 6:12 |
| مسار P4 | 4 | 3 | 1:2؛ 2:4؛ 3:6؛ 4:8؛ 5:10؛ 6:12 |
| دورة C6 | 6 | 6 | 1:2؛ 2:4؛ 3:6؛ 4:8؛ 5:10؛ 6:12 |
| دورة C5 | 5 | 5 | 1:3؛ 2:5؛ 3:8؛ 4:10؛ 5:13؛ 6:15 |
| مسار P5 | 5 | 4 | 1:2؛ 2:4؛ 3:6؛ 4:8؛ 5:10؛ 6:12 |
| مسار P6 | 6 | 5 | 1:2؛ 2:4؛ 3:6؛ 4:8؛ 5:10؛ 6:12 |
| نجمة بثلاث أوراق | 4 | 3 | 1:2؛ 2:4؛ 3:6؛ 4:8؛ 5:10؛ 6:12 |
| نجمة بخمس أوراق | 6 | 5 | 1:2؛ 2:4؛ 3:6؛ 4:8؛ 5:10؛ 6:12 |
| مثلث | 3 | 3 | 1:3؛ 2:6؛ 3:9؛ 4:12؛ 5:15؛ 6:18 |
| ماسة: مثلثان يشتركان بحافة | 4 | 5 | 1:3؛ 2:6؛ 3:9؛ 4:12؛ 5:15؛ 6:18 |
| رسم كامل K4 | 4 | 6 | 1:4؛ 2:8؛ 3:12؛ 4:16؛ 5:20؛ 6:24 |
| كامل ثنائي الأجزاء K2,3 | 5 | 6 | 1:2؛ 2:4؛ 3:6؛ 4:8؛ 5:10؛ 6:12 |
| كامل ثنائي الأجزاء K3,3 | 6 | 9 | 1:2؛ 2:4؛ 3:6؛ 4:8؛ 5:10؛ 6:12 |
| رسم كامل K5 | 5 | 10 | 1:5؛ 2:10؛ 3:15؛ 4:20؛ 5:25؛ 6:30 |
| رسم كامل K6 | 6 | 15 | 1:6؛ 2:12؛ 3:18؛ 4:24؛ 5:30؛ 6:36 |
| حافة ورؤوس معزولة | 4 | 1 | 1:2؛ 2:4؛ 3:6؛ 4:8؛ 5:10؛ 6:12 |
| حافتان منفصلتان | 4 | 2 | 1:2؛ 2:4؛ 3:6؛ 4:8؛ 5:10؛ 6:12 |
| أربعة رؤوس بلا حواف | 4 | 0 | 1:1؛ 2:2؛ 3:3؛ 4:4؛ 5:5؛ 6:6 |
| رسم كامل K7 | 7 | 21 | 1:7؛ 2:14؛ 3:21؛ 4:28؛ 5:35؛ 6:42 |
| مسار P7 | 7 | 6 | 1:2؛ 2:4؛ 3:6؛ 4:8؛ 5:10؛ 6:12 |
| دورة C7 | 7 | 7 | 1:3؛ 2:5؛ 3:7؛ 4:10؛ 5:12؛ 6:14 |
| مثلث وحافة منفصلة | 5 | 4 | 1:3؛ 2:6؛ 3:9؛ 4:12؛ 5:15؛ 6:18 |
| مثلث ورأسان معزولان | 5 | 3 | 1:3؛ 2:6؛ 3:9؛ 4:12؛ 5:15؛ 6:18 |
خمسة أسماء تختلف عن النسبة خمسة على اثنين
التلوين الكسري يضع أوزانًا حقيقية غير سالبة على مجموعات مستقلة، ويغطي كل رأس بوزن 1 على الأقل مع تقليل المجموع. [3]
في مسألتنا نعد أسماء منفصلة في لوحة منتهية، ونثبت b، ويأخذ كل رأس b أسماء مختلفة بالضبط. يجوز أن تتكرر مجموعة الرؤوس المستقلة بوصفها حاملة لاسمين مختلفين؛ التكرار يضيف اسمًا جديدًا ولا يكرر الاسم نفسه عند الرأس.
على C5، عند b=2 نحتاج k=5 أسماء، والنسبة k/b=5/2. عند b=3 نحتاج k=8، والنسبة 8/3. النسبتان مختلفتان رغم أن الرسم واحد؛ الطلب الثابت يؤثر في التقريب الصحيح.
القيمة الكسرية للدورة الخماسية 5/2: نصف وزن لكل من الأزواج الخمسة يغطي كل رأس بوزن 1، وأسعار النصف عند الرؤوس تثبت الحد. هذه حجة خاصة بالمثال؛ لا تحول العدد 5/2 إلى اسمين ونصف في لوحة b=2.
إذا أعطينا مجموعة الرؤوس الحاملة لكل اسم وزنًا 1/b، حصلنا على تغطية كسرية مجموع أوزانها k/b، لكن الهدف في المقال هو أقل k للطلب المحدد، لا اختيار b بحرية لتحسين النسبة.
يوجد معنى مختلف للحرف b في تلوين b المسيطر: هو تلوين عادي صحيح، ولكل فئة لون رأس يشاهد جميع الفئات الأخرى، ويطلب أكبر عدد من الألوان. [4]
لا نطلب ذلك الرأس الشاهد هنا، ولا نعظم العدد؛ b في نموذجنا عدد الأسماء المطلوبة عند كل رأس. تشابه الحرف لا يسمح باستعمال نتيجة للمسألة المسيطرة لإثبات عدد الأسماء في التلوين المتعدد.
ماذا راجع الحصر، وماذا يثبت البرهان؟
راجعنا 23 نموذجًا مع b من 1 إلى 6، أي 138 حالة ذات طلب ثابت. وراجعنا الرسوم ذات أربعة رؤوس مسماة: ست حواف ممكنة تعطي 64 رسمًا، ومع ستة طلبات نحصل على 384 حالة. الرسم بلا حواف داخل الحصر وله قيمة b.
في كل حالة، راجع الفحص حجم مجموعة كل رأس وتمايز أسمائها، وانفصال مجموعتي كل حافة، ثم استعاد مجموعة الرؤوس الحاملة لكل اسم وتحقق من استقلالها ومن استعمال كل أسماء اللوحة.
للحد الأدنى، فحصنا كل مجموعة مستقلة وأسعارها غير السالبة، ثم ضربنا مجموع الأسعار في b وقربنا إلى الأعلى. طابق هذا العدد حجم اللوحة المبنية في كل حالة. بلغ عدد قيود أسعار المجموعات المستقلة في حصر الأربعة الرأس مع الطلبات الستة 2886.
فحص آخر أعاد حصر مجموعات الرؤوس باستخدام بتات، وقارن مجموعات الأسماء على الحواف مباشرة، وراجع العد من جهة الأسماء ومن جهة الرؤوس. وراجع كتل بناء الدورتين وعدد مرات ظهور كل رأس وصيغ بواقي القسمة.
حصر الطلبات الستة لا يثبت النتيجة لكل طلب موجب وحده. البرهان العام للدورتين يأتي من حد أكبر مجموعة مستقلة، ثم من تكرار كتل البناء بأسماء جديدة وإضافة البناء الملائم للباقي.
الفحوص من إعداد المقال وتشترك في مكتبة الكسور؛ لا ندعي مراجعًا بشريًا مستقلًا أو برنامجًا يحل كل رسم. التعريفات من المصادر المحددة، أما مجموعات الأمثلة وشهاداتها والبناءات والحصر فمن إعداد المقال.
لفحص تعيين جديد، ابدأ بكل رأس: هل له b أسماء مختلفة؟ ثم بكل حافة: هل المجموعتان منفصلتان؟ بعد ذلك عد الأسماء المستخدمة مرة واحدة، وقدم حدًا أدنى يطابق العدد قبل إعلان أنه الأقل.
اقرأ أيضًا: استرجاع الرسوم البيانية: نوع العلاقة واتجاهها
اقرأ أيضًا: أنواع الرسم البياني: اختر الشكل الذي يجيب عن السؤال
المراجع
- Tight lower bounds for the complexity of multicoloring — arXiv:1607.03432
- MathWorld — Vertex Coloring
- MathWorld — Fractional Coloring
- b-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs — arXiv:1310.8313
أُعدّ هذا المقال بمساعدة الذكاء الاصطناعي، وخضع لمراجعة ذاتية بالأداة نفسها. لا يُنسب إلى مراجع بشري أو خبير مستقل. منهجية المحتوى.