تلوين كامل

📅 آخر تحديث: ١ أغسطس ٢٠٢٦
✍️ نُشر في: ١ أغسطس ٢٠٢٦
📷 يحتوي على 3 صور
الموسوعة الحرة
تلوين كامل لمخطط كليبيش باستخدام 8 ألوان. يظهر كل زوج من الألوان على حافة واحدة على الأقل. لا يوجد تلوين كامل باستخدام ألوان أكثر: في أي تلوين بـ 9 ألوان، سيظهر لون ما عند رأس واحد فقط، ولن يكون هناك عدد كافٍ من الرؤوس المجاورة لتغطية جميع الأزواج التي تتضمن هذا اللون. لذلك، فإن العدد اللوني لمخطط كليبيش هو 8.

في نظرية المخططات ، يُعرف التلوين الكامل بأنه تلوين (صحيح) للرؤوس، حيث يظهر كل زوج من الألوان على زوج واحد على الأقل من الرؤوس المتجاورة . وبصورة مكافئة، يكون التلوين الكامل بسيطًا بمعنى أنه لا يمكن تحويله إلى تلوين صحيح بألوان أقل عن طريق دمج أزواج من فئات الألوان. أما العدد اللوني ψ( G ) للمخطط G فهو الحد الأقصى لعدد الألوان الممكنة في أي تلوين كامل للمخطط G.

التلوين الكامل هو عكس التلوين المتناغم ، والذي يتطلب ظهور كل زوج من الألوان على زوج واحد على الأكثر من الرؤوس المتجاورة.

نظرية التعقيد

يُعدّ إيجاد ψ( G ) مسألة تحسين . ويمكن صياغة مسألة القرار للتلوين الكامل على النحو التالي:

مثال: رسم بياني G = ( V , E ) وعدد صحيح موجب k
السؤال: هل يوجد تقسيم لـ V إلى k أو أكثر من المجموعات المنفصلة V 1 ، V 2 ، … ، V k بحيث تكون كل Vi مجموعة مستقلة لـ G، وبحيث يكون لكل زوج من المجموعات المتميزة Vi ، V j ، فإن Vi ∪ V j ليست مجموعة مستقلة.

يُعد تحديد العدد اللوني مسألة صعبة من نوع NP ؛ أما تحديد ما إذا كان أكبر من عدد معين فهو مسألة كاملة من نوع NP ، كما أوضح ياناكاكيس وغافريل في عام 1978 من خلال التحويل من مسألة المطابقة الدنيا القصوى. [ 1 ]

لاحظ أن أي تلوين للرسم البياني بأقل عدد من الألوان يجب أن يكون تلوينًا كاملاً، لذا فإن تقليل عدد الألوان في التلوين الكامل هو مجرد إعادة صياغة لمشكلة تلوين الرسم البياني القياسية .

الخوارزميات

لأي قيمة ثابتة لـ k ، من الممكن تحديد ما إذا كان العدد اللوني لرسم بياني معين يساوي k على الأقل ، في وقت خطي. [ 2 ]

تسمح مسألة التحسين بالتقريب، ويمكن تقريبها ضمن نطاقيا(|V|/سجل⁡|V|){\displaystyle O\left(|V|/{\sqrt {\log |V|}}\right)}نسبة التقريب . [ 3 ]

فئات خاصة من الرسوم البيانية

تنطبق خاصية اكتمال NP لمسألة العدد غير اللوني أيضًا على بعض الفئات الخاصة من الرسوم البيانية: الرسوم البيانية ثنائية الأجزاء ، [ 2 ] ومكملات الرسوم البيانية ثنائية الأجزاء (أي الرسوم البيانية التي لا تحتوي على مجموعة مستقلة من أكثر من رأسين)، [ 1 ] والرسوم البيانية التكميلية والرسوم البيانية الفاصلية ، [ 4 ] وحتى على الأشجار. [ 5 ]

بالنسبة لمكملات الأشجار، يمكن حساب العدد اللوني في وقت متعدد الحدود. [ 6 ] أما بالنسبة للأشجار، فيمكن تقريبه ضمن عامل ثابت. [ 3 ]

من المعروف أن العدد اللوني لرسم بياني مكعب فائق الأبعاد n يتناسب معن2ن{\displaystyle {\sqrt {n2^{n}}}}لكن ثابت التناسب غير معروف بدقة. [ 7 ]

مراجع

  1. 1 2 مايكل ر. غاري وديفيد س. جونسون (1979)، الحواسيب والاستعصاء: دليل لنظرية اكتمال NP ، دبليو إتش فريمان، ISBN 978-0-7167-1045-5A1.1: GT5، صفحة 191.
  2. 1 2 فاربر، م.؛ هان، ج.؛ هيل، ب .؛ ميلر، د. ج. (1986)، "حول العدد اللوني للرسوم البيانية"، مجلة نظرية التوافيق، السلسلة ب ، 40 (1): 21-39 ، doi : 10.1016/0095-8956(86)90062-6.
  3. 1 2 تشودري، أميتاب؛ فيشواناثان، سوندار (2001)، "خوارزميات تقريبية للعدد اللوني"، مجلة الخوارزميات ، 41 (2): 404-416 ، CiteSeerX 10.1.1.1.5562 ، doi : 10.1006/jagm.2001.1192 ، S2CID 9817850  .
  4. ↑ بودليندر، هـ. (1989)، "العدد غير اللوني هو مسألة NP-كاملة للرسوم البيانية التكميلية والرسوم البيانية الفاصلية"، رسائل معالجة المعلومات ، 31 (3): 135-138 ، doi : 10.1016/0020-0190(89)90221-4 ، hdl : 1874/16576.
  5. ↑ مانلوف، د.؛ ماكديارميد، س. (1995)، "تعقيد التلوين المتناغم للأشجار"، الرياضيات التطبيقية المنفصلة ، ​​57 ( 2-3 ): 133-144 ، doi : 10.1016/0166-218X(94)00100-R.
  6. ↑ ياناكاكيس، م.؛ جافريل، ف. (1980)، "مجموعات هيمنة الحواف في الرسوم البيانية"، مجلة SIAM للرياضيات التطبيقية ، 38 (3): 364-372 ، doi : 10.1137/0138030.
  7. ↑ رويشمان، ي. (2000)، "حول العدد اللوني للمكعبات الفائقة"، مجلة نظرية التوافيق، السلسلة ب ، 79 (2): 177-182 ، doi : 10.1006/jctb.2000.1955.