Bipartiter Graph
Bipartiter Graph Definition
Ein bipartiter Graph (bipartit: zweigeteilt) ist ein ungerichteter Graph mit mindestens 2 Knoten, wenn man daraus disjunkte Knotenmengen (zum Beispiel A und B) so bilden kann, dass gilt: es gibt nur Kanten zwischen Elementen von A und Elementen von B (nicht innerhalb von A oder innerhalb von B).
Vollständig bipartiter Graph
Sind alle derartigen Kanten vorhanden, ist der Graph vollständig bipartit.
Beispiel
Beispiel: bipartiter Graph
Ein sehr einfacher zweigeteilter Graph könnte so aussehen:
Der Knoten 1 ist mit dem Knoten 2 und mit dem Knoten 3 verbunden. Zwischen dem Knoten 2 und dem Knoten 3 gibt es keine Verbindung.
Daraus lassen sich folgende zwei Mengen bilden:
A: {1}
B: {2, 3}
Es gibt nur Kanten zwischen den Elementen der Menge A (nur ein Element: Knoten 1) und B (Knoten 2 und 3). Innerhalb der Mengen A und B gibt es keine Kanten.
Dieser Graph ist auch vollständig bipartit, alle möglichen Kanten von A nach B sind vorhanden.