Kantengraph

Definition

Der Kantengraph oder Linegraph $L(G):=(V',E')$ eines ungerichteten Graphen $G=(V,E)$ ist in der Graphentheorie der Graph mit folgenden Eigenschaften:

1. $V'=E$, das heißt jede Kante von $G$ ist ein Knoten in $L(G)$.
2. Je zwei Knoten aus $V'$ sind adjazent, wenn die zugehörigen Kanten aus $E$ adjazent sind.

Jeder Kantengraph ist ein Perfekter Graph.

Beispiel

Datei:Kantengraph-original.png

Graph G

Das folgende Beispiel veranschaulicht die Konstruktion des Kantengraphen $L(G)$ zu einem gegebenen Graphen $G=(V,E)$. Der abgebildete Graph $G$ hat die Knotenmenge $V=\{1,2,3,4,5\}$ und die Kantenmenge $E=\{\{1,2\},\{1,3\},\{1,4\},\{2,5\},\{3,4\},\{4,5\}\}$.

Datei:Kantengraph-konstruktion.png

Konstruktion von L(G)

Aus dem Original $G$ wird jetzt ein neuer Graph konstruiert, indem jede Kante $e\in E$ von $G$ zu einem neuen Knoten $v'\in V'$in $L(G)$ wird (durch die grüne Ellipse auf den originalen Kanten veranschaulicht). Die neu entstandenen Knoten werden genau dann miteinander verbunden, wenn die Kanten im Originalgraphen aneinanderstießen.

Datei:Kantengraph-resultat.png

Kantengraph L(G)

Das Resultat der Konstruktion erhält man durch Ausblenden des Originalgraphen $G$. Zurück bleibt der Kantengraph $L(G)$.

Wieder als Mengen ausgedrückt erhält man $L(G)=(V',\{\{\{1,2\},\{1,3\}\},\{\{1,2\},\{1,4\}\},\{\{1,2\},\{2,5\}\},\dots \})$