Wie partitionieren ich einen zweiteiligen Graphen von Farbe?

Question

Zum Beispiel: Angenommen ich habe einen Graphen G = (V, E), wobei

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

Dieser Graph ist bipartite, und kann somit in zwei disjunkte Mengen aufgeteilt werden, {A, C} und {B, D}. Meine erste Vermutung ist, dass ich einfach die Grafik laufen kann, und weise wechselnde Farben zu jedem Eckpunkt. Ist dies der Fall, oder ist es komplizierter / einfacher als das? Gibt es bekannte Algorithmen für das?

Answer 1

Ihre erste Vermutung ist richtig -. Verfahrweg der Grafik und alternativen

Der Algorithmus sollte einfach sein. Ich würde zwei Warteschlangen von Knoten halten zu besuchen, eine für jede Farbe. Pop Knoten die Warteschlangen abwechselnd markieren seine Farbe aus und schieben alle nicht besucht benachbarten Knoten in die Warteschlange für die entgegengesetzte Farbe. Beenden, wenn die Anzahl der besuchten Knoten + die Länge der beiden Warteschlangen Anzahl der Knoten in der Grafik =.

Answer 2

Traverse die Grafik und wechseln sich ab, wenn es nicht gelungen ist es bedeutet, dass Ihr Diagramm nicht bipartit ist.

Answer 3

Wenn Sie sicher sind, dass die Graph biparte ist, dann können Sie nur zuweisen Farben, um sie für Wechsel jede Ecke durchlaufen, da es gilt:

  

Ein Graph ist zweiteiligen, wenn und nur wenn sie 2-färbbar ist.

Answer 4

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

Wenn ein zweiteiliger Graph verbunden ist, dessenderen Zweiteilung kann durch die Parität der Abstände von jedem beliebig gewählten Punkt v definiert werden: eine Teilmenge besteht aus der Vertices in gleichem Abstand zu v und die andere Untermenge besteht aus den Scheitelpunkten an den ungeraden Abstand v.

So kann man effizient testen, ob ein Graph unter Verwendung dieser Paritäts Technik bipartite ist Vertices auf die beiden Untergruppen innerhalb jeder verbundenen Komponente des Graphen U und V, separat zuweisen und dann jede Kante untersuchen, um zu überprüfen, dass es Endpunkte hat zugewiesen verschiedene Untergruppen.

Answer 5

ich es in meinem Diagramm Malwerkzeug , Sie meinen Code in JavaScript sehen.

I markiert nur erste Vertex als partity links, dann ist es die Nachbarn als rechts partity rekursiv markiert, markieren rekursiv ihre Nachbarn links partity ... Wenn Sie richtig markiert Knoten finden, Rekursion dieser Branche stoppen. Wenn Sie uncorrectly markierte Knoten finden, Graph ist nicht bipartite.

Vielleicht kann es einfacher gemacht werden, aber in den letzten paar Monaten hatte ich einige harte Prolog - Haskell Tage Codierung, vielleicht war es mein Gehirn betroffen und jetzt sehe ich Rekursion in alles :-D

Answer 6

Für den Fall, jemand ist neugierig, hier ist der Code kam ich mit:

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)

Zugegeben, das ist nicht mein bester Code. Ich verwende True / False als die Farbe, weil, wenn ich Rekursion verwendet, es es einfach nur sagen, not color. Natürlich hatte ich es zu ändern, weil ich auf größere Graphen meinen Stack blies. Auch geben Kredit, in dem auf Grund wird dieser Code auf der Wikipedia-Code basiert für DFS .

Obwohl, wie bereits erwähnt wurde, ich denke, das ist nur eine verschleierte BFS sein kann.