弦圖（chordal graph）是圖論中滿足特定環結構條件的無向圖，其定義為：每個長度大於3的環都至少包含一條連線環中非相鄰頂點的邊（稱為弦）。該圖類具有完美消除序列特性，可通過最大勢算法構造頂點序列，使得每個頂點與其後續鄰接點構成完全子圖。弦圖的導出子圖仍保持弦圖性質，且色數等於最大團大小。在算法套用中，弦圖理論廣泛適用於圖染色、組合最佳化等問題求解。
基本介紹
- 別名：chordal graph
- 學科：圖論
- 特性：導出子圖仍為弦圖
- 判定定理：存在完美消除序列
- 算法：最大勢算法(MCS)
- 套用：圖染色、組合最佳化
定義與結構,基本性質,判定與算法,套用場景,
定義與結構
弦圖的本質特徵表現為環結構約束：若圖G=(V,E)中每個長度≥4的環都至少存在一條弦（連線環上兩個非連續頂點的邊），則該圖稱為弦圖。等價定義包括：
- 不存在長度≥4的無弦導出環（孔）
- 所有極小點割集的導出子圖構成完全子圖（團）
核心結構概念包含：
- 團（clique）：頂點集的完全子圖，極大團無法通過添加頂點保持完全性
- 單純點（simplicial vertex）：鄰域頂點構成團的頂點，弦圖至少存在兩個非相鄰單純點
- 完美消除序列：頂點排列使得每個頂點與其後續鄰接點構成團
基本性質
弦圖具有以下關鍵數學性質：
- 任意頂點導出子圖仍為弦圖
- 色數等於最大團頂點數
- 最小團覆蓋數等於最大獨立集基數
- 屬於完美圖類，滿足強完美圖定理
結構特性證明方法包含：
- 極小點割集導出團的分解定理
- 單純點存在性引理
- 區間圖必為弦圖的包含關係
判定與算法
弦圖判定主要依據完美消除序列的存在性：
- 最大勢算法(MCS)：通過疊代選取鄰接已選頂點最多的頂點構造序列
- 序列驗證：檢查每個頂點的後續鄰接是否構成團
典型算法套用包括：
- 染色數計算：沿完美消除序列逆序進行貪心染色
- 極大團識別：通過序列中頂點的鄰域閉包檢測
- 獨立集求解：基於完美序列順序選擇非相鄰頂點
套用場景
弦圖理論在圖論與組合最佳化領域具有重要套用價值：
- 硬體設計：暫存器綁定算法利用弦圖著色最佳化資源分配
- 競賽數學：解決HNOI2008王國染色等圖論問題
- 社交網路：建模具有局部完全連線特性的網路結構
- 生物信息：分析蛋白質相互作用網路的模組化特徵
算法複雜度方面，最大勢算法可在O(m+n)時間內構造完美消除序列（m為邊數，n為頂點數），判定驗證過程時間複雜度為O(n)。該特性使弦圖成為算法競賽中高頻考點，如ZOJ1015弦圖判定問題。
