Questi algoritmi di colorazione grafica sono equivalenti?

Question

Questi algoritmi di colorazione grafica sono equivalenti?

#1 da (0 voti)

3

Supponiamo di voler colorare i vertici di un grafico in modo avido, dato un ordine predeterminato di questi vertici. L'obiettivo è evitare di dare due vertici adiacenti (collegati da un bordo) dello stesso colore.

Mi chiedo se questi due algoritmi sono equivalenti:

Algoritmo 1: considera ciascun vertice (nell'ordine specificato) e assegna il colore più piccolo disponibile.

Algoritmo 2: anche se non tutti i vertici sono colorati, le classi di colori vengono create in sequenza cercando di includere i vertici non colorati, non adiacenti (nell'ordine specificato) nella classe corrente.

Sono quasi certo che questi due algoritmi siano equivalenti. In effetti, considera Algorithm 2 su un grafico con 5 vertici. Supponiamo che la prima classe di colore abbia i vertici 1, 3, 5. Ciò significa che i vertici 2 e 4 non possono prendere il colore 1. Quindi in Algorithm 1, il vertice 1 prende il colore 1, il vertice 2 assume il colore 2, il vertice 3 prende il colore 1 il vertice 4 assumerebbe il colore 2 o 3 e il vertice 5 assumerebbe il colore 1. Questo semplice esempio mi convince che è vero, ma ovviamente non è una prova. Possiamo trasformarlo in una dimostrazione rendendola più generica o possiamo trovare un esempio di contatore?

algorithms graph algorithm-analysis

posta Kuifje 04.11.2015 - 00:11

fonte

1 risposta

Leggi altre domande sui tag algorithms graph algorithm-analysis

Comando Separazione query. Come gestire la gestione degli errori per le funzioni di muting che ritornano void Redux Saga pattern per risposte server grandi e non specifici

score 0 · Accepted Answer

Penso che tu abbia ragione, entrambi gli algoritmi sono equivalenti. Guarda quale dei vertici di un grafo arbitrario ottiene il primo (più piccolo) colore C1 da entrambi gli algoritmi. È facile vedere che quelli sono gli stessi, perché entrambi gli algoritmi fanno essenzialmente lo stesso - iterare sui vertici nell'ordine dato, assegnare C1 o

un colore diverso (algoritmo 1)
nessun colore (algoritmo 2)

a un vertice, con il vincolo di usare C1 quando la vertice successiva non è adiacente a un vertice precedentemente colorato da C1.

Ora puoi applicare lo stesso argomento per il prossimo colore C2, usando tutti i vertici non colorati in C1, poi C3 e così via, che ti porta induttivamente alla stessa colorazione totale.