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

Эта статья о математической концепции. Информацию о структуре данных см. в разделе Структура данных Disjoint-set .

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

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

Обобщения

Непересекающаяся коллекция наборов

Это определение непересекающихся множеств можно распространить на семейства множеств и на индексированные семейства множеств. По определению, совокупность множеств называется семейством множеств (например , набором степеней ). В некоторых источниках это набор наборов, в то время как в других источниках допускается, что это мультимножество наборов, причем некоторые наборы повторяются. семейство Индексированное множеств $\left(A_{i}\right)_{i\in I},$ с множеством значений по определению является функцией (то есть это функция, которая присваивает множество $A_{i}$ каждому элементу $i\in I$ в своем домене), чей домен $I$ называется его набором индексов (а элементы его домена называются индексами ).

Есть два слегка различающихся определения того, когда семейство множеств ${\mathcal {F}}$ называется попарно непересекающимся . Согласно одному из таких определений, семейство является непересекающимся, если каждые два множества в нем либо идентичны, либо не пересекаются. Это определение позволит попарно непересекающимся семействам множеств иметь повторяющиеся копии одного и того же набора. Согласно альтернативному определению, каждые два множества в семействе должны быть непересекающимися; повторные копии не допускаются. Те же два определения могут быть применены к индексированному семейству множеств: согласно первому определению, каждые два различных индекса в семействе должны называть множества, которые не пересекаются или идентичны, а согласно второму, каждые два различных индекса должны называть непересекающиеся множества. . Например, семейство множеств { {0, 1, 2}, {3, 4, 5}, {6, 7, 8}, ... } непересекающееся согласно обоим определениям, как и семейство { {. .., −2, 0, 2, 4, ...}, {..., −3, −1, 1, 3, 5} } двух классов четности целых чисел. Однако семья $(\{n+2k\mid k\in \mathbb {Z} \})_{n\in \{0,1,\ldots ,9\}}$ с 10 членами имеет по пять повторений каждый из двух непересекающихся наборов, поэтому он попарно непересекающийся согласно первому определению, но не по второму.

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

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

Перекрестки

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

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

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

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

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

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

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

См. также

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

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

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