弦圖

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

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

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

定義

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

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

等價刻畫

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

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

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