Line Graph

Line Graph

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:

  • line graph — ➔ graph1 * * * line graph UK US noun [C] GRAPHS & CHARTS ► LINE CHART(Cf. ↑line chart) …   Financial and business terms

  • Line graph — This article is about the mathematical concept. For statistical presentation method, see line chart. In graph theory, the line graph L(G) of undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The name… …   Wikipedia

  • line graph — noun : a graph in which points representing values of a variable for suitable values of an independent variable are connected by a broken line * * * line graph UK US noun [countable] [singular line graph plural line graphs] …   Useful english dictionary

  • line graph — UK / US noun [countable] Word forms line graph : singular line graph plural line graphs maths a graph that uses lines to show the relationship between numbers or measurements that change …   English dictionary

  • line graph — graph which plots one value over a period of time …   English contemporary dictionary

  • line graph — noun Date: circa 1924 a graph in which points representing values of a variable for suitable values of an independent variable are connected by a broken line …   New Collegiate Dictionary

  • Line graph of a hypergraph — The line graph of a hypergraph is the graph whose vertex set is the set of the hyperedges of the hypergraph, with two edges adjacent when they have nonempty intersection. In other words, the line graph of a hypergraph is the intersection graph of …   Wikipedia

  • Planar straight-line graph — (PSLG) is a term used in computational geometry for an embedding of a planar graph in the plane such that its edges are mapped into straight line segments. [cite book author = Franco P. Preparata and Michael Ian Shamos | title = Computational… …   Wikipedia

  • Digital line graph — USGS Logo A Digital Line Graph (DLG) is a cartographic map feature represented in digital vector form that is distributed by the U.S. Geological Survey (USGS). DLGs are collected from USGS maps and are distributed in large , intermediate and… …   Wikipedia

  • broken-line graph — UK US noun [C] ► GRAPHS & CHARTS a graph that shows information as dots (= small spots) that are connected by straight lines …   Financial and business terms

Share the article and excerpts

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