„Assoziierter bipartiter Graph“ – Versionsunterschied
Zur Navigation springen
Zur Suche springen
[gesichtete Version] | [gesichtete Version] |
Inhalt gelöscht Inhalt hinzugefügt
Literatur ergänzt |
|||
Zeile 7: | Zeile 7: | ||
* für alle <math>i=1,\ldots,n</math> ist <math>x_i</math> adjazent zu <math>y_i</math> |
* für alle <math>i=1,\ldots,n</math> ist <math>x_i</math> adjazent zu <math>y_i</math> |
||
* für <math>i\not=j</math> ist <math>x_i</math> genau dann adjazent zu <math>y_j</math>, wenn <math>(v_iv_j)\in E(G)</math> gilt. |
* für <math>i\not=j</math> ist <math>x_i</math> genau dann adjazent zu <math>y_j</math>, wenn <math>(v_iv_j)\in E(G)</math> gilt. |
||
== Literatur == |
|||
* {{Literatur|Titel=Mathematische Grundlagen Der Ingenieurinformatik|Autor=Peter Jan Pahl, Rudolf Damrath|Verlag=Springer Verlag|Ort=Heidelberg|Jahr=2000|ISBN=9783642570131|Seiten=558|Online={{Google Buch|BuchID=4K0geUrF2gYC|Seite=8558}}}} |
|||
== Einzelnachweise == |
== Einzelnachweise == |
Version vom 18. Dezember 2013, 22:28 Uhr
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 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.
Literatur
- Peter Jan Pahl, Rudolf Damrath: Mathematische Grundlagen Der Ingenieurinformatik. Springer Verlag, Heidelberg 2000, ISBN 978-3-642-57013-1, S. 558 (eingeschränkte Vorschau in der Google-Buchsuche).
Einzelnachweise
- ↑ Balakrishnan, R.; Ranganathan, K.: A textbook of graph theory. Second edition. Universitext. Springer, New York, 2012. ISBN 978-1-4614-4528-9; 978-1-4614-4529-6 (Kapitel 9.5)