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

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

正式定義

 線圖 定義如下:

  •  的一個頂點對應 的一邊
  •  的頂點相鄰若且唯若它們在 對應的邊相鄰(有公共頂點)。

该定义也可以用图论的语言表述如下:设 ,那么 ,且 

例子

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

性質

 
有些圖總不是線圖

由原图转移过来的性质

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

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

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

惠特尼同构定理

惠特尼同构定理[1]阐述了以下事实:设有连通图  且它们均不是三角形 或爪形 。如果 ,那么 。也就是说,除了极特殊的情形,图 的结构可以由线图 的结构中唯一地恢复出来。

其它性质

任何的线图都是无爪的,亦即不包含 作为导出子图。因此,任意含有偶数个顶点的连通线图都存在完美匹配。

线图 邻接矩阵 的全部特征值都不小于-2。这是因为 ,其中 是原图 关联矩阵(incidence matrix)。又由于矩阵 是半正定的,所以 的任何特征值 均满足 

等价刻画

 
九种排除在线图之外的导出子图

Beineke给出了线图的一种等价刻画: 是某图的线图当且仅当 不包含九种类型的导出子图(见右图)。[2]

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

参考文献

  1. ^ 1.0 1.1 Whitney, Hassler. Congruent Graphs and the Connectivity of Graphs. American Journal of Mathematics. 1932-01, 54 (1): 150 [2020-10-23]. doi:10.2307/2371086. (原始内容存档于2020-10-26). 
  2. ^ Beineke, Lowell W. Characterizations of derived graphs. Journal of Combinatorial Theory. 1970-09-01, 9 (2): 129–135 [2020-10-23]. ISSN 0021-9800. doi:10.1016/S0021-9800(70)80019-9. (原始内容存档于2020-10-30) (英语).