主题
Search

树状度

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

给定一个图 G，树状度 Upsilon(G) 是边不相交的无环子图（即，生成森林）的最小数量，它们的并集是 G。

因此，无环图的树状度为 Upsilon(G)=1=1。

看起来，正则图 G 的顶点度 d 的树状度为

Upsilon(G)=|_n/2_|+1.
(1)

设 G 是一个具有 n 个顶点和 m 条边的非空图，令 m_p 是 G 的任何具有 p 个顶点的子图中边的最大数量。那么

Upsilon(G)=max_(p>1)[(m_p)/(p-1)]
(2)

（Nash-Williams 1961；Harary 1994，第 90 页）。

平面图的树状度最多为 3（Harary 1994，第 124 页，问题 11.22）。

完全图 K_n 的树状度由下式给出

Upsilon(K_n)=[n/2]
(3)

以及完全二分图 K_(m,n) 的树状度由下式给出

Upsilon(K_(m,n))=[(mn)/(m+n-1)]
(4)

（Harary 1994，第 91 页），其中 [x] 是向上取整函数。

另请参阅

无圈染色数，生成树

使用 探索

参考文献

Harary, F. "Covering and Packing in Graphs, I." Ann. New York Acad. Sci. 175, 198-205, 1970.Harary, F. "Arboricity." In Graph Theory. Reading, MA: Addison-Wesley, pp. 90-92, 1994.Harary, F. and Palmer, E. M. Graphical Enumeration. New York: Academic Press, p. 225, 1973.Harary, F. and Palmer, E. M. "A Survey of Graph Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam: North-Holland, pp. 259-275, 1973.Nash-Williams, C. St. J. A. "Edge-Disjoint Spanning Trees of Finite Graphs." J. London Math. Soc. 36, 455-450, 1961.

在 中被引用

树状度

引用为

Weisstein, Eric W. “树状度。” 来自 —— 资源。 https://mathworld.net.cn/Arboricity.html

主题分类