Come faccio a partizionare un grafo bipartito per colore?

Question

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

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

Questo grafico è bilaterale, e quindi può essere suddiviso in due insiemi disgiunti {A, C} e {B, D}. La mia prima risposta è che posso semplicemente a piedi il grafico e assegnare colori alternati ad ogni vertice. E 'questo il caso, o è più complicato / semplice di questo? Ci sono algoritmi noti per questo?

Answer 1

La prima ipotesi è corretta -. Traverso il grafico e si alternano

L'algoritmo deve essere semplice. Mi piacerebbe continuare a due code di nodi da visitare, uno per ogni colore. Pop nodi al largo delle code alternativamente, segnare il suo colore, e spingere tutti i nodi non visitati adiacenti in coda per il colore opposto. Terminerà quando il numero di nodi visitati + la lunghezza delle due code = numero di nodi del grafo.

Answer 2

Traverse il grafico e si alternano, se non riuscì significa che il grafico non è bipartita.

Answer 3

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

  

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

Answer 4

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 a v e l'altro sottoinsieme costituito dai vertici a distanza dispari al v.

Così, si può efficacemente testare se un grafo è bipartito utilizzando questa tecnica parità per assegnare i vertici delle due sottoinsiemi U e V, separatamente in ogni componente connessa del grafo, e quindi esaminare ciascun bordo per verificare che abbia endpoint assegnato a diversi sottoinsiemi.

Answer 5

ho implementato nel mio disegno grafico strumento , si può vedere il mio codice in JavaScript.

Ho appena segnato primo vertice come a sinistra partity, quindi in modo ricorsivo segnato E 'vicini come partity destra, in modo ricorsivo contrassegnare i loro vicini di casa come partity sinistra ... Se si trova correttamente segnata nodo, smette di ricorsione di questo ramo. Se si trova uncorrectly marcata nodo, grafico non è bipartita.

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

Answer 6

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 il colore, perché quando ho usato la ricorsione, ha reso facile dire solo not color. Naturalmente, ho dovuto cambiare perché ho saltato il mio stack su grafici grandi. Anche per dare credito dove a causa, questo codice è basato sul codice di Wikipedia per DFS .

Anche se, come è stato sottolineato, credo che questo potrebbe essere solo un BFS mascherata.