主題
Search

極小覆蓋

下載 Mathematica 筆記本下載 Wolfram 筆記本

極小覆蓋是一種覆蓋，移除其中任何單個成員都會破壞其覆蓋性質。例如，對於 {1,2} 的五個覆蓋，即 {{1},{2}}、{{1,2}}、{{1},{1,2}}、{{2},{1,2}} 和 {{1},{2},{1,2}}，只有 {{1},{2}} 和 {{1,2}} 是極小覆蓋。

類似地，{1,2,3} 的極小覆蓋由 {{1,2,3}}、{{1,2},{1,3}}、{{2},{1,3}}、{{2,3},{1,2}}、{{2,3},{1,3}}、{{2,3},{1}}、{{3},{2},{1}} 和 {{3},{1,2}} 給出。 n 個成員的極小覆蓋的數量，對於 n=1, 2, ..., 分別為 1, 2, 8, 49, 462, 6424, 129425, ... (OEIS A046165)。

Royle (2000) 證明了在 n 個頂點的分裂圖與大小為 n 的集合的極小覆蓋之間存在一一對應關係。

設 mu(n,k) 為 {1,...,n} 且具有 k 個成員的極小覆蓋的數量。則

mu(n,k)=1/(k!)sum_(m=k)^(alpha_k)(2^k-k-1; m-k)m!s(n,m),

其中 (n; k) 是一個二項式係數，s(n,m) 是第二類斯特林數，並且

alpha_k=min(n,2^k-1).

特殊情況包括 mu(n,1)=1 和 mu(n,2)=s(n+1,3)。下表給出了 mu(n,k) 的三角形 (OEIS A035348)。

nk=1k=2k=3k=4k=5k=6k=7
OEISA000392A003468A016111A046166A046167A057668
11
211
3161
4125221
5190305651
61301341025401711
719663362177350170664201
81302530538220229511298346100814988

另請參閱

覆蓋, Lew k-gram, 極小邊覆蓋, 極小頂點覆蓋, 分裂圖, 第二類斯特林數

使用 探索

參考文獻

Hearne, T. and Wagner, C. "Minimal Covers of Finite Sets." Disc. Math. 5, 247-251, 1973.Macula, A. J. "Covers of a Finite Set." Math. Mag. 67, 141-144, 1994.Macula, A. J. "Lewis Carroll and the Enumeration of Minimal Covers." Math. Mag. 68, 269-274, 1995.Royle, G. F. "Counting Set Covers and Split Graphs." J. Integer Seq. 3, Article 00.2.6, 2000. https://cs.uwaterloo.ca/journals/JIS/VOL3/ROYLE/royle.html.Sloane, N. J. A. Sequences A000392, A003468, A016111, A035348, A046165, A046166, A046167, A046168, and A057668 in "The On-Line Encyclopedia of Integer Sequences."

在 中被引用

極小覆蓋

請按如下方式引用

Weisstein, Eric W. "極小覆蓋。" 來自 網路資源。 https://mathworld.tw/MinimalCover.html

學科分類