wake-up-neo.com

Wie finde ich heraus, ob eine Grafik zweiteilig ist?

Ich habe versucht, den zweiteiligen Graphen zu verstehen. Nach meinem Verständnis ist dies ein Graph G, der in zwei Untergraphen U und V unterteilt werden kann. Der Schnittpunkt von U und V ist also eine Nullmenge und die Vereinigung ist Graph G. .. Ich versuche herauszufinden, ob ein Graph zweigeteilt ist oder BFS nicht verwenden. Noch ist mir nicht klar, wie wir das mit BFS finden können.

Nehmen wir an, wir haben die unten definierte Grafik.

a:e,f
b:e
c:e,f,h
d:g,h
e:a,b,c
f:a,c,g
g:f,d
h:c,d

Was ich hier brauche, ist eine schrittweise Erklärung, wie dieser Graph zweiteilig ist oder kein BFS verwendet.

14
user2738777

Aus GeeksforGeeks

Es folgt ein einfacher Algorithmus, um herauszufinden, ob ein bestimmter Graph Birpartit ist oder nicht, wobei die Breadth First Search (BFS) verwendet wird:

  1. Weisen Sie dem Quellscheitel die rote Farbe zu (in Set U).
  2. Färben Sie alle Nachbarn mit BLAUER Farbe (in Set V).
  3. Färben Sie alle Nachbarn mit der Farbe ROT ein (setzen Sie sie in Set U).
  4. Weisen Sie auf diese Weise allen Scheitelpunkten Farbe zu, sodass alle Einschränkungen des m-Way-Farbproblems mit m = 2 erfüllt werden.
  5. Wenn wir beim Zuweisen von Farben einen Nachbarn finden, der dieselbe Farbe wie der aktuelle Scheitelpunkt hat, kann der Graph nicht mit 2 Scheitelpunkten gefärbt werden (oder der Graph ist nicht zweiteilig).

Eine zweigeteilte Grafik ist möglich, wenn die Diagrammfärbung mit .__ möglich ist. zwei Farben, so dass Scheitelpunkte in einem Satz mit dem gleichen Farbe.

HINWEIS: -

-> Es ist möglich, einen Zyklusgraphen mit zwei Farben einzufärben.

-> Es ist nicht möglich, einen Zyklusgraphen mit zwei Farben zu färben.

EDIT: -

Wenn ein Graph nicht verbunden ist, hat may mehr als eine Partition. Sie müssen alle diese Komponenten separat mit dem oben genannten Algorithmus prüfen.

Für verschiedene nicht verbundene Untergrafiken desselben Diagramms müssen Sie diese Bipartitionsprüfung für alle separat ausführen, wobei derselbe Algorithmus verwendet wird, der oben erläutert wurde. Alle verschiedene nicht verbundene Untergrafiken desselben Diagramms werden für ihren eigenen Satz von Bipartitionen verantwortlich sein. 

Und der Graph wird als zweiteilig bezeichnet, WENN UND NUR, WENN sich jede seiner verbundenen Komponenten als zweigeteilt erweist.

25
Am_I_Helpful

Hier ist eine Prolog CLP (FD) -Lösung. Modellieren Sie einfach jede Kante im Diagramm als Variable in der Domäne 0..1. Dann modelliere jeden Scheitelpunkt als eine Gleichung:

X #\= Y.

Dann geben Sie das Etikett aus. Wenn die Beschriftung eine Lösung findet, sind Sie fertig. Es kann jedoch mehrere Lösungen finden. Hier ist ein Beispiel für dein Beispiel:

Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.23)
Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam

:- use_module(library(clpfd)).
problem(L) :- L=[A,B,C,D,E,F,G],
    A #\= E, A #\= F,
    B #\= E,
    C #\= E, C #\= F, C #\= H,
    D #\= G, D #\= H,
    E #\= A, E #\= B, E #\= C,
    F #\= A, F #\= C, F #\= G,
    G #\= F, G #\= D,
    H #\= C, H #\= D.

?- problem(L), L ins 0..1, label(L).
L = [0, 0, 0, 1, 1, 1, 0] ;
L = [1, 1, 1, 0, 0, 0, 1].

Funktioniert auch in GNU Prolog, SICStus Prolog, Jekejeke Minlog usw. meistens mit jedem Prolog-System, das CLP (FD) implementiert. Alternativ könnte auch CLP (B) oder Dif/2 verwendet werden.

2
j4n bur53

Von der Carnegie Mellon University:

Man erinnere sich daran, dass ein Graph G = (V, E) als zweiteilig bezeichnet wird, wenn seine Scheitelpunktmenge V in zwei disjunkte Mengen V1, V2 unterteilt werden kann, so dass alle Kanten in E einen Endpunkt in V1 und einen Endpunkt haben in V2.

(Quelle: http://www.cs.cmu.edu/~15251/homework/hw5.pdf )

Sind Sie sicher, dass Sie BFS verwenden müssen? Bestimmen, ob ein Diagramm ermittelt, ob für zwei Teile die Zykluslänge erkannt werden muss und DFS für die Zykluserkennung wahrscheinlich besser geeignet ist als BFS. 

Wie auch immer, ein Diagramm, wenn und nur dann zweiteilig, wenn es keine ungeraden Zyklen hat. Wenn Sie DFS verwenden dürfen, können Sie DFS im Diagramm anzeigen und nach Hinterkanten suchen, um das Vorhandensein von Zyklen zu erkennen, und DFS-Zeitstempel verwenden, um die Größe jedes Zyklus zu berechnen. 

2
Xceptional

Erstellen Sie einen bfs-Baum. Wenn sich zwischen den Scheiteln derselben Baumebene Baumkanten befinden, ist der Graph nicht zweiteilig.

1
ashu beckham

sie können diesen Link wie unten angegeben verweisen
Dieser Code enthält die Prüfung, ob ein bestimmter Graph zweiteilig ist oder nicht den BFS-Algorithmus verwendet
https://github.com/gangwar-yogendra/Graph/blob/master/BipartiteGraphUsingBFS.c

0
Yogendra Kumar

Im Folgenden wird ein BFS-Ansatz beschrieben, um zu prüfen, ob der Graph zweigeteilt ist.

  • c = 0
  • wähle einen Knoten x und setze x.class = c
  • sei ys die Knoten, die von BFS erhalten wurden
    • c = 1-c
    • für y in ys set y.class = c
    • wenn eine y in ys einen Nachbarn z mit z.class == c hat, ist der Graph nicht zweiteilig
    • wiederholen, bis keine Knoten mehr gefunden werden
  • das Diagramm ist zweiteilig

Dies setzt voraus, dass der Graph eine einzelne verbundene Komponente ist. Wenn dies nicht der Fall ist, führen Sie diese Prozedur einfach für jede Komponente aus.

0
mitchus