弦圖

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

環（黑色）和環上的兩條弦（綠色）

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

定義

設${\displaystyle C_{k}:=v_{1}v_{2}\dots v_{k}v_{1}}$是一個環，其中${\displaystyle k\geq 4}$。只要${\displaystyle i-j\not \equiv 0,1,k-1{\pmod {k}}}$，我們就稱邊${\displaystyle e:=\{v_{i},v_{j}\}}$為環${\displaystyle C_{k}}$的一條弦。

設${\displaystyle G=(V,E)}$是一張圖。若對於圖中任意環${\displaystyle C_{k}\subseteq G~(k\geq 4)}$，邊集${\displaystyle E}$都含有${\displaystyle C_{k}}$的某條/某些弦，則稱${\displaystyle G}$是一張弦圖。

等價刻畫

弦圖可以被完美消去序（perfect elimination ordering，以下簡稱完美序）的概念所刻畫。記${\displaystyle \Gamma _{H}(v):=\{u\mid u=v\lor \{u,v\}\in E(H)\}}$為頂點${\displaystyle v}$在圖${\displaystyle H}$的含心鄰域。現給定圖${\displaystyle G}$的一個頂點排序${\displaystyle \pi :=v_{1},v_{2},\dots ,v_{n}}$，我們定義${\displaystyle H_{i}:=G\left[\cup _{j=1}^{i}v_{j}\right]}$。若對任意${\displaystyle i}$，${\displaystyle \Gamma _{H_{i}}(v_{i})}$均為完全圖，那麼就稱${\displaystyle \pi }$是一個完美序。

富爾克森和Gross（1965）證明了一張圖是弦圖若且唯若它擁有某種完美序。擁有完美序的圖一定是完美圖，因此弦圖是完美圖的子類。^[3]

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