弦圖

在圖論中，弦圖（英語：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]

參考文獻

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） （英語）.