الرسم البياني 3-ألوان التلوين مع استخدام وظيفة معينة

Question

لدي وظيفة ثلاثة الألوان (ن ، ه) الذي يعطي الناتج صحيح(عندما الرسم البياني مع تلك الحواف والرؤوس يمكن أن تكون ملونة مع 3 ألوان) أو كاذبة(إن لم يكن).(!لا توجد معلمة لمعرفة ما تم تلوينه بالفعل) نفترض أن هذه الوظيفة تعمل في تعقيد زمني خطي.

لا بد لي من جعل 3-خوارزمية التلوين من الرسم البياني غير الموجه ز مع استخدام وظيفة معينة والتي سوف تعمل في وقت متعدد الحدود.

لا أستطيع التوصل إلى حل لهذا.

Answer 1

إضافة 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 في الرسم البياني.