Problem mit Graphen-Bipartit

Neue Frage »

Hurrikan Auf diesen Beitrag antworten »
Problem mit Graphen-Bipartit
Hallo,
in dem Lexikon hier steht bei bipartit,das man mit einem einfachen Algorithmus ,der auf der Tiefensuche basiert,bestimmen kann ob ein Graph bitartit ist oder nicht.
Leider wird der Algorithmus nicht näher erklärt.

Kann mir jemand erklären,wie ich herausfinde,ob ein Graph bitartit ist oder nicht?
SirJective Auf diesen Beitrag antworten »

Hallo Hurrikan,

kann ich davon ausgehen, dass du weißt, wie ein Tiefensuch-Algorithmus prinzipiell funktioniert?

Du musst überprüfen, ob sich der Graph mit zwei Farben färben lässt. Dazu beginnst du bei irgendeinem Knoten, färbst ihn mit Farbe 1. Alle seine Nachbarknoten färbst du mit Farbe 2. Dann besuchst du (rekursiv) alle diese Nachbarknoten: Deren Nachbarknoten färbst du mit Farbe 1 und besuchst (rekursiv) deren Nachbarknoten...

Wenn du bei irgendeinem Nachbarknoten feststellst, dass er bereits eine Farbe hat, schaust du, ob es die Farbe ist, die er bekommen soll. Wenn er eine andere Farbe hat, weißt du, dass der Graph nicht bipartit ist und kannst abbrechen; andernfalls irgnorierst du den Graphen beim Besuch der Nachbarn.

Gruss,
SirJective
Hurrikan Auf diesen Beitrag antworten »

Aah,

Ja,wie die Tiefensuche funktioniert weiß ich.
Vielen Dank für die Hilfe Mit Zunge
Meisterz Auf diesen Beitrag antworten »

Hallo,

da sich an der Laufzeit ncihts verändern wird, kann man auch erst die Breitensuche in einem Knoten starten und den Breitensuchbaum aufbauen. Dann färbt man anschliessend abwechselnd in der Höhe des Baumes die Knoten. Dann überprüft man, ob irgendwo eine Kante existiert die Knoten gleicher Farbe verbinden.

Gruß,

Meister
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »