Assoziierter bipartiter Graph

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

Konstruktion

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

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