Bipartiter Graph (auch paarer Graph genannt) ist ein Graph, dessen Knoten sich in zwei disjunkte Teil Mengen A und B zerlegen lassen, sodass jede Kante genau einen Knoten aus A mit einem aus B verbindet. Innerhalb derselben Teilmenge gibt es keine Kanten. Ein klassisches Beispiel ist die Zuordnung von Personen (Teilmenge A) zu Aufgaben (Teilmenge B): Jede Verbindung steht für „kann diese Aufgabe übernehmen“.
Eigenschaften
- 2-Färbbarkeit: Ein Graph ist genau dann bipartit, wenn sich seine Knoten mit zwei Farben so einfärben lassen, dass benachbarte Knoten nie dieselbe Farbe tragen. Der Breitensuche-Algorithmus prüft das in linearer Zeit.
- Keine ungeraden Kreise: Ein Graph ist genau dann bipartit, wenn er keinen Zyklus ungerader Länge enthält.
- Matching: Bipartite Graphen sind die Grundlage der Matching-Theorie, etwa bei der Frage, ob sich alle Personen einer Gruppe einer passenden Aufgabe zuordnen lassen (Hall-Heiratssatz).
- Vollständig bipartit: Der Graph K_{m,n} verbindet jeden Knoten von A (m Knoten) mit jedem Knoten von B (n Knoten).
Erkennung per 2-Färbung
Man startet an einem beliebigen Knoten, färbt ihn rot, alle Nachbarn blau, deren Nachbarn wieder rot – und so weiter. Trifft man dabei auf einen Knoten, der bereits mit der falschen Farbe markiert ist, liegt ein ungerader Zyklus vor, und der Graph ist nicht bipartit. Die Färbung entspricht genau der Zerlegung in die beiden Teil Mengen.
Anwendungen
- Zuordnungsprobleme: Stundenpläne, Jobvergabe, Raumplanung
- Empfehlungssysteme: Nutzer-Artikel-Matrix, bei der Nutzer und Artikel die beiden Teil Mengen bilden
- Netzwerkflüsse: Transportprobleme zwischen Angebots- und Nachfrageknoten
- Soziale Netzwerke: Paarungen in Dating-Plattformen oder Projekt-Teambildung
In der Adjazenzmatrix eines bipartiten Graphen lässt sich die Knotenmenge so anordnen, dass nur zwei der vier Matrixblöcke Einträge enthalten – ein nützliches Erkennungsmerkmal. Der Grad eines Knotens und die Zusammenhangskomponenten verhalten sich wie in jedem anderen ungerichteten Graphen.