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

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

正式定義

編輯

 線圖 定義如下:

  •  的一個頂點對應 的一邊
  •  的頂點相鄰若且唯若它們在 對應的邊相鄰(有公共頂點)。

該定義也可以用圖論的語言表述如下:設 ,那麼 ,且 

例子

編輯

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

性質

編輯
 
有些圖總不是線圖

由原圖轉移過來的性質

編輯

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

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

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

惠特尼同構定理

編輯

惠特尼同構定理[1]闡述了以下事實:設有連通圖  且它們均不是三角形 或爪形 。如果 ,那麼 。也就是說,除了極特殊的情形,圖 的結構可以由線圖 的結構中唯一地恢復出來。

其它性質

編輯

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

線圖 鄰接矩陣 的全部特徵值都不小於-2。這是因為 ,其中 是原圖 關聯矩陣(incidence matrix)。又由於矩陣 是半正定的,所以 的任何特徵值 均滿足 

等價刻畫

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

Beineke給出了線圖的一種等價刻畫: 是某圖的線圖若且唯若 不包含九種類型的導出子圖(見右圖)。[2]

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

參考文獻

編輯
  1. ^ 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). 
  2. ^ 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) (英語).