主题
Search

覆盖


集合 X 的非空 子集 的族 gamma,其 并集 包含给定的集合 X(且不包含重复的子集),称为 X 的一个覆盖(或覆盖族)。例如,{1} 只有一个覆盖,即 {{1}}。然而,{1,2} 有五个覆盖,即 {{1},{2}}{{1,2}}{{1},{1,2}}{{2},{1,2}}{{1},{2},{1,2}}

极小覆盖 是指移除任何一个成员都会破坏覆盖性质的覆盖。例如,在 {1,2} 的五个覆盖中,只有 {{1},{2}}{{1,2}} 是极小覆盖。还有各种其他类型的专门覆盖,包括 真覆盖、反链覆盖、k-覆盖 和 k^*-覆盖 (Macula 1994)。

具有 N 个元素的集合的可能覆盖的数量是

 |C(N)|=1/2sum_(k=0)^N(-1)^k(N; k)2^(2^(N-k)),

其中前几个是 1, 5, 109, 32297, 2147321017, 9223372023970362989, ... (OEIS A003465)。


另请参阅

棒球覆盖, 覆盖映射, 边覆盖, Lebesgue 覆盖维数, 极小覆盖, Minkowski 覆盖, 开覆盖, 真覆盖, 万有覆盖, 顶点覆盖

使用 探索

参考文献

Eppstein, D. "Covering and Packing." http://www.ics.uci.edu/~eppstein/junkyard/cover.html.Macula, A. J. "Covers of a Finite Set." Math. Mag. 67, 141-144, 1994.Sloane, N. J. A. Sequences A003465/M4024 和 A055621 in “整数序列在线百科全书”.

在 上被引用

覆盖

引用为

Weisstein, Eric W. “覆盖。”来自 —— 资源。 https://mathworld.net.cn/Cover.html

主题分类