線圖

在图论中，图G所对应的线图是一张能够反映G中各边邻接性的图，记作L(G)。简单来说，L(G)将G中的每条边各自抽象成一个顶点；如若原图中两条边相邻，那么就给线图中对应顶点之间连接一条边。因为线图将原图的边化作了顶点，所以也可以将其视作原图的一种对偶。

哈斯勒·惠特尼证明了：假定图G是连通的，那么除了一种特殊情况外，我们总能根据线图L(G)的结构还原出G的结构。以该定理为中介，可以证明线图的许多其它性质。线图总是无爪图，即线图的所有导出子图均不是K_{1,3}。

正式定義
圖G的線圖L(G)定義如下：

• L(G)的一個頂點對應G的一邊

• L(G)的頂點相鄰若且唯若它們在G對應的邊相鄰（有公共頂點）。

该定义也可以用图论的语言表述如下：设G = (V,E)，那么L(G) = (E, \tilde{E})，且(e_1, e_2) \in \tilde{E} \iff e_1 \cap e_2 \neq \emptyset。

例子
下面的例子演示了由原图生成线图的流程。

File:Line graph construction (original).png|原圖
File:Line graph construction (intermediate).png|製作線圖的過程
File:Line graph construction (result).png|結果

性質
由原图转移过来的性质
根据线图的定义，若性质／概念P仅取决于原图G中边的邻接性，那么P便可以转移（或者说对偶）到线图L(G)上去变成性质／概念P'，刻画线图顶点的邻接属性。例如，图G中的一个匹配指的是图中一组不相交的边，把这一概念平移到线图上去，就等价于线图的一组不相邻的顶点——用术语来说即线图上的一个独立集。

下面就列举了原图和线图之间的若干联系：

• 若原圖是連通的，線圖也是。
• 若两个图同构，那么它们的线图也同构。
• 若G的顶点数和边数分别为n和m，那么L(G)的顶点数和边数分别是m和\sum_{v} \binom{\deg(v)}{2}。
• \chi_E(G) = \chi_V(L(G))，即原圖的邊色數等於線圖的點色數。
• G中的一个匹配对应了L(G)中的一个独立集，且其大小相等。于是，G中最大匹配的大小等于L(G)最大独立集的大小。借助这一关系，可以通过求解后者来求解前者，但反之不总是可行，因为并非所有图都能表示为某个G的线图。在计算机科学中，最大匹配问题和最大独立集问题是两个重要的问题。前者已经被高效解决（Edmonds' Blossom Algorithm）；而后者则是NP完全问题，被普遍认为无法高效求解。
• 若G存在欧拉回路，则L(G)存在哈密顿回路，但反之不然。

惠特尼同构定理
惠特尼同构定理

如果H的最小度至少为5，那么只有左边一列和右边一列是必要的。换言之，此时，H是某图的线图当且仅当H不包含六种类型的导出子图（见右图的左边一列和右边一列）。

参考文献