主题
Search

最大叶数

下载 Mathematica Notebook下载 Wolfram Notebook

图 G 的最大叶数 l(G) 是其任何生成树中树叶的最大数量。（相应的最小叶数称为最小叶数。）

图 G 的最大叶数和连通支配数 d(G) 通过下式连接：

d(G)+l(G)=|G|,

其中 n=|G|>2 是 G 的顶点数。

许多图族都具有简单的闭合形式，如下表所示。在表中，|_x_| 表示向下取整函数。

图族最大叶数
Andrásfai 图3n-4
反棱柱图n+1
阿波罗尼网络{3 for n=1; 6 for n=2; 1/2(3^n+5) otherwise
哑铃图2(n-1)
黑主教图 BB_(n,n){1 for n=1; 1/4[2(n-2)n-(-1)^n+9] otherwise
书图 S_(n+1) square P_22n
鸡尾酒会图 K_(n×2)2(n-1)
完全二分图 K_(m,n){2 for m=n=1; m+n-1 for min(m,n)=1; m+n-2 otherwise
完全二分图 K_(n,n)2(n-1)
完全图 K_nn-1
完全三部图 K_(k,m,n){k+m+n-1 for min(k,m,n)=1; k+m+n-2 otherwise
完全三部图 K_(n,n,n)3n-2
2n-交叉棱柱图2n
冠图 K_2 square K_n^_2(n-2)
圈图 C_n2
齿轮图|_3n/2_|
舵图n+1
梯子图 nP_2n
莫比乌斯梯子 M_nn+1
平底锅图3
路径图 P_n2
棱柱图 Y_nn
车补图 K_n square K_n^_{1 for n=1; undefined for n=2; n^2-3 otherwise
车图 K_n square K_nn(n-1)
星图 S_nn-1
太阳图1/4(6n+(-1)^n-1)
日珥图 C_n circledot K_1n
三角形图1/2(n^2-3n+4)
网图2n
轮图 W_nn-1
白主教图 WB_(n,n){2 for n=2,3; 1/4[2(n-2)n+(-1)^n+7] otherwise

另请参阅

连通支配集, 连通支配数, 最小叶数, 生成树, 树叶

使用 Wolfram|Alpha 探索

参考文献

Fellows, M.; Lokshtanov, D.; Misra, N.; Mnich, M.; Rosamond, F.; and Saurabh, S. "The Complexity Ecology of Parameters: an Illustration Using Bounded Max Leaf Number." Th. Comput. Sys. 45, 822-848, 2009.Lu, H.-I. and Ravi, R. "Approximating Maximum Leaf Spanning Trees in Almost Linear Time." J. Algorithms 29, 132-141, 1998.Solis-Oba, R. "2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves." In Proceedings of Algorithms--ESA '98. 6th Annual European Symposium Venice, Italy, August 24-26, 1998 (Ed. G. Bilardi, G. F. Italiano, A. Pietracaprina, and G. Pucci). Belin: Springer, pp. 441-452, 1998.Zhou, G.; Gen, M.; and Wu, T. "A New Approach to the Degree-Constrained Minimum Spanning Tree Problem Using Genetic Algorithm." In IEEE International Conference on Systems, Man, and Cybernetics, 1996, Vol. 4, pp. 2683-2688, 1996.

请引用为

Weisstein, Eric W. "最大叶数。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/MaximumLeafNumber.html

主题分类