الرسم البياني 3-ألوان التلوين مع استخدام وظيفة معينة
-
20-12-2019 - |
سؤال
لدي وظيفة ثلاثة الألوان (ن ، ه) الذي يعطي الناتج صحيح(عندما الرسم البياني مع تلك الحواف والرؤوس يمكن أن تكون ملونة مع 3 ألوان) أو كاذبة(إن لم يكن).(!لا توجد معلمة لمعرفة ما تم تلوينه بالفعل) نفترض أن هذه الوظيفة تعمل في تعقيد زمني خطي.
لا بد لي من جعل 3-خوارزمية التلوين من الرسم البياني غير الموجه ز مع استخدام وظيفة معينة والتي سوف تعمل في وقت متعدد الحدود.
لا أستطيع التوصل إلى حل لهذا.
المحلول
إضافة 3 العقد الجديدة ، واسمه C1
, C2
و C3
حسب اللون الذي يمثلونه.إضافة حواف بين العقد الجديدة (C1,C2)
, (C2,C3)
و (C1,C3)
.إذا three_colorability(V,E)
صحيح من three_colorability(V+{C1,C2,C3},E+{(C1,C2),(C2,C3),(C1,C3)})
صحيح أيضا.
لكل رأس (أصلي) v
, three_colorability()
يعود صحيحا لواحد على الأقل من الرسوم البيانية مع إضافة اثنين من حافة {(v,C1), (v,C2), (v,C3)}
.على سبيل المثال.إذا three_colorability()
يعود صحيح للرسم البياني مع حواف المضافة {(v,C2), (v,C3)}
, ، هذا يعني ذلك v
يمكن أن تكون ملونة مع اللون 1.
للعثور على اللون لجميع القمم ، تجد تدريجيا لون قمة الرأس وإضافة هذه الحواف 2 في الرسم البياني.