線圖

维基百科,自由的百科全书
跳转至: 导航搜索
原圖
製作線圖的過程
結果

圖論上,一個圖G線圖L(G)是:

  • L(G)的一個頂點對應G的一邊
  • L(G)的頂點相鄰若且唯若它們在G對應的邊相鄰(有公共頂點)。
有些圖總不是線圖

性質[编辑]

  • 若原圖是連通的,線圖也是。
  • \chi_E(G) = \chi_V(L(G)),原圖的邊色數等於線圖的點色數