In der Graphentheorie, einem Teilgebiet der Mathematik kann man jedem Graphen seinen assoziierten bipartiten Graphen zuordnen.

Konstruktion Es sei ein endlicher Graph mit Knoten und Kanten . Dem Graphen wird sein assoziierter bipartiter Graph wie folgt zugeordnetR. Balakrishnan, K. Ranganathan: A textbook of graph theory. 2. Auflage. Universitext. Springer, New York 2012, ISBN 978-1-4614-4528-9, Kapitel 9.5

die Knotenmenge von ist eine disjunkte Vereinigung mit , d. h. und haben jeweils dieselbe Kardinalität wie für alle ist adjazent zu für ist genau dann adjazent zu , wenn gilt.

Dieser Graph ist nach Konstruktion ein bipartiter Graph.

Anwendungen

Chordal bipartiter Graph

Literatur

Einzelnachweise

Kategorie:Graph Kategorie:Graphentheorie