Assoziierter bipartiter Graph

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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

Es sei ein endlicher Graph mit Knoten und Kanten . Dem Graphen wird sein assoziierter bipartiter Graph wie folgt zugeordnet[1]

  • 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.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. R. Balakrishnan, K. Ranganathan: A textbook of graph theory. 2. Auflage. Universitext. Springer, New York 2012, ISBN 978-1-4614-4528-9, Kapitel 9.5