弦圖
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/3/34/Chordal-graph.svg/197px-Chordal-graph.svg.png)
在圖論中,弦圖(英語:Chordal graph)是一類含有很多弦的圖。所謂「弦」,即環中跨越非鄰點的一條邊,或者說「捷徑」(可類比圓中的弦)。弦圖要求圖中任意一個長度不小於4的環都須含有弦。根據該定義,弦圖中每一個大環都被弦切割成若干小三角形,因此弦圖也被稱作三角化圖。[1][2]
弦圖是完美圖的一種子類。算法可以在線性時間內判定一張圖是否為弦圖。而且,有些在一般圖上困難的問題(比如圖着色問題),在弦圖上可被高效解決。
定義
設是一個環,其中。只要,我們就稱邊為環的一條弦。
設是一張圖。若對於圖中任意環,邊集都含有的某條/某些弦,則稱是一張弦圖。
等價刻畫
弦圖可以被完美消去序(perfect elimination ordering,以下簡稱完美序)的概念所刻畫。記為頂點在圖的含心鄰域。現給定圖的一個頂點排序,我們定義。若對任意,均為完全圖,那麼就稱是一個完美序。
富爾克森和Gross(1965)證明了一張圖是弦圖當且僅當它擁有某種完美序。擁有完美序的圖一定是完美圖,因此弦圖是完美圖的子類。[3]
Rose,Lueker和Tarjan(1976)構造了一種用於尋找完美序的線性算法。結合前面的等價刻畫,算法可以在線性時間內斷定一張圖是否為弦圖。[4]
參考文獻
- ^ Padraic Bartlett. Chordal Graphs (PDF). (原始內容 (PDF)存檔於2017-08-30) (英語).
- ^ Koller, Daphne.; Friedman, Nir. 概率图模型:原理与技术. 北京: 清華大學出版社. 2015. ISBN 978-7-302-37134-2. OCLC 928973258.
- ^ 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) (英語).
- ^ 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) (英語).