線圖

在圖論中，圖$G$所對應的線圖是一張能夠反映$G$中各邊鄰接性的圖，記作$L(G)$。簡單來說，$L(G)$將$G$中的每條邊各自抽象成一個頂點；如若原圖中兩條邊相鄰，那麼就給線圖中對應頂點之間連接一條邊。因為線圖將原圖的邊化作了頂點，所以也可以將其視作原圖的一種對偶。

哈斯勒·惠特尼證明了：假定圖$G$是連通的，那麼除了一種特殊情況外，我們總能根據線圖$L(G)$的結構還原出$G$的結構。以該定理為中介，可以證明線圖的許多其它性質。線圖總是無爪圖，即線圖的所有導出子圖均不是$K_{1,3}$。

正式定義

圖$G$的線圖$L(G)$定義如下：

• $L(G)$的一個頂點對應$G$的一邊

• $L(G)$的頂點相鄰若且唯若它們在$G$對應的邊相鄰（有公共頂點）。

該定義也可以用圖論的語言表述如下：設$G=(V,E)$，那麼$L(G)=(E,{\tilde {E}})$，且$(e_{1},e_{2})\in {\tilde {E}}\iff e_{1}\cap e_{2}\neq \emptyset$。

例子

下面的例子演示了由原圖生成線圖的流程。

• 
  原圖
• 
  製作線圖的過程
• 
  結果

性質

有些圖總不是線圖

由原圖轉移過來的性質

根據線圖的定義，若性質／概念P僅取決於原圖$G$中邊的鄰接性，那麼P便可以轉移（或者說對偶）到線圖$L(G)$上去變成性質／概念P'，刻畫線圖頂點的鄰接屬性。例如，圖$G$中的一個匹配指的是圖中一組不相交的邊，把這一概念平移到線圖上去，就等價於線圖的一組不相鄰的頂點——用術語來說即線圖上的一個獨立集。

下面就列舉了原圖和線圖之間的若干聯繫：

• 若原圖是連通的，線圖也是。
• 若兩個圖同構，那麼它們的線圖也同構。
• 若$G$的頂點數和邊數分別為$n$和$m$，那麼$L(G)$的頂點數和邊數分別是$m$和${\textstyle \sum _{v}{\binom {\deg(v)}{2}}}$。
• $\chi _{E}(G)=\chi _{V}(L(G))$，即原圖的邊色數等於線圖的點色數。
• $G$中的一個匹配對應了$L(G)$中的一個獨立集，且其大小相等。於是，$G$中最大匹配的大小等於$L(G)$最大獨立集的大小。藉助這一關係，可以通過求解後者來求解前者，但反之不總是可行，因為並非所有圖都能表示為某個$G$的線圖。在計算機科學中，最大匹配問題和最大獨立集問題是兩個重要的問題。前者已經被高效解決（Edmonds' Blossom Algorithm）；而後者則是NP完全問題，被普遍認為無法高效求解。
• 若$G$存在歐拉迴路，則$L(G)$存在哈密頓迴路，但反之不然。

惠特尼同構定理

惠特尼同構定理闡述了以下事實：設有連通圖$G_{1}$和$G_{2}$且它們均不是三角形$K_{3}$或爪形$K_{1,3}$。如果$L(G_{1})\cong L(G_{2})$，那麼$G_{1}\cong G_{2}$。也就是說，除了極特殊的情形，圖$G$的結構可以由線圖$L(G)$的結構中唯一地恢復出來。

其它性質

任何的線圖都是無爪的，亦即不包含$K_{1,3}$作為導出子圖。因此，任意含有偶數個頂點的連通線圖都存在完美匹配。

線圖$L(G)$的鄰接矩陣$A_{m\times m}$的全部特徵值都不小於-2。這是因為$A=J^{\operatorname {T} }J-2I$，其中$J_{n\times m}$是原圖$G$的關聯矩陣（incidence matrix）。又由於矩陣$J^{\operatorname {T} }J$是半正定的，所以$A$的任何特徵值$\lambda$均滿足$\lambda +2\geq 0$。

等價刻畫

九種排除在線圖之外的導出子圖

Beineke給出了線圖的一種等價刻畫：$H$是某圖的線圖若且唯若$H$不包含九種類型的導出子圖（見右圖）。

如果$H$的最小度至少為5，那麼只有左邊一列和右邊一列是必要的。換言之，此時，$H$是某圖的線圖若且唯若$H$不包含六種類型的導出子圖（見右圖的左邊一列和右邊一列）。