跳转到内容

弦图

维基百科,自由的百科全书
环(黑色)和环上的两条弦(绿色)

图论中,弦图(英语:Chordal graph)是一类含有很多的图。所谓“弦”,即中跨越非邻点的一条边,或者说“捷径”(可类比中的弦)。弦图要求图中任意一个长度不小于4的环都须含有弦。根据该定义,弦图中每一个大环都被弦切割成若干小三角形,因此弦图也被称作三角化图[1][2]

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

定义

是一个环,其中。只要,我们就称边为环的一条弦。

是一张图。若对于图中任意环,边集都含有的某条/某些弦,则称是一张弦图。

等价刻画

弦图可以被完美消去序(perfect elimination ordering,以下简称完美序)的概念所刻画。记为顶点在图的含心邻域。现给定图的一个顶点排序,我们定义。若对任意均为完全图,那么就称是一个完美序。

富尔克森和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) (英语).