logo
ЭУМКД_ДиВМ3

Разбиения и покрытия

Пусть Ě ={Ei} для i ϵ I – некоторое семейство непустых подмножеств множества M, Ei Í M. Тогда семейство Ě называется покрытием множества M, если каждый элемент множества M принадлежит хотя бы одному из Ei:

M Í  Û " x ϵ M $  i ϵ I |  x ϵ Ei.

Семейство Ě называется дизъюнктным, если элементы этого семейства попарно не пересекаются, т.е. каждый элемент множества M принадлежит не более чем одному из множеств Ei: " i,j ϵ I, i¹j Þ Ei  Ç Ej = Ø

Дизъюнктное покрытие Ě называется разбиением множества M.

Пример

Пусть имеется множество M={1,2,3}.

Тогда семейство {{1,2}, {2,3}, {3,1}} является покрытием, но не разбиением;

семейство {{1},{2},{3}} – покрытием и разбиением,

а семейство {{1},{2}} является дизъюнктным, но в то же время не является ни покрытием, ни разбиением.