Linegraph

Ein Linegraph ist in der Graphentheorie ein Graph $L(G):=(V',E')$ zu einem Graphen $G=(V,E)$ mit folgenden Eigenschaften:

• $E=V'$, dass heißt jede Kante von $G$ ist eine Ecke in $L(G)$.
• Je zwei Ecken aus $V'$ sind adjazent, wenn die zugehörigen Kanten aus $E$ inzident sind.

Jeder Linegraph ist ein Perfekter Graph.

Datei:Linegraph.png

Beispiel eines Linegraphen

Siehe auch: Kantengraph.