Bipartiter Graph
framed|K3,3: bipartiter Graph mit 3 Knoten pro Teilmenge
Ein einfacher Graph G = (V,E) heißt in der Graphentheorie bipartit (auch paar), falls sich seine Knoten in zwei disjunkte Teilmengen A und B aufteilen lassen, so dass zwischen den Knoten innerhalb beider Teilmengen keine Kanten verlaufen. Das heißt für eine Kante 
gilt entweder 
und 
oder aber 
und 
. Die Menge {A, B} bezeichnet man dann als Bipartition des Graphen G.
Der Graph G heißt sogar vollständig bipartit, falls eine Bipartition {A,B} existiert, für die jedes Paar (a,b) mit 
und 
die Kante {a,b} zu E gehört. Einen solchen Graphen bezeichnet man auch als Km,n, wobei m und n die Anzahl der Knoten von A bzw. B sind.
Folgerungen
Die Teilmengen A und B sind also schon nach Definition 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 Grapheneigenschaften mit weniger Aufwand berechnen, als dies im allgemeinen Fall möglich ist.
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
- 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ärer bipartiter Graph besitzt ein perfektes Matching.