線圖

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

哈斯勒·惠特尼證明了：假定圖 $G$ 是連通的，那麼除了一種特殊情況外，我們總能根據線圖 $L(G)$ 的結構還原出 $G$ 的結構^[1]。以該定理為中介，可以證明線圖的許多其它性質。線圖總是無爪圖，即線圖的所有導出子圖均不是 $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)$ 存在哈密頓迴路，但反之不然。

惠特尼同構定理[編輯]

惠特尼同構定理^[1]闡述了以下事實：設有連通圖 $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$ 。