弦圖

在图论中，弦图（英語：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） （英语）.