在圖論中,弦圖(英語:Chordal graph)是一類含有很多弦的圖。所謂「弦」,即環中跨越非鄰點的一條邊,或者說「捷徑」(可類比圓中的弦)。弦圖要求圖中任意一個長度不小於4的環都須含有弦。根據該定義,弦圖中每一個大環都被弦切割成若干小三角形,因此弦圖也被稱作三角化圖。[1][2]
![Thumb](http://upload.wikimedia.org/wikipedia/commons/thumb/3/34/Chordal-graph.svg/197px-Chordal-graph.svg.png)
弦圖是完美圖的一種子類。算法可以在線性時間內判定一張圖是否為弦圖。而且,有些在一般圖上困難的問題(比如圖著色問題),在弦圖上可被高效解決。
定義
設是一個環,其中。只要,我們就稱邊為環的一條弦。
設是一張圖。若對於圖中任意環,邊集都含有的某條/某些弦,則稱是一張弦圖。
等價刻畫
弦圖可以被完美消去序(perfect elimination ordering,以下簡稱完美序)的概念所刻畫。記為頂點在圖的含心鄰域。現給定圖的一個頂點排序,我們定義。若對任意,均為完全圖,那麼就稱是一個完美序。
富爾克森和Gross(1965)證明了一張圖是弦圖若且唯若它擁有某種完美序。擁有完美序的圖一定是完美圖,因此弦圖是完美圖的子類。[3]
Rose,Lueker和Tarjan(1976)構造了一種用於尋找完美序的線性算法。結合前面的等價刻畫,算法可以在線性時間內斷定一張圖是否為弦圖。[4]