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