Assoziierter bipartiter Graph
Teilgebiet der Mathematik
In der Graphentheorie, einem Teilgebiet der Mathematik kann man jedem Graphen seinen assoziierten bipartiten Graphen zuordnen.
Konstruktion Bearbeiten
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.
Anwendungen Bearbeiten
Literatur Bearbeiten
- Peter Jan Pahl, Rudolf Damrath: Mathematische Grundlagen der Ingenieurinformatik. Springer Verlag, Heidelberg 2000, ISBN 3-642-57013-5, S. 558 (eingeschränkte Vorschau in der Google-Buchsuche).
Einzelnachweise Bearbeiten
- ↑ 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