Bipartiter Graph

K_3,3: vollständig bipartiter Graph mit 3 Knoten pro Teilmenge

Ein bipartiter oder paarer Graph ist ein mathematisches Modell für Beziehungen zwischen den Elementen zweier Mengen. Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen.

Ein einfacher Graph G = (V, E) (V Menge der Knoten, E Menge der Kanten) heißt bipartit oder paar, falls sich seine Knoten in zwei disjunkte Teilmengen A und B aufteilen lassen, sodass 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. Vereinfacht dargestellt, ist ein bipartiter Graph ein Graph, in dem zwei Gruppen von Knoten existieren, innerhalb derer keine Knoten miteinander verbunden sind.

Der Graph G heißt vollständig bipartit, falls eine Bipartition {A, B} existiert, sodass jeder Knoten aus A mit jedem Knoten aus B verbunden ist. Einen solchen Graphen bezeichnet man auch als K_{m, n} , wobei m und n die Anzahl der Knoten von A und B sind.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Bipartiter Graph aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung