Colorazione del grafico 3 colori con l'uso della funzione data
-
20-12-2019 - |
Domanda
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.
Soluzione
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.