主题
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 覆盖, 开覆盖, 真覆盖, 万有覆盖, 顶点覆盖

使用 Wolfram|Alpha 探索

参考文献

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 “整数序列在线百科全书”.

在 Wolfram|Alpha 上被引用

覆盖

引用为

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

主题分类