https://www.arabsciencepedia.org/w/index.php?action=history&feed=atom&title=%D8%AA%D9%84%D9%88%D9%8A%D9%86_%D9%85%D8%AE%D8%B7%D8%B7_%D9%85%D8%B3%D8%AA%D9%88_%D8%A8%D8%AB%D9%84%D8%A7%D8%AB%D8%A9_%D8%A3%D9%84%D9%88%D8%A7%D9%86تلوين مخطط مستو بثلاثة ألوان - تاريخ المراجعة2026-04-13T01:11:09Zتاريخ التعديل لهذه الصفحة في الويكيMediaWiki 1.43.6https://www.arabsciencepedia.org/w/index.php?title=%D8%AA%D9%84%D9%88%D9%8A%D9%86_%D9%85%D8%AE%D8%B7%D8%B7_%D9%85%D8%B3%D8%AA%D9%88_%D8%A8%D8%AB%D9%84%D8%A7%D8%AB%D8%A9_%D8%A3%D9%84%D9%88%D8%A7%D9%86&diff=225&oldid=prevWikiSysop: ١ مراجعة: الصفحات في تصنيف رياضيات2010-11-12T21:16:09Z<p>١ مراجعة: الصفحات في تصنيف رياضيات</p>
<p><b>صفحة جديدة</b></p><div>{{مسألة NP كاملة}}<br />
هو امتداد لمسألة [[مشكلة تلوين المخطط|تلوين مخطط]]، يكون في [[مخطط مستوي]] وتعريف المسألة كما يلي:<br />
<br />
# G مخطط مستوي<br />
# السؤال: هل يمكن تلوين المخطط G باستعمال ثلاثة ألوان فقط بحيث تلون كل قمتين مرتبطتين بلونين مختلفين.<br />
<br />
== الاختصار ==<br />
يبين هذا الاختصار أن تلوين مخطط مستوي هو من المسائل NP الكاملة.<br />
<br />
انطلاقا من مسألة [[تلوين مخطط بثلاثة ألوان]]، يتم تحويل كل مخطط عادي إلى مخطط مستوي، وذلك بوضع مخطط مستو خاص يسمى '''المخطط الماسي''' (انظر الصورة)، مكان تقاطع الارتباطات (انظر الصورة).<br />
=== خصائص المخطط الماسي ===<br />
[[ملف:Gadget 3COL-plan.PNG|تصغير|المخطط الماسي]] <br />
يحمل المخطط الماسي الخصائص الآتية:<br />
<br />
# عند تلوين المخطط الماسي بثلاثة ألوان، القمم الطرفية (الموجودة في الطرف) تكون ملونة بنفس اللون مثنى مثنى.<br />
# إذا تم تلوين القمم الطرفية بنفس اللون مثنى مثنى، فيمكن تلوين بقية القمم.<br />
# المخطط الماسي مخطط مستو.<br />
=== تحويل المخطط العادي للمخطط مستو ===<br />
ليكن G مخطط عادي و(a,b) ارتباط يقطع بعض الارتباطات الأخرى. يتم وضع مخطط ماسي مكان كل تقاطع.<br />
[[ملف:Transformetoplanargraph.PNG|تصغير|تموضع المخطط الماسي]] فنحصل على مخطط مستو. وانطلاقا من خصائص المخطط الماسي، يكون المخطط المستوي ملونا بثلاثة ألوان إذا وفقط إذا كان المخطط العادي ملون أيضا بثلاثة ألوان.<br />
<br />
{{بذرة رياضيات}}<br />
<br />
{{بوابة رياضيات}}<br />
<br />
[[تصنيف:رياضيات]]<br />
[[تصنيف:نظرية المخططات]]<br />
[[تصنيف:مسائل NP كاملة]]</div>WikiSysop