^Rose, Donald J.; Tarjan, R. Endre; Lueker, George S. . SIAM Journal on Computing. 1976-06, 5 (2): 266–283 [2020-12-09]. ISSN 0097-5397. doi:10.1137/0205021. (原始内容存档于2022-05-31) (英语).
一月 30, 2023
弦圖, 在图论中, 弦图, 英語, chordal, graph, 是一类含有很多弦的图, 所谓, 即环中跨越非邻点的一条边, 或者说, 捷径, 可类比圆中的弦, 弦图要求图中任意一个长度不小于4的环都须含有弦, 根据该定义, 弦图中每一个大环都被弦切割成若干小三角形, 因此弦图也被称作三角化图, 黑色, 和环上的两条弦, 绿色, 弦图是完美图的一种子类, 算法可以在线性时间内判定一张图是否为弦图, 而且, 有些在一般图上困难的问题, 比如图着色问题, 在弦图上可被高效解决, 定义, 编辑设c, displayst. 在图论中 弦图 英語 Chordal graph 是一类含有很多弦的图 所谓 弦 即环中跨越非邻点的一条边 或者说 捷径 可类比圆中的弦 弦图要求图中任意一个长度不小于4的环都须含有弦 根据该定义 弦图中每一个大环都被弦切割成若干小三角形 因此弦图也被称作三角化图 1 2 环 黑色 和环上的两条弦 绿色 弦图是完美图的一种子类 算法可以在线性时间内判定一张图是否为弦图 而且 有些在一般图上困难的问题 比如图着色问题 在弦图上可被高效解决 定义 编辑设C k v 1 v 2 v k v 1 displaystyle C k v 1 v 2 dots v k v 1 是一个环 其中k 4 displaystyle k geq 4 只要i j 0 1 k 1 mod k displaystyle i j not equiv 0 1 k 1 pmod k 我们就称边e v i v j displaystyle e v i v j 为环C k displaystyle C k 的一条弦 设G V E displaystyle G V E 是一张图 若对于图中任意环C k G k 4 displaystyle C k subseteq G k geq 4 边集E displaystyle E 都含有C k displaystyle C k 的某条 某些弦 则称G displaystyle G 是一张弦图 等价刻画 编辑弦图可以被完美消去序 perfect elimination ordering 以下简称完美序 的概念所刻画 记G H v u u v u v E H displaystyle Gamma H v u mid u v lor u v in E H 为顶点v displaystyle v 在图H displaystyle H 的含心邻域 现给定图G displaystyle G 的一个顶点排序p v 1 v 2 v n displaystyle pi v 1 v 2 dots v n 我们定义H i G j 1 i v j displaystyle H i G left cup j 1 i v j right 若对任意i displaystyle i G H i v i displaystyle Gamma H i v i 均为完全图 那么就称p displaystyle pi 是一个完美序 富爾克森和Gross 1965 证明了一张图是弦图当且仅当它拥有某种完美序 拥有完美序的图一定是完美图 因此弦图是完美图的子类 3 Rose Lueker和Tarjan 1976 构造了一种用于寻找完美序的线性算法 结合前面的等价刻画 算法可以在线性时间内断定一张图是否为弦图 4 参考文献 编辑 Padraic Bartlett Chordal Graphs PDF 原始内容 PDF 存档于2017 08 30 英语 Koller Daphne Friedman Nir 概率图模型 原理与技术 北京 清华大学出版社 2015 ISBN 978 7 302 37134 2 OCLC 928973258 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 英语 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 英语 取自 https zh wikipedia org w index php title 弦圖 amp oldid 72356246, 维基百科,wiki,书籍,书籍,图书馆,