Come si partiziona un grafico bipartito per colore?

Question

Ad esempio, supponiamo di avere un grafo G = (V, E) dove

V = {A, B, C, D}
E = {(A, B), (A, D), (C, D)}

Questo grafico è bipartito e quindi può essere diviso in due gruppi disgiunti {A, C} e {B, D}. La mia prima ipotesi è che posso semplicemente camminare sul grafico e assegnare colori alternati a ciascun vertice. È questo il caso, o è più complicato/più semplice di questo? Esistono algoritmi noti per questo?

Answer 1

La prima ipotesi è corretta - attraversa il grafico e si alterna.

L'algoritmo dovrebbe essere semplice. Manterrei due code di nodi da visitare, una per ogni colore. Disattiva alternativamente i nodi delle code, contrassegna il colore e sposta nella coda i nodi adiacenti non visitati per il colore opposto. Termina quando il numero di nodi visitati + la lunghezza di entrambe le code = numero di nodi nel grafico.

Answer 2

Se si è certi che il grafico è biparte, allora si può solo assegnare i colori alternati per attraversare ogni vertice, in quanto sostiene che:

Un grafo è bipartito se e solo se è 2- colorable.

Answer 3

Da Wikipedia (http://en.wikipedia.org/wiki/Bipartite_graph)

Se è collegato un grafo bipartito, il suo bipartition può essere definita dalla parità delle distanze da qualsiasi vertice scelto arbitrariamente v: un sottoinsieme costituito dai vertici alla stessa distanza di v e l'altro sottoinsieme è costituito dai vertici a distanza dispari a v.

Così, si può verificare in modo efficiente se un grafico è bipartito usando questa tecnica di parità per assegnare i vertici ai due sottoinsiemi U e V, separatamente all'interno di ciascun connesso componente del grafico, quindi esaminare ogni spigolo per verificare che abbia gli endpoint assegnati t o sottoinsiemi diversi.

Answer 4

Attraversa il grafico e si alterna, se non riesce significa che il tuo grafico non è bipartito.

Answer 5

Solo nel caso in cui qualcuno è curioso, ecco il codice mi si avvicinò con:

def dfs(root, colorings): 
    to_visit1 = deque() 
    to_visit2 = deque() 
    to_visit1.append(root) 
    while len(to_visit1) != 0 or len(to_visit2) != 0: 
     dfs_color(to_visit1, to_visit2, True, colorings) 
     dfs_color(to_visit2, to_visit1, False, colorings) 

def dfs_color(queue, opposite_queue, color, colorings): 
    while len(queue) != 0: 
    v = queue.pop() 
    if v in adjacency_list: 
     colorings[v] = color 
     neighbors = adjacency_list[v] 
     del adjacency_list[v] 
     for neighbor in neighbors: 
     opposite_queue.append(neighbor) 

Certo, questo non è il mio codice migliore. Sto usando True/False come colore perché quando ho usato la ricorsione, è stato facile dire semplicemente not color. Certo, ho dovuto cambiarlo perché ho fatto esplodere il mio stack su grafici più grandi. Anche per dare credito dove dovuto, questo codice è basato sul codice wikipedia per DFS.

Anche se, come è stato sottolineato, penso che questo possa essere solo un BFS mascherato.

Answer 6

L'ho implementato nel mio graph drawing tool, è possibile vedere il mio codice in JavaScript.

Ho appena segnato il primo vertice come partizione sinistra, quindi segnato ricorsivamente i suoi vicini come partizione corretta, contrassegna in modo ricorsivo i loro vicini come partizione sinistra ... Se trovi il nodo contrassegnato correttamente, interrompi la ricorsione di questo ramo. Se trovi un nodo contrassegnato in modo errato, il grafico non è bipartito.

Forse si può fare più semplice, ma durante questi mesi ho avuto alcuni dischi Prolog - giorni di codifica Haskell, forse aveva colpito il mio cervello e ora vedo la ricorsione in tutto :-D