Kantengraph
aus Wikipedia, der freien Enzyklopädie
[Bearbeiten] Definition
Der Kantengraph (engl. line graph) L(G): = (V',E') eines ungerichteten Graphen G = (V,E) ist in der Graphentheorie der Graph mit folgenden Eigenschaften:
- V' = E, das heißt jede Kante von G ist ein Knoten in L(G).
- Je zwei Knoten aus V' sind adjazent, wenn die zugehörigen Kanten aus E adjazent sind.
Jeder Kantengraph ist ein Perfekter Graph.
[Bearbeiten] Beispiel
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}}.
Aus dem Original G wird jetzt ein neuer Graph konstruiert, indem jede Kante 
von G zu einem neuen Knoten 
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.
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 
