弦圖

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

环(黑色)和环上的两条弦(绿色)

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

定义

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

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

等价刻画

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

Fulkerson和Gross(1965)证明了一张图是弦图当且仅当它拥有某种完美序。拥有完美序的图一定是完美图,因此弦图是完美图的子类。[3]

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

参考文献

  1. Padraic Bartlett. (PDF) (英语).
  2. Koller, Daphne.; Friedman, Nir. . 北京: 清华大学出版社. 2015. ISBN 978-7-302-37134-2. OCLC 928973258.
  3. Fulkerson, Delbert; Gross, Oliver. . Pacific Journal of Mathematics. 1965-09-01, 15 (3): 835–855. ISSN 0030-8730. doi:10.2140/pjm.1965.15.835 (英语).
  4. Rose, Donald J.; Tarjan, R. Endre; Lueker, George S. . SIAM Journal on Computing. 1976-06, 5 (2): 266–283. ISSN 0097-5397. doi:10.1137/0205021 (英语).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.