主题
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, 极小边覆盖, 极小顶点覆盖, 分裂图, 第二类斯特林数

使用 Wolfram|Alpha 探索

参考文献

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."

在 Wolfram|Alpha 中被引用

极小覆盖

请按如下方式引用

Weisstein, Eric W. "极小覆盖。" 来自 MathWorld--Wolfram 网络资源。 https://mathworld.net.cn/MinimalCover.html

学科分类