Linegraph

Linegraph

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:

  1. V' = E, das heißt jede Kante von G ist ein Knoten in L(G).
  2. Je zwei Knoten aus V' sind in L(G) adjazent, wenn die zugehörigen Kanten aus E einen gemeinsamen Endknoten haben, also in G adjazent sind.

Jeder Kantengraph eines bipartiten Graphen ist ein Perfekter Graph.

Beispiel

Graph G

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}}.

Konstruktion von L(G)

Aus dem Original G wird jetzt ein neuer Graph konstruiert, indem jede Kante e \in E von G zu einem neuen Knoten v' \in V'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.

Kantengraph L(G)

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 L(G) = (V', \{\{\{1, 2\}, \{1, 3\}\}, \{\{1, 2\}, \{1, 4\}\}, \{\{1, 2\}, \{2, 5\}\}, \dots\})


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Abstand (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Adjazent — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Adjazenz — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Adjazenz (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Ausgangsgrad — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Benachbart (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Bogen (Graph) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Chromatische Zahl — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Chromatischer Index — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Eingangsgrad — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”