K_3,3: bipartiter Graph mit
3 Knoten pro Teilmenge

Ein Graph heißt in der Graphentheorie bipartit (auch paar), falls seine Knoten sich in zwei Teilmengen aufteilen lassen (Bipartition), so dass es zwischen den Knoten innerhalb einer Teilmenge keine Kantenn gibt. Damit sind die Teilmengen stabile Mengen und die Bipartition impliziert eine mögliche 2-Färbung des Graphen. Umgekehrt sind alle 2-färbbaren Graphen bipartit.

Für bipartite Graphen lassen sich viele Grapheigenschaftenen effektiv berechnen, die für allgemeinen Graphen nur schwer oder nicht in polynomieller Zeit bestimmen werden können.

Mit einem einfachen Algorithmus, der auf Tiefensuche basiert, lässt sich in Linerarer Zeit bestimmen, ob ein Graph bipartit ist, und eine gültige Partition bzw. 2-Färbung ermitteln.

Eigenschaften bipartiter Graphen:

• Die Paarungszahl entspricht der Knotenüberdeckungszahl
• Mit dem Algorithmus von Hopcroft und Karp lässt sich in O(√nm) eine größte Paarung finden und darüber auch die Stabilitätszahl bestimmen
• Der chromatische Index entspricht seinem Maximalgrad. Eine gültige Kantenfärbung lässt sich in O(nm) bestimmen
• Ein regulärerer bipartiter Graph besitzt ein perfektes Matching