تلوين مخطط مستو بثلاثة ألوان
| مسألة NP كاملة |
|---|
| زمرة كبرى |
| مسار هاملتونياني |
| عدل |
هو امتداد لمسألة تلوين مخطط، يكون في مخطط مستوي و تعريف المسألة كما يلي:
- G مخطط مستوي
- السؤال: هل يمكن تلوين المخطط G باستعمال ثلاثة ألوان فقط بحيث تلون كل قمتين مرتبطتين بلونين مختلفين.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
الاختصار
يبين هذا الاختصار أن تلوين مخطط مستوي هو من المسائل NP الكاملة.
انطلاقا من مسألة تلوين مخطط بثلاثة ألوان، يتم تحويل كل مخطط عادي إلى مخطط مستوي، و ذلك بوضع مخطط مستو خاص يسمى المخطط الماسي (انظر الصورة)، مكان تقاطع الارتباطات (انظر الصورة).
خصائص المخطط الماسي
يحمل المخطط الماسي الخصائص الآتية:
- عند تلوين المخطط الماسي بثلاثة ألوان، القمم الطرفية (الموجودة في الطرف) تكون ملونة بنفس اللون مثنى مثنى.
- إذا تم تلوين القمم الطرفية بنفس اللون مثنى مثنى، فيمكن تلوين بقية القمم.
- المخطط الماسي مخطط مستو.
تحويل المخطط العادي للمخطط مستو
ليكن G مخطط عادي و (a,b) ارتباط يقطع بعض الارتباطات الأخرى. يتم وضع مخطط ماسي مكان كل تقاطع.
فنحصل على مخطط مستو. و انطلاقا من خصائص المخطط الماسي، يكون المخطط المستوي ملونا بثلاثة ألوان إذا وفقط إذا كان المخطط العادي ملون أيضا بثلاثة ألوان.
