Kantengraph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Graph G
Konstruktion von L(G)
Kantengraph L(G)

Der Kantengraph oder Line-Graph ist ein Begriff aus der Graphentheorie. Er definiert zu einem gegebenen Graphen einen neuen Graphen der durch die Vertauschung von Knoten und Kanten entsteht.

Definition[Bearbeiten | Quelltext bearbeiten]

Der Kantengraph oder Line-Graph eines einfachen Graphen ist in der Graphentheorie der Graph mit folgenden Eigenschaften:

  1. , das heißt jede Kante von ist ein Knoten in .
  2. , das heißt je zwei Knoten aus sind in adjazent, wenn die zugehörigen Kanten aus einen gemeinsamen Endknoten haben, also in adjazent sind.

Beispiel[Bearbeiten | Quelltext bearbeiten]

Das folgende Beispiel veranschaulicht die Konstruktion des Kantengraphen zu einem gegebenen Graphen . Der abgebildete Graph hat die Knotenmenge und die Kantenmenge .

Aus dem Original wird jetzt ein neuer Graph konstruiert, indem jede Kante von zu einem neuen Knoten in 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 . Zurück bleibt der Kantengraph .

Wieder als Mengen ausgedrückt erhält man

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

  • Lutz Volkmann: Fundamente der Graphentheorie. Springer, Wien 1996, ISBN 3-211-82774-9, S. 180ff

Weblinks[Bearbeiten | Quelltext bearbeiten]