线图
在图论中，图<math>G</math>所对应的线图是一张能够反映<math>G</math>中各边邻接性的图，记作<math>L(G)</math>。简单来说，<math>L(G)</math>将<math>G</math>中的每条边各自抽象成一个顶点；如若原图中两条边相邻，那么就给线图中对应顶点之间连接一条边。因为线图将原图的边化作了顶点，所以也可以将其视作原图的一种对偶。
哈斯勒·惠特尼证明了：假定图<math>G</math>是连通的，那么除了一种特殊情况外，我们总能根据线图<math>L(G)</math>的结构还原出<math>G</math>的结构[1]。以该定理为中介，可以证明线图的许多其它性质。线图总是无爪图，即线图的所有导出子图均不是<math>K_{1,3}</math>。
正式定义[编辑]
图<math>G</math>的线图<math>L(G)</math>定义如下：
- <math>L(G)</math>的一个顶点对应<math>G</math>的一边
- <math>L(G)</math>的顶点相邻当且仅当它们在<math>G</math>对应的边相邻（有公共顶点）。
该定义也可以用图论的语言表述如下：设<math>G = (V,E)</math>，那么<math>L(G) = (E, \tilde{E})</math>，且<math>(e_1, e_2) \in \tilde{E} \iff e_1 \cap e_2 \neq \emptyset</math>。
例子[编辑]
下面的例子演示了由原图生成线图的流程。
-
原图
-
制作线图的过程
-
结果
.png){kind=link}
.png){kind=link}
.png){kind=link}
性质[编辑]
由原图转移过来的性质[编辑]
根据线图的定义，若性质／概念P仅取决于原图<math>G</math>中边的邻接性，那么P便可以转移（或者说对偶）到线图<math>L(G)</math>上去变成性质／概念P'，刻画线图顶点的邻接属性。例如，图<math>G</math>中的一个匹配指的是图中一组不相交的边，把这一概念平移到线图上去，就等价于线图的一组不相邻的顶点——用术语来说即线图上的一个独立集。
下面就列举了原图和线图之间的若干联系：
- 若原图是连通的，线图也是。
- 若两个图同构，那么它们的线图也同构。
- 若<math>G</math>的顶点数和边数分别为<math>n</math>和<math>m</math>，那么<math>L(G)</math>的顶点数和边数分别是<math>m</math>和<math display="inline">\sum_{v} \binom{\deg(v)}{2}</math>。
- <math>\chi_E(G) = \chi_V(L(G))</math>，即原图的边色数等于线图的点色数。
- <math>G</math>中的一个匹配对应了<math>L(G)</math>中的一个独立集，且其大小相等。于是，<math>G</math>中最大匹配的大小等于<math>L(G)</math>最大独立集的大小。借助这一关系，可以通过求解后者来求解前者，但反之不总是可行，因为并非所有图都能表示为某个<math>G</math>的线图。在计算机科学中，最大匹配问题和最大独立集问题是两个重要的问题。前者已经被高效解决（Edmonds' Blossom Algorithm）；而后者则是NP完全问题，被普遍认为无法高效求解。
- 若<math>G</math>存在欧拉回路，则<math>L(G)</math>存在哈密顿回路，但反之不然。
惠特尼同构定理[编辑]
惠特尼同构定理[1]阐述了以下事实：设有连通图<math>G_1</math>和<math>G_2</math>且它们均不是三角形<math>K_3</math>或爪形<math>K_{1,3}</math>。如果<math>L(G_1) \cong L(G_2)</math>，那么<math>G_1 \cong G_2</math>。也就是说，除了极特殊的情形，图<math>G</math>的结构可以由线图<math>L(G)</math>的结构中唯一地恢复出来。
其它性质[编辑]
任何的线图都是无爪的，亦即不包含<math>K_{1,3}</math>作为导出子图。因此，任意含有偶数个顶点的连通线图都存在完美匹配。
线图<math>L(G)</math>的邻接矩阵<math>A_{m \times m}</math>的全部特征值都不小于-2。这是因为<math>A = J^{\operatorname{T}}J - 2I</math>，其中<math>J_{n \times m}</math>是原图<math>G</math>的关联矩阵（incidence matrix）。又由于矩阵<math>J^{\operatorname{T}}J</math>是半正定的，所以<math>A</math>的任何特征值<math>\lambda</math>均满足<math>\lambda + 2 \geq 0</math>。
等价刻画[编辑]
Beineke给出了线图的一种等价刻画：<math>H</math>是某图的线图当且仅当<math>H</math>不包含九种类型的导出子图（见右图）。[2]
如果<math>H</math>的最小度至少为5，那么只有左边一列和右边一列是必要的。换言之，此时，<math>H</math>是某图的线图当且仅当<math>H</math>不包含六种类型的导出子图（见右图的左边一列和右边一列）。
参考文献[编辑]
- ^ 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）.
- ^ 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） （English）.