Coloration graphique en 3 couleurs avec l'utilisation de la fonction donnée

Question

J'ai la fonction three_colorability(n,E) qui donne un résultat vrai (lorsque le graphique avec ces arêtes et sommets peut être coloré avec 3 couleurs) ou faux (sinon).(! Il n'y a pas de paramètre pour savoir ce qui a déjà été coloré) Nous supposons que cette fonction fonctionne en complexité de temps linéaire.

Je dois créer un algorithme à 3 couleurs du graphe non orienté G donné avec l'utilisation de la fonction donnée qui fonctionnera en temps polynomial.

Je n'arrive pas à trouver une solution à ce problème.

Answer 1

Ajoutez 3 nouveaux nœuds, nommés C1, C2 et C3 par la couleur qu'ils représentent.Ajouter des arêtes entre les nouveaux nœuds (C1,C2), (C2,C3) et (C1,C3).Si three_colorability(V,E) est vrai que three_colorability(V+{C1,C2,C3},E+{(C1,C2),(C2,C3),(C1,C3)}) est également vrai.

Pour chaque sommet (original) v, three_colorability() renvoie vrai pour au moins un des graphiques avec deux bords ajoutés de {(v,C1), (v,C2), (v,C3)}.Par exemple.si three_colorability() renvoie vrai pour un graphique avec des arêtes ajoutées {(v,C2), (v,C3)}, cela signifie que v peut être coloré avec la couleur 1.

Pour trouver la couleur de tous les sommets, recherchez progressivement la couleur des sommets et ajoutez ces 2 arêtes dans un graphique.