跳至內容

弦圖

維基百科,自由的百科全書
環(黑色)和環上的兩條弦(綠色)

圖論中,弦圖(英語:Chordal graph)是一類含有很多的圖。所謂「弦」,即中跨越非鄰點的一條邊,或者說「捷徑」(可類比中的弦)。弦圖要求圖中任意一個長度不小於4的環都須含有弦。根據該定義,弦圖中每一個大環都被弦切割成若干小三角形,因此弦圖也被稱作三角化圖[1][2]

弦圖是完美圖的一種子類。算法可以在線性時間內判定一張圖是否為弦圖。而且,有些在一般圖上困難的問題(比如圖着色問題),在弦圖上可被高效解決。

定義

[編輯]

是一個環,其中。只要,我們就稱邊為環的一條弦。

是一張圖。若對於圖中任意環,邊集都含有的某條/某些弦,則稱是一張弦圖。

等價刻畫

[編輯]

弦圖可以被完美消去序(perfect elimination ordering,以下簡稱完美序)的概念所刻畫。記為頂點在圖的含心鄰域。現給定圖的一個頂點排序,我們定義。若對任意均為完全圖,那麼就稱是一個完美序。

富爾克森和Gross(1965)證明了一張圖是弦圖當且僅當它擁有某種完美序。擁有完美序的圖一定是完美圖,因此弦圖是完美圖的子類。[3]

Rose,Lueker和Tarjan(1976)構造了一種用於尋找完美序的線性算法。結合前面的等價刻畫,算法可以在線性時間內斷定一張圖是否為弦圖。[4]

參考文獻

[編輯]
  1. ^ Padraic Bartlett. Chordal Graphs (PDF). (原始內容 (PDF)存檔於2017-08-30) (英語). 
  2. ^ Koller, Daphne.; Friedman, Nir. 概率图模型:原理与技术. 北京: 清華大學出版社. 2015. ISBN 978-7-302-37134-2. OCLC 928973258. 
  3. ^ Fulkerson, Delbert; Gross, Oliver. Incidence matrices and interval graphs. Pacific Journal of Mathematics. 1965-09-01, 15 (3): 835–855 [2020-12-09]. ISSN 0030-8730. doi:10.2140/pjm.1965.15.835. (原始內容存檔於2022-01-19) (英語). 
  4. ^ Rose, Donald J.; Tarjan, R. Endre; Lueker, George S. Algorithmic Aspects of Vertex Elimination on Graphs. SIAM Journal on Computing. 1976-06, 5 (2): 266–283 [2020-12-09]. ISSN 0097-5397. doi:10.1137/0205021. (原始內容存檔於2022-05-31) (英語).