主題
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

另請參閱

連通支配集, 連通支配數, 最小葉數, 生成樹, 樹葉

使用 探索

參考文獻

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. "最大葉數。" 來自 Web 資源。 https://mathworld.tw/MaximumLeafNumber.html

主題分類