查看“︁線圖”︁的源代码

{{Translating|[[:en:line graph]]||tpercent=80|time=2020-10-23T06:44:31+00:00}}

在[[图论]]中，[[图]]<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>的结构<ref name=":0">{{Cite journal|title=Congruent Graphs and the Connectivity of Graphs|url=https://www.jstor.org/stable/2371086?origin=crossref|last=Whitney|first=Hassler|date=1932-01|journal=American Journal of Mathematics|issue=1|doi=10.2307/2371086|volume=54|pages=150|access-date=2020-10-23|archive-date=2020-10-26|archive-url=https://web.archive.org/web/20201026040828/https://www.jstor.org/stable/2371086?origin=crossref}}</ref>。以该定理为中介，可以证明线图的许多其它性质。线图总是[[无爪图]]，即线图的所有[[导出子图]]均不是<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>。

==例子==
下面的例子演示了由原图生成线图的流程。
<gallery widths="135px" heights="135px">
File:Line graph construction (original).png|原圖
File:Line graph construction (intermediate).png|製作線圖的過程
File:Line graph construction (result).png|結果
</gallery>

==性質==
[[File:Ind subg not in line graph.png|frame|有些圖總不是線圖]]

=== 由原图转移过来的性质 ===
根据线图的定义，若性质／概念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>存在[[哈密顿路径问题|哈密顿回路]]，但反之不然。

=== 惠特尼同构定理 ===
[[图同构|惠特尼同构定理]]<ref name=":0" />阐述了以下事实：设有连通图<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>。

== 等价刻画 ==
[[File:Forbidden line subgraphs.svg|缩略图|九种排除在线图之外的导出子图]]
Beineke给出了线图的一种等价刻画：<math>H</math>是某图的线图当且仅当<math>H</math>不包含九种类型的导出子图（见右图）。<ref>{{Cite journal|title=Characterizations of derived graphs|url=http://www.sciencedirect.com/science/article/pii/S0021980070800199|last=Beineke|first=Lowell W.|date=1970-09-01|journal=Journal of Combinatorial Theory|issue=2|doi=10.1016/S0021-9800(70)80019-9|volume=9|pages=129–135|language=en|issn=0021-9800|access-date=2020-10-23|archive-date=2020-10-30|archive-url=https://web.archive.org/web/20201030011124/https://www.sciencedirect.com/science/article/pii/S0021980070800199}}</ref>

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

== 参考文献 ==
<references />
{{图论}}
[[Category:图]]