请输入您要查询的字词:

 

单词 LineGraph
释义

line graph


Let G be a graph. The line graphMathworldPlanetmath of G is denoted by L(G) and is defined as follows. The vertices of L(G) are the edges of G. Two vertices of L(G) are connected by an edge if and only if the corresponding edges in G form a path (which must be a directed path if G is a digraphMathworldPlanetmath).

Example 1.

Let G be the undirected graph on the vertex set V(G)={a,b,c,d} and edge set E(G)={ab,bc,cd,bd}. Then the line graph L(G) has vertex set V(L(G))={ab,bc,cd,bd}. Since ab and bc are incidentPlanetmathPlanetmathPlanetmath in G, they are connected by an edge in L(G). We label this edge by the unique walk from a to c determined by these edges, namely abc. With this notation, the edge set is E(L(G))={abc,abd,bcd,bdc,cbd}.

\\xymatrix&a\\ar@-[d]ab&&&ab\\ar@-[dl]abc\\ar@-[dr]abd&&b\\ar@-[dl]bc\\ar@-[dr]bd&&bc\\ar@-[rr]bcd\\ar@-[dr]cbd&&bd\\ar@-[dl]bdcc\\ar@-[rr]cd&&d&&cd

Above we display the graphs G (left) and L(G) (right).

Part of the reason for interest in line graphs is the following observation:

Proposition.

If a graph is Eulerian, then its line graph is Hamiltonian.

This follows immediately from the fact that a sequence of incident edges in G is a sequence of incident vertices in L(G).

Example 2.

Let Bn be the de Bruijn digraph on binary strings of length n. Then for n2, the next de Bruijn digraph can be obtained by taking the line graph of the previous one, that is, Bn+1=L(Bn).

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 18:52:55