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