跳至內容

線圖

維基百科,自由的百科全書

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

哈斯勒·惠特尼證明了:假定圖連通的,那麼除了一種特殊情況外,我們總能根據線圖的結構還原出的結構[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) (英語).