Coloration graphique en 3 couleurs avec l'utilisation de la fonction donnée
-
20-12-2019 - |
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.
La solution
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.