Algorithmus - Bestimmung bipartiter Graphen

• Involvierte Definitionen:
  • Bipartiter Graph
  • Graph
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Algorithmus: Bestimmung bipartiter Graphen

Sei ein Graph.

Um festzustellen, ob bipartit ist, können wir wie folgt vorgehen:

1. Starte an einem beliebigen Knoten.
2. Färbe diesen ein (bspw. rot).
3. Färbe seine Nachbarn anders ein (bspw. blau).
4. Fahre mit 1. fort, bis alle Knoten eingefärbt sind. Müsste ein Knoten unterschiedliche Farben erhalten, so kann der Graph nicht bipartit sein.

Anmerkung

Der linke Graph ist offensichtlich bipartit, der rechte Graph kann nicht bipartit sein.