在图论中,图
所对应的线图是一张能够反映
中各边邻接性的图,记作
。简单来说,
将
中的每条边各自抽象成一个顶点;如若原图中两条边相邻,那么就给线图中对应顶点之间连接一条边。因为线图将原图的边化作了顶点,所以也可以将其视作原图的一种对偶。
哈斯勒·惠特尼证明了:假定图
是连通的,那么除了一种特殊情况外,我们总能根据线图
的结构还原出
的结构。以该定理为中介,可以证明线图的许多其它性质。线图总是无爪图,即线图的所有导出子图均不是
。
图
的线图
定义如下:
该定义也可以用图论的语言表述如下:设
,那么
,且
。
下面的例子演示了由原图生成线图的流程。
原图
制作线图的过程
结果
根据线图的定义,若性质/概念P仅取决于原图
中边的邻接性,那么P便可以转移(或者说对偶)到线图
上去变成性质/概念P',刻画线图顶点的邻接属性。例如,图
中的一个匹配指的是图中一组不相交的边,把这一概念平移到线图上去,就等价于线图的一组不相邻的顶点——用术语来说即线图上的一个独立集。
下面就列举了原图和线图之间的若干联系:
惠特尼同构定理阐述了以下事实:设有连通图
和
且它们均不是三角形
或爪形
。如果
,那么
。也就是说,除了极特殊的情形,图
的结构可以由线图
的结构中唯一地恢复出来。
任何的线图都是无爪的,亦即不包含
作为导出子图。因此,任意含有偶数个顶点的连通线图都存在完美匹配。
线图
的邻接矩阵
的全部特征值都不小于-2。这是因为
,其中
是原图
的关联矩阵(incidence matrix)。又由于矩阵
是半正定的,所以
的任何特征值
均满足
。
Beineke给出了线图的一种等价刻画:
是某图的线图当且仅当
不包含九种类型的导出子图(见右图)。
如果
的最小度至少为5,那么只有左边一列和右边一列是必要的。换言之,此时,
是某图的线图当且仅当
不包含六种类型的导出子图(见右图的左边一列和右边一列)。