Kantengraph

Datei:Line graph construction (original).png

Graph <math>G</math>

Datei:Line graph construction (intermediate).png

Konstruktion von <math>L(G)</math>

Datei:Line graph construction (result).png

Kantengraph <math>L(G)</math>

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

Der Kantengraph oder Line-Graph <math>L(G):=(V',E')</math> eines einfachen Graphen <math>G=(V,E)</math> ist in der Graphentheorie der Graph mit folgenden Eigenschaften:

1. <math>V'=E</math>, das heißt, jede Kante von <math>G</math> ist ein Knoten in <math>L(G)</math>.
2. <math>E' = \left\{\left\{e_1,e_2\right\}\mid e_1, e_2 \in E, |e_1 \cap e_2| =1\right\}</math>, das heißt, je zwei Knoten aus <math>V'</math> sind in <math>L(G)</math> adjazent, wenn die zugehörigen Kanten aus <math>E</math> einen gemeinsamen Endknoten haben, also in <math>G</math> adjazent sind.

Beispiel

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

Aus dem Original <math>G</math> wird jetzt ein neuer Graph konstruiert, indem jede Kante <math>e \in E</math> von <math>G</math> zu einem neuen Knoten <math>v' \in V'</math> in <math>L(G)</math> 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 <math>G</math>. Zurück bleibt der Kantengraph <math>L(G)</math>.

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

Eigenschaften

• Der Kantengraph des Kreisgraphen <math>C_n</math> 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 <math>S_n</math> ist der vollständige Graph <math>K_n</math>.
• Der Kantengraph eines bipartiten Graphen ist ein perfekter Graph.
• Jeder Kantengraph besitzt eine Krausz-Partition.

Literatur

• {{#invoke:Vorlage:Literatur|f}}

Weblinks

• Lutz Volkmann: Graphen an allen Ecken und Kanten. Skript 2011 (2. Version), S. 148ff (PDF; 3,51 MB)