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

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

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

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

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

Пример

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

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

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

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