Come faccio a partizionare un grafo bipartito per colore?
-
11-09-2019 - |
Domanda
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?
Soluzione
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.
Altri suggerimenti
Traverse il grafico e si alternano, se non riuscì significa che il grafico non è bipartita.
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.
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.
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
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.