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.

DefinitionBearbeiten

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.

BeispielBearbeiten

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  .

EigenschaftenBearbeiten

  • Der Kantengraph des Kreisgraphen   ist isomorph zu seinem Ausgangsgraphen. Kreisgraphen (bzw. Graphen, deren sämtliche Komponenten Kreisgraphen sind) sind die einzigen Graphen mit dieser Eigenschaft.
  • Der Kantengraph des Sterngraphen   ist der vollständige Graph  .
  • Der Kantengraph eines bipartiten Graphen ist ein perfekter Graph.
  • Jeder Kantengraph besitzt eine Krausz-Partition.

LiteraturBearbeiten

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

WeblinksBearbeiten