Assoziierter bipartiter Graph

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

Konstruktion

Es sei ${\displaystyle G}$ ein endlicher Graph mit Knoten ${\displaystyle V(G)=\left\{v_{1},\ldots ,v_{n}\right\}}$ und Kanten ${\displaystyle E(G)}$. Dem Graphen ${\displaystyle G}$ wird sein assoziierter bipartiter Graph ${\displaystyle B(G)}$ wie folgt zugeordnet[1]

• die Knotenmenge von ${\displaystyle B(G)}$ ist eine disjunkte Vereinigung ${\displaystyle X\cup Y}$ mit ${\displaystyle X=\left\{x_{1},\ldots ,x_{n}\right\},Y=\left\{y_{1},\ldots ,y_{n}\right\}}$, d. h. ${\displaystyle X}$ und ${\displaystyle Y}$ haben jeweils dieselbe Kardinalität wie ${\displaystyle V(G)}$
• für alle ${\displaystyle i=1,\ldots ,n}$ ist ${\displaystyle x_{i}}$ adjazent zu ${\displaystyle y_{i}}$
• für ${\displaystyle i\not =j}$ ist ${\displaystyle x_{i}}$ genau dann adjazent zu ${\displaystyle y_{j}}$, wenn ${\displaystyle (v_{i}v_{j})\in E(G)}$ gilt.

Dieser Graph ist nach Konstruktion ein bipartiter Graph.

Anwendungen

• Chordal bipartiter Graph

Literatur

• 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

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