主題
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.tw/Cover.html

主題分類