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)=\{v_1,\dots ,v_n\}$ 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=\{x_1,\dots ,x_n\},Y=\{y_1,\dots ,y_n\}$, d. h. $X$ und $Y$ haben jeweils dieselbe Kardinalität wie $V(G)$
• für alle $i=1,\dots ,n$ ist $x_i$ adjazent zu $y_i$
• für $i=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

• Vorlage:Literatur