التلوين

القسم 2.5 التلوين

الأهداف

بعد إتمام هذا القسم، ينبغي أن تتمكّن من فعل ما يلي.

1. أن تحدّد العددَ اللوني (chromatic number) لرسمٍ بياني.
2. أن تحدّد الفهرسَ اللوني (chromatic index) لرسمٍ بياني.
3. أن تقرّر أيّهما أنسب لحلّ مسألةٍ بعينها: العددُ اللوني أم الفهرسُ اللوني.

معاينة القسم

استكشف!

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

!

تُعدّ مسألةُ تلوين الخرائط أشهرَ مسائل نظرية الرسوم البيانية.

معطى أيّ خريطةٍ لدولٍ أو ولاياتٍ أو مقاطعات أو ما شابه، كم لونًا نحتاج لتلوين كلّ منطقةٍ على الخريطة بحيث تكون المناطق المتجاورة ملوّنةً بألوانٍ مختلفة؟

يستعمل صانعو الخرائط عادةً نحو سبعة ألوان. فمن جهة، يشترطون أن تكون المناطق المائيّة بلونٍ محدّد، ومع كثرة الألوان يكون العثور على تلوينٍ مسموحٍ أسهل. ونحن نريد أن نعرف: هل توجد لوحةُ ألوانٍ أصغر من هذه تنفع لأيّ خريطة؟

فما علاقة هذا بنظرية الرسوم البيانية؟ حسنًا، إن وضعنا رأسًا (vertex) في مركز كلّ منطقة (ولنفرض في عاصمة كلّ ولاية) ثمّ وصلنا بين رأسين متى تشترك ولايتاهما في حدّ، حصلنا على رسمٍ بياني. وتلوين مناطق الخريطة يقابل تلوين رؤوس ذلك الرسم البياني. وبما أنّ المناطق المتجاورة لا يجوز أن تُلوَّن باللون نفسه، فإنّ رسمَنا البياني لا يجوز أن تكون فيه رؤوسٌ متجاورة ملوّنةٌ باللون نفسه.

وبوجهٍ عام، معطى أيّ رسمٍ بياني $G\text{,}$ يُسمّى تلوينُ رؤوسه (وهذا ليس مفاجئًا على نحوٍ ما) تلوينَ رؤوس (vertex coloring). فإذا كان تلوينُ الرؤوس بحيث تُلوَّن الرؤوسُ المتجاورة بألوانٍ مختلفة، سُمّي هذا التلوين سليمًا (proper). ولكلّ رسمٍ بياني تلوينُ رؤوسٍ سليم. فمثلًا يمكنك أن تُلوِّن كلّ رأسٍ بلونٍ مختلف. لكنّك غالبًا ما تستطيع أفضل من ذلك. وأقلّ عددٍ من الألوان اللازم للحصول على تلوين رؤوسٍ سليم يُسمّى العددَ اللوني (chromatic number) للرسم البياني، ويُكتب $\chi(G)\text{.}$

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

ورقة العمل: نشاط تمهيدي

لكلّ رسمٍ بياني أدناه:

• أوجد تلوينَ رؤوسٍ سليمًا باستعمال عددٍ ما من الألوان. أي: لوّن الرؤوس باستعمال أيّ عددٍ من الألوان، على أن لا يتشارك أيّ زوجٍ من الرؤوس المتجاورة اللونَ نفسه.
• أوجد أقلّ عددٍ من الألوان تحتاجه لتلوين رؤوس الرسم البياني تلوينًا سليمًا. وهذا ما يُسمّى العددَ اللوني (chromatic number) للرسم البياني. فكّر في كيفية إدراكك أنّ إجابتك صحيحة.
• هل تستطيع التعميم؟ هل يمكنك أن تستنتج أيّ شيءٍ عن العدد اللوني في أنواعٍ معيّنة من الرسوم البيانية؟

1.

$\chi(G) =$

2.

$\chi(G) =$

3.

$\chi(G) =$

4.

$\chi(G) =$

5.

$\chi(G) =$

6.

$\chi(G) =$

تلوين الرؤوس

استكشف!

خطّط قسم الرياضيات لعرض 10 مقرّراتٍ في الفصل الدراسي القادم. وبعض المقرّرات لا يمكن أن تُعقد في الوقت نفسه (ربما لأنّها يدرّسها أستاذٌ واحد، أو لأنّها مقرّراتٌ إلزامية لطلبة السنة الرابعة).

المقررّ:	يتعارض مع:
A	D I
B	D I J
C	E F I
D	A B F
E	C H I
F	C D I
G	J
H	E I J
I	A B C E F H
J	B G H

كم عدد الفترات الزمنية المختلفة اللازمة لتقديم هذه المقرّرات (وأيّها ينبغي أن تُقدَّم في الوقت نفسه)؟ والأهمّ من ذلك، كيف يمكننا أن نستعمل تلوين الرسوم البيانية للإجابة عن هذا السؤال؟

أفضلُ طريقة للإحساس بالعدد اللوني هي أن تحاول فعليًّا تلوينَ بعض الرسوم البيانية.

مثال 2.5.1.

أوجد العددَ اللوني (chromatic number) للرسوم البيانية أدناه.

الحلّ. الرسمُ البياني على اليسار هو $K_6\text{.}$ والطريقةُ الوحيدة لتلوين هذا الرسم تلوينًا سليم هي إعطاءُ كلّ رأسٍ لونًا مختلفًا (لأنّ كلّ رأسٍ مجاورٌ لكلّ رأسٍ آخر). ومن ثمّ فإنّ العدد اللوني هو 6.

ويمكن تلوينُ الرسم الأوسط تلوينًا سليمًا بثلاثة ألوانٍ فقط (الأحمر والأزرق والأخضر). مثلًا:

ولا توجد طريقةٌ لتلوينه بلونين فقط، لأنّ هناك ثلاثة رؤوسٍ كلٌّ منها مجاورٌ للاثنين الآخرين (أي مثلّثًا). ومن ثمّ فإنّ العدد اللوني هو 3.

والرسمُ البياني على اليمين هو ببساطة $K_{2,3}\text{.}$ وكما في جميع الرسوم الثنائية الجزء، فإنّ هذا الرسم عدده اللوني 2: لوّن رؤوس الصفّ العلوي بالأحمر ورؤوس الصفّ السفلي بالأزرق.

يبدو أنّه لا حدّ لمدى كِبَر الأعداد اللونية. ولا ينبغي أن يفاجئك أنّ $K_n$ عدده اللوني $n\text{.}$ فكيف إذن يمكن لسؤال تلوين الخرائط الأصلي أن تكون له إجابة؟ وإذا كان العددُ اللوني لرسمٍ بياني قد يصير كبيرًا إلى حدٍّ غير محدود، فإنّه يبدو إذن ألّا يكون هناك حدٌّ أعلى لعدد الألوان اللازم لأيّ خريطة. غير أنّ هناك حدًّا.

والملاحظةُ المفتاحية هي أنّه وإن كان صحيحًا أنّه لكلّ عددٍ $n$ يوجد رسمٌ بياني عدده اللوني $n\text{,}$ فإنّ بعض الرسوم البيانية فقط هي التي تصلح تمثيلًا للخرائط. فإذا حوّلتَ خريطةً إلى رسمٍ بياني، فإنّ الحوافّ بين الرؤوس تقابل الحدودَ بين البلدان. ومن ثمّ ينبغي أن تستطيع وصلَ الرؤوس بحيث لا تتقاطع الحواف. وبعبارةٍ أخرى، الرسومُ البيانية التي تمثّل الخرائط كلّها مستويّة (planar)!

والسؤالُ إذن هو: ما أكبر عددٍ لونيٍّ لأيّ رسمٍ بياني مستوٍّ؟ والجوابُ هو أشهرُ مبرهنةٍ في نظرية الرسوم البيانية:

مبرهنة 2.5.2. مبرهنة الألوان الأربعة.

إذا كان $G$ رسمًا بيانيًا مستويًّا، فإنّ العددَ اللوني لـ $G$ أصغرُ من 4 أو مساوٍ له. ومن ثمّ يمكن تلوينُ أيّ خريطةٍ تلوينًا سليمٍ بأربعة ألوانٍ أو بأقلّ.

لن نبرهن هذه المبرهنة. حقًّا. فمع أنّ المبرهنة سهلةُ الصياغة والفهم، إلّا أنّ برهانها ليس كذلك. وفي الحقيقة لا توجد حتى الآن برهنةٌ معروفةٌ “سهلة” لهذه المبرهنة. وما زال أفضلُ برهانٍ حاليٍّ يتطلّب حواسيبَ قويّةَ للتحقّق من مجموعةٍ لا مفرّ من 633 تركيبةً اختزالية (reducible configurations). والفكرةُ أنّ كلّ رسمٍ بياني يجب أن يحوي إحدى هذه التركيبات الاختزالية (وهذه الحقيقة تحتاج بدورها إلى التحقّق بستعمال حاسوب) وأنّ التركيبات الاختزالية يمكن بالفعل تلوينُها بأربعة ألوانٍ أو بأقلّ.

ورسمُ الخرائط ليس بالتأكيد التطبيقَ الوحيد للتلوين الرسوميّ. فهناك حالاتٌ كثيرة قد ترغب فيها في تقسيم الأشياء محلّ البحث بحيث لا تقع الأشياءُ المترابطة في المجموعة نفسها. فمثلًا قد ترغب في تخزين المواد الكيميائية بأمان. ولتجنّب الانفجارات، ينبغي ألّا تُخزَّن أزواجٌ معيّنة من المواد الكيميائية في الغرفة نفسها. وبتلوين رسمٍ بياني (مع رؤوسٍ تمثّل المواد الكيميائية وحوافٍ تمثّل التفاعلات السلبية المحتملة)، تستطيع تحديدَ أقلّ عددٍ من الغرف اللازمة لتخزين المواد الكيميائية.

وإليك مثالًا آخر:

مثال 2.5.3.

تبثّ محطّاتُ الراديو إشاراتها عند تردداتٍ معيّنة. لكنّ عددَ الترددات التي يمكن اختيارها محدود، لذا فعلى مستوى البلاد تستخدم محطّاتٌ كثيرةً الترددَ نفسه. ويأتي ذلك لأنّ المحطّات متباعدةٌ بدرجةٍ كافية بحيث لا تتداخل إشاراتها؛ إذ لا يستطيع أيّ جهازِ رادٍ التقاطَها في الوقت نفسه.

لنفرض أنّ عشر محطّات راديو جديدة ستُنشأ في منطقةٍ خاليةٍ حاليًّا (من محطّات الراديو). وتُدوَّن في الجدول أدناه المحطّاتُ القريبةُ من بعضها بالدرجة الكافية بحيث يحدث تداخل. فما أقلّ عددٍ من الترددات يمكن للمحطّات أن تستعمله؟

	KQEA	KQEB	KQEC	KQED	KQEE	KQEF	KQEG	KQEH	KQEI	KQEJ
KQEA			x			x	x			x
KQEB			x	x
KQEC	x	x				x	x			x
KQED		x			x	x		x
KQEE				x					x
KQEF	x		x	x			x			x
KQEG	x		x			x				x
KQEH				x					x
KQEI					x			x		x
KQEJ	x		x			x	x		x

الحلّ. مثّل المسألةَ برسمٍ بيانيٍّ تكون رؤوسُه هي المحطّات، وتكون فيه حافةٌ متى كانت محطّتان قريبتَين بالدرجة الكافية يحدث بينهما تداخل. ونحن نبحث عن العدد اللوني لهذا الرسم البياني. والرؤوسُ الملوّنة بالطريقة نفسها تمثّل محطّاتٍ يمكن أن تتشارك الترددَ نفسه.

عددُ هذا الرسم البياني اللوني 5. ويظهر على اليمين تلوينٌ سليمٌ بخمسة ألوان. ولاحظ أنّ الرسم البياني يحوي نسخةً من الرسم البياني الكامل $K_5\text{,}$ ومن ثمّ لا يمكن استعمالُ أقلّ من خمسة ألوان.

في المثال أعلاه كان العددُ اللوني 5، لكنّ هذا ليس مثالًا مضادًّا لـ مبرهنة الألوان الأربعة 2.5.2، لأنّ الرسم البياني الذي يمثّل محطّات الراديو ليس مستويًّا. وكان من جيّد لو وُجدت طريقةٌ سريعةٌ لإيجاد العدد اللوني لرسمٍ بياني (قد لا يكون مستويًّا). لكنّ الأمر تبيّن أنّ لا أحد يعرف هل توجد خوارزميّةٌ كفاءةٌ لحساب الأعداد اللونية.

ولئن كنّا قد لا نستطيع بسهولة إيجادَ العدد اللوني الدقيق لرسمٍ بياني، فإنّنا نستطيع غالبًا إعطاءَ مدىً معقولٍ للعدد اللوني. وبعبارةٍ أخرى، نستطيع إعطاءَ حدٍّ أعلى وحدٍّ أدنى للعدد اللوني.

وهذا ليس صعبًا جدًّا: فلكلّ رسمٍ بياني $G\text{,}$ يكون العددُ اللوني لـ $G$ مساويًا 1 على الأقلّ، ومساويًا لعدد رؤوس $G\text{.}$

ماذا؟ أتريد حدودًا أدقّ للعدد اللوني؟ حسنًا، أنت في الحظّ السعيد.

التجمّع (clique) في رسمٍ بياني هو مجموعةُ رؤوسٍ كلُّها متجاورةٌ فيما بينها. وبعبارةٍ أخرى، التجمّعُ بحجم $n$ ليس سوى نسخةٍ من الرسم البياني الكامل $K_n\text{.}$ ونعرّف عددَ التجمّعات (clique number) في رسمٍ بياني بأنّه أكبرُ $n$ يكون عندها في الرسم البياني تجمّعٌ بحجم $n\text{.}$ وأيّ تجمّعٍ بحجم $n$ لا يمكن تلوينُه بأقلّ من $n$ لونًا، ومن ثمّ لدينا حدٌّ أدنى جميل:

مبرهنة 2.5.4.

العددُ اللوني لرسمٍ بياني $G$ أصغرُ من عدد التجمّعات لـ $G\text{.}$ أو مساوٍ له.

وهناك أحيانًا ما يكون فيه العددُ اللوني لـ $G$ مساويًا لعدد التجمّعات. وهذه الرسومُ البيانية لها اسمٌ خاص؛ فهي تسمّى مثاليّة (perfect). فإذا عرفتَ أنّ رسمًا بيانيًا مثاليّ، فإنّ إيجادَ العدد اللوني ليس سوى مسألةِ البحث عن أكبر تجمّع. 10 وهناك أصنافٌ خاصةٌ من الرسوم البيانية يمكن إثباتُ أنّها مثاليّة. ومن هذه الأصناف مجموعةُ الرسوم التاجيّة (chordal graphs)، التي لها خاصيّةُ أنّ كلّ دورةٍ في الرسم البياني تحوي وترًا—أي حافةً بين رأسين في الدورة ليسا متجاورَين في الدورة. غير أنّ ليس كلُّ الرسوم البيانية مثاليًّا.

وبالنسبة إلى الحدّ الأعلى، يمكننا تحسينُ «عدد الرؤوس» بالنظر إلى درجات الرؤوس. فليكن $\Delta(G)$ أكبرَ درجةٍ لأيّ رأسٍ في الرسم البياني $G\text{.}$ ومن التقديرات المعقولة للحدّ الأعلى للعدد اللوني أنّ $\chi(G) \le \Delta(G) + 1\text{.}$ ولماذا هذا معقول؟ إن بدأنا بأيّ رأس، فإنّه هو وكلُّ جيرانه يمكن تلوينُهم دائمًا بـ $\Delta(G) + 1$ لونًا، لأنّنا نتكلّم في الغاية عن $\Delta(G) + 1$ رأسًا في هذه المجموعة. والآن فتّح وانتشر! في أيّ لحظة، إن نظرتَ إلى رأسٍ ملوَّنٍ بالفعل، فإنّ بعضَ جيرانه قد يكونون ملوّنين وبعضُهم لا يكون. لكنّ ذلك الرأس وجيرانَه يمكن أن يكون كلٌّ منهم بلونٍ مختلف، إذ لا يزيد عددُ جيرانه عن $\Delta(G)$، تزيد ذلك الرأسُ الواحد محلّ النظر.

وفي الحقيقة، هناك رسومٌ بيانية يكون فيها $\chi(G) = \Delta(G) + 1\text{.}$ فلكلّ $n\text{,}$ يكون للرسم البياني الكامل $K_n$ عددٌ لونيّ $n\text{,}$ لكنّ $\Delta(K_n) = n-1$ (لأنّ كلّ رأسٍ مجاورٌ لكلّ رأسٍ آخر). وإضافةً إلى ذلك، فإنّ أيّ دورةٍ فرديّة يكون عددها اللوني 3، لكنّ درجةَ كلّ رأسٍ في دورةٍ هي 2. ويبيّن الأمرُ أنّ نوعَي الأمثلة هذين هما الوحيدان اللذان نحصل فيهما على التساوي، وهذه نتيجةٌ معروفةٌ باسم مبرهنة بروكس.

مبرهنة 2.5.5. مبرهنة بروكس.

كلُّ رسمٍ بياني $G$ يحقّق $\chi(G) \le \Delta(G)\text{,}$ إلا إذا كان $G$ رسمًا كاملًا أو دورةً فرديّة، وعندئذٍ $\chi(G) = \Delta(G) + 1\text{.}$

برهانُ هذه المبرهنة معقّدٌ إلى الحدّ الذي لن نعرضه هنا (مع أنّه مطلوبٌ منك إثباتُ حالةٍ خاصةٍ في التمارين). والقارئُ المغامر مدعوٌّ إلى أن يعثر على كتابٍ في نظرية الرسوم البيانية ليجد فيه اقتراحاتٍ حول كيفية إثبات المبرهنة.

تلوين الحوافّ

العددُ اللوني لرسمٍ بياني يخبرنا عن تلوين رؤوسه، لكنّنا يمكننا أيضًا أن نسأل عن تلوين حوافّه. ومثلَ تلوين الرؤوس تمامًا، قد نُلحّ على أنّ الحوافّ المتجاورة يجب أن تُلوَّن بألوانٍ مختلفة. وهنا نعتبر حافتين متجاورَتين إذا كانا تلتقيان في الرأس نفسه. وأقلُّ عددٍ من الألوان اللازم لتلوين حوافّ رسمٍ بياني $G$ تلوينًا سليمًا يُسمّى الفهرسَ اللوني (chromatic index) لـ $G\text{,}$ ويُكتب $\chi'(G)\text{.}$

مثال 2.5.6.

قرّر ستةُ أصدقاء قضاءَ فترةٍ بعد الظهر في لعب الشطرنج. وسيلعب كلٌّ منهم كلَّ آخرٍ منهم مرّةً واحدة. ولديهم مجموعاتُ شطرنجٍ كثيرة، لكن لا أحد يريد أن يلعب أكثرَ من مباراةٍ في وقتٍ واحد. وستدوم كلُّ مباراةٍ ساعةً (بفضل ساعات الشطرنج اليدوية عندهم). فكم ساعةً ستدوم البطولة؟

الحلّ. مثّل كلَّ لاعبٍ برأس، وضع حافةً بين لاعبين إذا لعب أحدهما الآخر. وفي هذه الحالة نحصل على الرسم البياني $K_6\text{:}$

وعلينا أن نلوّن الحوافّ؛ ويمثّل كلُّ لونٍ ساعةً مختلفة. وبما أنّ الحوافّ المختلفة الملتقيّة في الرأس نفسه ستُلوَّن بألوانٍ مختلفة، فلا سيلعب أيُّ لاعب مباراتين (حافتين) مختلفتين في الوقت نفسه. ومن ثمّ نحتاج إلى معرفة الفهرس اللوني لـ $K_6\text{.}$

ولاحظ أنّ $\chi'(K_6) \ge 5\text{,}$ بالتأكيد، لأنّ هناك رأسًا درجته 5. ويبيّن الأمرُ أنّ خمسةَ ألوانٍ تكفي (اذهب وابحث عن تلوينٍ من هذا النوع). ومن ثمّ سيلعب الأصدقاء لمدّة خمس ساعات.

ومن اللافت للنظر أنّه لو غادر أحدُ الأصدقاء في المثال أعلاه، لكان الخمسةُ المتبقّون من هواة الشطرنج ما زالوا يحتاجون خمس ساعات: فالفهرسُ اللوني لـ $K_5$ هو أيضًا 5.

وبوجهٍ عام، ماذا يمكننا أن نقول عن الفهرس اللوني؟ وبالطبع $\chi'(G) \ge \Delta(G)\text{.}$ لكنّ إلى أيّ حدٍّ قد يكون أعلى؟ ليس أعلى إلّا بقليلٍ جدًّا.

مبرهنة 2.5.7. مبرهنة فيزينغ.

لكلّ رسمٍ بياني $G\text{,}$ فإنّ الفهرسَ اللوني $\chi'(G)$ إمّا $\Delta(G)$ وإمّا $\Delta(G) + 1\text{.}$

في البداية، تُوحي هذه المبرهنة بأنّ الفهرسَ اللوني ربّما ليس مثيرًا للاهتمام كثيرًا. لكنّ تحديدَ الحالة التي يقع فيها رسمٌ بيانيٍّ ليس سهلًا دائمًا. وتُسمّى الرسومُ التي يكون $\chi'(G) = \Delta(G)$ الصنف 1، بينما تُسمّى سواها الصنف 2. والرسومُ الثنائية الجزء (bipartite) تحقّق دائمًا $\chi'(G) = \Delta(G)\text{,}$ فهي من الصنف 1 (وقد أثبت ذلك كونيغ (König) سنة 1916، أي قبل عقودٍ من إثبات فيزينغ مبرهنته سنة 1964). وقد أثبت فيزينغ سنة 1965 أنّ كلَّ الرسوم المستوية التي يكون $\Delta(G) \ge 8$ تنتمي إلى الصنف 1، لكنّ هذا لا يتحقّق لكلِّ الرسوم المستوية التي يكون $2 \le \Delta(G) \le 5\text{.}$ وتوقّع فيزينغ أنّ كلَّ الرسوم المستوية التي يكون $\Delta(G) = 6$ أو $\Delta(G) = 7$ تنتمي إلى الصنف 1؛ وقد ثبتت حالة $\Delta(G) = 7$ سنة 2001 على يد ساندِرز (Sanders) وزاو (Zhao)؛ أمّا حالة $\Delta(G) = 6$ فما تزال مفتوحة.

نظرية رامزي.

هناك طريقةٌ أخرى مثيرةٌ للاهتمام يمكننا بها التفكير في تلوين الحوافّ، مختلفةٌ تمامًا عمّا ناقشناه حتى الآن. فماذا لو لوّنّا كلَّ حافةٍ في رسمٍ بيانيٍّ إمّا بالأحمر وإمّا بالأزرق؟ هل يمكننا فعلَ ذلك دون أن نُنشئ، مثلًا، مثلّثًا أحاديَّ اللون (monochromatic)، أي مثلّثًا كلُّه أحمر أو كلُّه أزرق؟ وبالطبع، فإنّ الجوابَ نعم لبعض الرسوم البيانية. جرّب ذلك على $K_4\text{.}$ فماذا عن $K_5\text{?}$ $K_6\text{?}$ وإلى أيّ حدٍّ يمكننا الذهاب؟

والمسألةُ أعلاه ليست صعبةً جدًّا وهي تمرينٌ ممتع. ويمكننا توسيعَ السؤال بطرقٍ متعدّدة. فماذا لو كان لدينا ثلاثةُ ألوان؟ وماذا لو كنا نحاول تجنّب رسومٍ بيانيةٍ أخرى؟ ولأمرٍ مدهش، فمعلوماتُنا عن هذه الأسئلة قليلةٌ جدًّا. فمثلًا، نعرف أنّه يلزم الصعودُ إلى $K_{17}$ لإجبار وجود مثلّثٍ أحاديّ اللون باستعمال ثلاثة ألوان، لكن لا أحد يعرف كم يجب أن نصعد إليه مع ألوانٍ أكثر. وبالمثل، نعلم أنّ باستعمال لونين يكون $K_{18}$ أصغرَ رسمٍ بيانيٍّ يُجبر على نسخةٍ أحاديةِ اللون من $K_4\text{,}$ لكنّ أفضلَ ما لدينا لإجبار $K_{5}$ أحاديّ اللون هو مدىً من $K_{43}$ إلى $K_{49}\text{.}$ وإن كنت مهتمًّا بهذه الأسئلة، فإنّ هذا المجالَ من نظرية الرسوم البيانية يُسمّى نظرية رامزي (Ramsey theory). فتفحّصها.

أسئلة القراءة

1.

صحّ أم خطأ: إذا احتوى رسمٌ بيانيٌّ على رأسٍ درجته 5، فإنّ العددَ اللوني للرسم البياني مساوٍ لـ 5 على الأقلّ. اشرح.

2.

بعباراتك أنت، اشرح الفرقَ بين العدد اللوني والفهرس اللوني.

3.

ما الأسئلةُ التي تدور في ذهنك بعد قراءة هذا القسم؟ اكتب سؤالًا واحدًا على الأقلّ عن محتوى هذا القسم يثيرُ اهتمامك.