Colorazione del grafico 3 colori con l'uso della funzione data

Question

Ho la funzione Three_Colorability (N, E) che fornisce il conto in uscita (quando il grafico con tali bordi e vertici può essere colorato con 3 colori) o falso (se non).(! Non c'è parametro per sapere cosa è già stato colorato) Supponiamo che questa funzione funzioni nella complessità del tempo lineare.

Devo effettuare un algoritmo a 3 colori del grafico indenneto indicato G con l'uso della funzione data che funzionerà in tempo polinomiale.

Non posso venire alla soluzione a questo.

Answer 1

Aggiungi 3 nuovi nodi, denominati C1, C2 e C3 per colore che rappresentano.Aggiungere i bordi tra i nuovi nodi (C1,C2), (C2,C3) e (C1,C3).Se three_colorability(V,E) è vero che three_colorability(V+{C1,C2,C3},E+{(C1,C2),(C2,C3),(C1,C3)}) è anche vero.

Per ciascun (originale) v vertice, three_colorability() restituisce true per almeno uno dei grafici con due margine aggiunto di {(v,C1), (v,C2), (v,C3)}.Per esempio.Se three_colorability() restituisce true per il grafico con i bordi aggiunti {(v,C2), (v,C3)}, significa che v può essere colorato con colore 1.

Per trovare il colore per tutti i vertici, trovare in modo incrementale il colore vertice e aggiungere questi 2 bordi in un grafico.