弦圖

环（黑色）和环上的两条弦（绿色）

在图论中，弦图（Template:Lang-en）是一类含有很多弦的图。所谓“弦”，即环中跨越非邻点的一条边，或者说“捷径”（可类比圆中的弦）。弦图要求图中任意一个长度不小于4的环都须含有弦。根据该定义，弦图中每一个大环都被弦切割成若干小三角形，因此弦图也被称作三角化图。

弦图是完美图的一种子类。算法可以在线性时间内判定一张图是否为弦图。而且，有些在一般图上困难的问题（比如图着色问题），在弦图上可被高效解决。

定义

设$C_k:=v_1{v}_2\dots v_k{v}_1$是一个环，其中$k\ge 4$。只要$i-j\equiv ̸0,1,k-1(\mathrm{mod}k)$，我们就称边$e:=\{v_i,v_j\}$为环$C_k$的一条弦。

设$G=(V,E)$是一张图。若对于图中任意环$C_k\subseteq G(k\ge 4)$，边集$E$都含有$C_k$的某条/某些弦，则称$G$是一张弦图。

等价刻画

弦图可以被完美消去序（perfect elimination ordering，以下简称完美序）的概念所刻画。记${\mathrm{\Gamma }}_H(v):=\{u\mid u=v\vee \{u,v\}\in E(H)\}$为顶点$v$在图$H$的含心邻域。现给定图$G$的一个顶点排序$\pi :=v_1,v_2,\dots ,v_n$，我们定义$H_i:=G\left[\underset{j=1}{\overset{i}{\cup }}{v}_j\right]$。若对任意$i$，${\mathrm{\Gamma }}_{H_i}(v_i)$均为完全图，那么就称$\pi$是一个完美序。

富爾克森和Gross（1965）证明了一张图是弦图当且仅当它拥有某种完美序。拥有完美序的图一定是完美图，因此弦图是完美图的子类。

Rose，Lueker和Tarjan（1976）构造了一种用于寻找完美序的线性算法。结合前面的等价刻画，算法可以在线性时间内断定一张图是否为弦图。