查看“︁弦圖”︁的源代码

[[File:Chordal-graph.svg|缩略图|197x197像素|环（黑色）和环上的两条弦（绿色）]]
在[[图论]]中，'''弦图'''（{{lang-en|Chordal graph}}）是一类含有很多[[弦]]的图。所谓“弦”，即[[環 (圖論)|环]]中跨越非邻点的一条边，或者说“捷径”（可类比[[圆]]中的弦）。弦图要求图中任意一个长度不小于4的环都须含有弦。根据该定义，弦图中每一个大环都被弦切割成若干小三角形，因此弦图也被称作'''三角化图'''。<ref>{{Cite web|title=Chordal Graphs|url=http://web.math.ucsb.edu/~padraic/mathcamp_2011/perfectgraphs/MC2011_perfectgraphs_wk1_day3.pdf|accessdate=|author=Padraic Bartlett|date=|format=|publisher=|language=英语|archive-date=2017-08-30|archive-url=https://web.archive.org/web/20170830033345/http://web.math.ucsb.edu/~padraic/mathcamp_2011/perfectgraphs/MC2011_perfectgraphs_wk1_day3.pdf}}</ref><ref>{{Cite book|url=https://www.worldcat.org/oclc/928973258|publisher=清华大学出版社|location=北京|isbn=978-7-302-37134-2|oclc=928973258|last=Koller, Daphne.|last2=Friedman, Nir|title=概率图模型：原理与技术|first=|year=2015|pages=}}</ref>

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

== 定义 ==
设<math>C_k := v_1 v_2 \dots v_k v_1</math>是一个环，其中<math>k \geq 4</math>。只要<math>i - j \not\equiv 0, 1, k-1 \pmod{k}</math>，我们就称边<math> e := \{v_i, v_j\}</math>为环<math>C_k</math>的一条弦。

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

== 等价刻画 ==
弦图可以被''完美消去序（perfect elimination ordering，以下简称完美序）''的概念所刻画。记<math>\Gamma_H(v) := \{ u \mid u = v \lor \{u,v\} \in E(H) \}</math>为顶点<math>v</math>在图<math>H</math>的含心邻域。现给定图<math>G</math>的一个顶点排序<math>\pi := v_1, v_2, \dots, v_n</math>，我们定义<math>H_i := G \left[\cup_{j=1}^i v_j\right]</math>。若对任意<math>i</math>，<math>\Gamma_{H_i}(v_i)</math>均为[[完全图]]，那么就称<math>\pi</math>是一个完美序。

富爾克森和Gross（1965）证明了一张图是弦图当且仅当它拥有某种完美序。拥有完美序的图一定是完美图，因此弦图是完美图的子类。<ref>{{Cite journal|title=Incidence matrices and interval graphs|url=http://msp.org/pjm/1965/15-3/p11.xhtml|last=Fulkerson|first=Delbert|last2=Gross|first2=Oliver|date=1965-09-01|journal=Pacific Journal of Mathematics|issue=3|doi=10.2140/pjm.1965.15.835|volume=15|pages=835–855|language=en|issn=0030-8730|access-date=2020-12-09|archive-date=2022-01-19|archive-url=https://web.archive.org/web/20220119180633/http://msp.org/pjm/1965/15-3/p11.xhtml}}</ref>

Rose，Lueker和Tarjan（1976）构造了一种用于寻找完美序的线性算法。结合前面的等价刻画，算法可以在线性时间内断定一张图是否为弦图。<ref>{{Cite journal|title=Algorithmic Aspects of Vertex Elimination on Graphs|url=http://epubs.siam.org/doi/10.1137/0205021|last=Rose|first=Donald J.|last2=Tarjan|first2=R. Endre|date=1976-06|journal=SIAM Journal on Computing|issue=2|doi=10.1137/0205021|volume=5|pages=266–283|language=en|issn=0097-5397|last3=Lueker|first3=George S.|access-date=2020-12-09|archive-date=2022-05-31|archive-url=https://web.archive.org/web/20220531180651/https://epubs.siam.org/doi/10.1137/0205021}}</ref>

== 参考文献 ==
<references />
[[Category:图论]]