Непересекающиеся множества - Disjoint sets

Два непересекающихся множества.

В математике два набора называются непересекающимися наборами, если у них нет общих элементов . Эквивалентно, два непересекающихся множества - это множества, пересечение которых является пустым множеством . Например, {1, 2, 3} и {4, 5, 6} являются непересекающимися множествами, в то время как {1, 2, 3} и {3, 4, 5} не пересекаются. Набор из более чем двух наборов называется непересекающимся, если любые два различных набора набора не пересекаются.

Обобщения

Непересекающийся набор множеств

Это определение непересекающихся множеств может быть продолжено до семейства множеств : семья попарно не пересекаются , или попарно не пересекаются , если всякий раз , когда . В качестве альтернативы некоторые авторы используют термин дизъюнктный для обозначения этого понятия. ${\ displaystyle (A_ {я}) _ {я \ in I}}$${\ displaystyle A_ {i} \ cap A_ {j} = \ varnothing}$${\ displaystyle i \ neq j}$

Для семейств понятие попарно непересекающихся или взаимно непересекающихся иногда определяется несколько иначе, в том смысле, что допускаются повторяющиеся идентичные члены: семейство попарно не пересекается, если когда-либо (каждые два различных набора в семействе не пересекаются). Например, набор наборов {{0,1,2}, {3,4,5}, {6,7,8}, ...} не пересекается, как и набор {{...− 2 , 0,2,4, ...}, {...− 3, −1,1,3,5 }} двух классов четности целых чисел; семейство из 10 членов не является непересекающимся (потому что классы четных и нечетных чисел присутствуют пять раз каждый), но попарно не пересекается в соответствии с этим определением (так как один получает непустое пересечение двух членов, когда они того же класса). ${\ displaystyle A_ {i} \ cap A_ {j} = \ varnothing}$${\ displaystyle A_ {i} \ neq A_ {j}}$${\ Displaystyle (\ {п + 2к \ середина к \ в \ mathbb {Z} \}) _ {п \ в \ {0,1, \ ldots, 9 \}}}$

Два множества называются почти непересекающимися множествами, если их пересечение в некотором смысле мало. Например, два бесконечных множества , пересечение которых является конечным множеством, можно назвать почти не пересекающимися.

В топологии существуют различные понятия разделенных множеств с более строгими условиями, чем дизъюнктность. Например, два набора могут считаться разделенными, если они имеют непересекающиеся замыкания или непересекающиеся окрестности . Аналогичным образом , в метрическом пространстве , положительно отделенные множества являются множества разделены ненулевым расстоянием .

Перекрестки

Непересекаемость двух множеств или семейства множеств может быть выражена в терминах пересечения их пар.

Два множества A и B не пересекаются тогда и только тогда, когда их пересечение является пустым множеством . Из этого определения следует, что каждое множество не пересекается с пустым множеством, и что пустое множество является единственным множеством, которое не пересекается с самим собой. ${\ displaystyle A \ cap B}$

Если коллекция содержит по крайней мере два набора, условие, что коллекция не пересекается, означает, что пересечение всей коллекции пусто. Однако набор множеств может иметь пустое пересечение, не будучи непересекающимся. Кроме того, хотя набор из менее чем двух наборов тривиально не пересекается, поскольку нет пар для сравнения, пересечение набора из одного набора равно этому набору, который может быть непустым. Например, три набора {{1, 2}, {2, 3}, {1, 3}} имеют пустое пересечение, но не являются непересекающимися. На самом деле в этом наборе нет двух непересекающихся множеств. Также пустое семейство множеств попарно не пересекается.

Семьи Хелли является система множеств , в течение которого только подсемейства с пустыми пересечениями являются те, которые попарно не пересекаются. Так , например, замкнутые интервалы этих действительных чисел образуют семейство Хелли: если семейство замкнутых интервалов имеет пустое пересечение и минимальна (т.е. не подсемейство семейства не имеет пустое пересечение), то должны быть попарно не пересекаются.

Непересекающиеся союзы и разделы

Разбиение множества X является любой совокупностью непересекающихся непустых множеств, объединение является X . Каждый раздел может быть эквивалентно описан отношением эквивалентности , бинарным отношением, которое описывает, принадлежат ли два элемента к одному и тому же набору в разделе. Структуры данных с непересекающимися наборами и уточнение разделов - это два метода в компьютерной науке для эффективного обслуживания разделов набора, подвергающихся соответственно операциям объединения, которые объединяют два набора, или операциям уточнения, которые разбивают один набор на два.

Несвязное объединение может означать одно из двух. Проще говоря, это может означать объединение непересекающихся множеств. Но если два или более набора еще не являются непересекающимися, их непересекающееся объединение может быть сформировано путем модификации наборов, чтобы сделать их не пересекающимися, прежде чем формировать объединение модифицированных наборов. Например, два набора могут быть разделены путем замены каждого элемента упорядоченной парой элемента и двоичного значения, указывающего, принадлежит ли он первому или второму набору. Для семейств, состоящих из более чем двух наборов, можно аналогичным образом заменить каждый элемент упорядоченной парой элемента и индекса набора, который его содержит.

Смотрите также

• Теорема об отделении гиперплоскостей для непересекающихся выпуклых множеств
• Взаимоисключающие события
• Относительно простые числа с непересекающимися наборами простых делителей
• Сепароид
• Упаковка множеств , проблема поиска наибольшего непересекающегося подсемейства семейства множеств.

Рекомендации

Внешние ссылки

• Вайсштейн, Эрик В. «Непересекающиеся множества» . MathWorld .