Kantengraph - LinkFang.de





Kantengraph


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\}| e_1 \cap e_2 \neq \emptyset\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

Literatur

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

Weblinks


Kategorien: Graphentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Kantengraph (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.