主题
Search

弦图


弦图是一个 简单图,其中每个长度为四或更大的 图的环 都有一个 环的弦。换句话说,弦图是一个没有长度为四或更大的 无弦环 的图(参见 West 2000, p. 225; Gross and Yellen 2006, p. 437)。

ChordalGraphs

节点数为 n=1, 2, ... 的简单弦图的数量分别为 1, 2, 4, 10, 27, 94, 393, ... (OEIS A048193)。上面展示了前几个,尽管许多都是平凡的弦图,因为它们没有长度 >=4 的环。

ChordalGraphsConnected

相应的简单连通弦图的数量分别为 1, 1, 2, 5, 15, 58, 272, ... (OEIS A048192)。上面展示了前几个,尽管许多再次只是平凡的弦图。

分裂图 是一个弦图,其 图的补图 也是弦图 (Royle 2000)。

每个弦图都是 完美图

在线性时间内识别弦图是可能的。此外,可以在 多项式时间 内找到弦图的最大团,尽管对于一般图,这个问题是 NP-完全 的。

弦图(没有无弦环)与 无弦图(没有 )不是相同的(或相反的)。例如,方形图 C_4无弦图 但不是弦图,钻石图四面体图 K_4 是弦图但不是 无弦图,并且 空图 K^__n, 路径图 P_n, 和 三角形图 C_3 既是弦图又是 无弦图

弦图的图类包括 块图


另请参阅

仙人掌图, 无弦环, 无弦图, 环的弦, 图的环, 完美图, 托勒密图, 分裂图

使用 探索

参考文献

Blair, J. R. S. 和 Peyton, B. W. "弦图和团树导论。" 在 图论与稀疏矩阵计算 (Ed. A. George, J. R. Gilbert, 和 J. W. H. Liu)。纽约: Springer-Verlag, pp.1-29, 1993.Brandstadt, A.; Le, V. B.; 和 Spinrad, J. P. 图类:综述。 费城,宾夕法尼亚州: SIAM, 1999. Bulatov, Y. "Mathematica Bits: 弦图包更新。" http://mathematica-bits.blogspot.com/2011/02/chordal-graph-usage.html.Gross, J. T. 和 Yellen, J. 图论及其应用,第二版。 博卡拉顿,佛罗里达州: CRC Press, 2006.Habib, M.; McConnell, R.; Paul, C.; 和 Viennot, L. "Lex-BFS 和分区细化,及其在传递定向、区间图识别和连续 1 测试中的应用。" Theoret. Comput. Sci. 234, 59-84, 2000.Rose, D.; Lueker, G.; 和 Tarjan, R. E. "图上顶点消除的算法方面。" SIAM J. Comput. 5, 266-283, 1976.Royle, G. F. "计数集合覆盖和分裂图。" J. Integer Seq. 3, Article 00.2.6, 2000. https://cs.uwaterloo.ca/journals/JIS/VOL3/ROYLE/royle.html.Sloane, N. J. A. 序列 A048192A048193 在 "整数序列在线百科全书" 中。West, D. B. "弦图" 和 "弦图再探"。 图论导论,第二版。 恩格尔伍德悬崖,新泽西州: Prentice-Hall, pp. 224-226 和 323-328, 2000.

在 中被引用

弦图

引用为

Weisstein, Eric W. "弦图。" 来自 MathWorld-- 资源。 https://mathworld.net.cn/ChordalGraph.html

主题分类