在圖論中,圖所對應的線圖是一張能夠反映中各邊鄰接性的圖,記作。簡單來說,將中的每條邊各自抽象成一個頂點;如若原圖中兩條邊相鄰,那麼就給線圖中對應頂點之間連接一條邊。因為線圖將原圖的邊化作了頂點,所以也可以將其視作原圖的一種對偶。
哈斯勒·惠特尼證明了:假定圖是連通的,那麼除了一種特殊情況外,我們總能根據線圖的結構還原出的結構[1]。以該定理為中介,可以證明線圖的許多其它性質。線圖總是無爪圖,即線圖的所有導出子圖均不是。
圖的線圖定義如下:
- 的一個頂點對應的一邊
- 的頂點相鄰若且唯若它們在對應的邊相鄰(有公共頂點)。
該定義也可以用圖論的語言表述如下:設,那麼,且。
下面的例子演示了由原圖生成線圖的流程。
根據線圖的定義,若性質/概念P僅取決於原圖中邊的鄰接性,那麼P便可以轉移(或者說對偶)到線圖上去變成性質/概念P',刻畫線圖頂點的鄰接屬性。例如,圖中的一個匹配指的是圖中一組不相交的邊,把這一概念平移到線圖上去,就等價於線圖的一組不相鄰的頂點——用術語來說即線圖上的一個獨立集。
下面就列舉了原圖和線圖之間的若干聯繫:
- 若原圖是連通的,線圖也是。
- 若兩個圖同構,那麼它們的線圖也同構。
- 若的頂點數和邊數分別為和,那麼的頂點數和邊數分別是和。
- ,即原圖的邊色數等於線圖的點色數。
- 中的一個匹配對應了中的一個獨立集,且其大小相等。於是,中最大匹配的大小等於最大獨立集的大小。藉助這一關係,可以通過求解後者來求解前者,但反之不總是可行,因為並非所有圖都能表示為某個的線圖。在計算機科學中,最大匹配問題和最大獨立集問題是兩個重要的問題。前者已經被高效解決(Edmonds' Blossom Algorithm);而後者則是NP完全問題,被普遍認為無法高效求解。
- 若存在歐拉迴路,則存在哈密頓迴路,但反之不然。
惠特尼同構定理[1]闡述了以下事實:設有連通圖和且它們均不是三角形或爪形。如果,那麼。也就是說,除了極特殊的情形,圖的結構可以由線圖的結構中唯一地恢復出來。
任何的線圖都是無爪的,亦即不包含作為導出子圖。因此,任意含有偶數個頂點的連通線圖都存在完美匹配。
線圖的鄰接矩陣的全部特徵值都不小於-2。這是因為,其中是原圖的關聯矩陣(incidence matrix)。又由於矩陣是半正定的,所以的任何特徵值均滿足。
Beineke給出了線圖的一種等價刻畫:是某圖的線圖若且唯若不包含九種類型的導出子圖(見右圖)。[2]
如果的最小度至少為5,那麼只有左邊一列和右邊一列是必要的。換言之,此時,是某圖的線圖若且唯若不包含六種類型的導出子圖(見右圖的左邊一列和右邊一列)。
- ^ 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) (英語).