线图
在图论中，图formula_1所对应的线图是一张能够反映formula_1中各边邻接性的图，记作formula_3。简单来说，formula_3将formula_1中的每条边各自抽象成一个顶点；如若原图中两条边相邻，那么就给线图中对应顶点之间连接一条边。因为线图将原图的边化作了顶点，所以也可以将其视作原图的一种对偶。
哈斯勒·惠特尼证明了：假定图formula_1是连通的，那么除了一种特殊情况外，我们总能根据线图formula_3的结构还原出formula_1的结构。以该定理为中介，可以证明线图的许多其它性质。线图总是无爪图，即线图的所有导出子图均不是formula_9。
正式定义.
图formula_1的线图formula_3定义如下：
该定义也可以用图论的语言表述如下：设formula_16，那么formula_17，且formula_18。
例子.
下面的例子演示了由原图生成线图的流程。
性质.
由原图转移过来的性质.
根据线图的定义，若性质／概念P仅取决于原图formula_1中边的邻接性，那么P便可以转移（或者说对偶）到线图formula_3上去变成性质／概念P'，刻画线图顶点的邻接属性。例如，图formula_1中的一个匹配指的是图中一组不相交的边，把这一概念平移到线图上去，就等价于线图的一组不相邻的顶点——用术语来说即线图上的一个独立集。
下面就列举了原图和线图之间的若干联系：
惠特尼同构定理.
惠特尼同构定理阐述了以下事实：设有连通图formula_36和formula_37且它们均不是三角形formula_38或爪形formula_9。如果formula_40，那么formula_41。也就是说，除了极特殊的情形，图formula_1的结构可以由线图formula_3的结构中唯一地恢复出来。
其它性质.
任何的线图都是无爪的，亦即不包含formula_9作为导出子图。因此，任意含有偶数个顶点的连通线图都存在完美匹配。
线图formula_3的邻接矩阵formula_46的全部特征值都不小于-2。这是因为formula_47，其中formula_48是原图formula_1的关联矩阵（incidence matrix）。又由于矩阵formula_50是半正定的，所以formula_51的任何特征值formula_52均满足formula_53。
等价刻画.
Beineke给出了线图的一种等价刻画：formula_54是某图的线图当且仅当formula_54不包含九种类型的导出子图（见右图）。
如果formula_54的最小度至少为5，那么只有左边一列和右边一列是必要的。换言之，此时，formula_54是某图的线图当且仅当formula_54不包含六种类型的导出子图（见右图的左边一列和右边一列）。
生成维基百科快照图片，大概需要3-30秒！
如果网站内容有侵犯您的版权
请联系：pinbor@iissy.com
请联系：pinbor@iissy.com
Copyright ©2014 iissy.com, All Rights Reserved.