Assoziierter bipartiter Graph
# 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
