تلوين مخطط مستو بثلاثة ألوان

من ويكيبيديا، الموسوعة الحرة

مسألة NP كاملة
قابلية الإرضاء 3سات NAE OIT
تلوين مخطط تلوين مخطط بثلاثة ألوان تلوين مخطط مستو بثلاثة ألوان
زمرة كبرى
مسار هاملتونياني
عدل

هو امتداد لمسألة تلوين مخطط، يكون في مخطط مستوي و تعريف المسألة كما يلي:

1. G مخطط مستوي
2. السؤال: هل يمكن تلوين المخطط G باستعمال ثلاثة ألوان فقط بحيث تلون كل قمتين مرتبطتين بلونين مختلفين.

[تحرير] الاختصار

يبين هذا الإختصار أن تلوين مخطط مستوي هو من المسائل NP الكاملة.

انطلاقا من مسألة تلوين مخطط بثلاثة ألوان، يتم تحويل كل مخطط عادي إلى مخطط مستوي، و ذلك بوضع مخطط مستو خاص يسمى المخطط الماسي (انظر الصورة)، مكان تقاطع الارتباطات (انظر الصورة).

[تحرير] خصائص المخطط الماسي

يحمل المخطط الماسي الخصائص الآتية:

1. عند تلوين المخطط الماسي بثلاثة ألوان، القمم الطرفية (الموجودة في الطرف) تكون ملونة بنفس اللون مثنى مثنى.
2. إذا تم تلوين القمم الطرفية بنفس اللون مثنى مثنى، فيمكن تلوين بقية القمم.
3. المخطط الماسي مخطط مستو.

[تحرير] تحويل المخطط العادي للمخطط مستو

ليكن G مخطط عادي و (a,b) ارتباط يقطع بعض الارتباطات الأخرى. يتم وضع مخطط ماسي مكان كل تقاطع.

فنحصل على مخطط مستو. و انطلاقا من خصائص المخطط الماسي، يكون المخطط المستوي ملونا بثلاثة ألوان إذا وفقط إذا كان المخطط العادي ملون أيضا بثلاثة ألوان.