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

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

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

Обобщения

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

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

Для семейств понятие попарно непересекающихся или взаимно непересекающихся иногда определяется несколько иначе, в том смысле, что допускаются повторяющиеся идентичные члены: семейство попарно не пересекается, если в любое время (каждые два отчетливый множества в семействе не пересекаются).[2] Например, коллекция наборов { {0,1,2}, {3,4,5}, {6,7,8}, ... } не пересекается, как и множество { {...,-2,0,2,4,...}, {...,-3,-1,1,3,5 }} двух классов четности целых чисел; семья с 10 членами не является непересекающимся (потому что классы четных и нечетных чисел каждый присутствует по пять раз), но попарно не пересекается в соответствии с этим определением (поскольку один получает только непустое пересечение двух членов, когда два одинаковые учебный класс).

Говорят, что два набора почти непересекающиеся множества если их пересечение в каком-то смысле невелико. Например, два бесконечные множества чье пересечение является конечный набор можно сказать, что они почти не пересекаются.[3]

В топология, существуют различные понятия отдельные наборы с более строгими условиями, чем дизъюнктность. Например, два набора могут считаться разделенными, если они не пересекаются. закрытие или непересекающийся окрестности. Точно так же в метрическое пространство, положительно разделенные множества - множества, разделенные ненулевым расстояние.[4]

Перекрестки

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

Два набора А и B не пересекаются тогда и только тогда, когда их пересечение это пустой набор.[1]Из этого определения следует, что каждое множество не пересекается с пустым множеством, и что пустое множество является единственным множеством, которое не пересекается с самим собой.[5]

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

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

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

А раздел набора Икс - это любой набор непересекающихся друг с другом непустых множеств, союз является Икс.[8] Любое разбиение эквивалентно описывается отношение эквивалентности, а бинарное отношение который описывает, принадлежат ли два элемента к одному и тому же набору в разделе.[8]Структуры данных с непересекающимися наборами[9] и уточнение раздела[10] - это два метода в информатике для эффективного обслуживания разделов набора, подвергнутого соответственно операциям объединения, которые объединяют два набора, или операциям уточнения, которые разбивают один набор на два.

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

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

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

  1. ^ а б Халмос, П. Р. (1960), Наивная теория множеств, Тексты для бакалавриата по математике, Springer, стр. 15, ISBN  9780387900926.
  2. ^ а б Смит, Дуглас; Эгген, Морис; Сент-Андре, Ричард (2010), Переход к высшей математике, Cengage Learning, стр. 95, ISBN  978-0-495-56202-3.
  3. ^ Хальбайзен, Лоренц Дж. (2011), Комбинаторная теория множеств: мягкое введение в принуждение, Монографии Springer по математике, Springer, p. 184, г. ISBN  9781447121732.
  4. ^ Копсон, Эдвард Томас (1988), Метрические пространства, Кембриджские трактаты по математике, 57, Cambridge University Press, стр. 62, ISBN  9780521357326.
  5. ^ Оберсте-Ворт, Ральф В .; Музакитис, Аристидес; Лоуренс, Бонита А. (2012), Мост к абстрактной математике, Учебники MAA, Математическая ассоциация Америки, стр. 59, ISBN  9780883857793.
  6. ^ Посмотреть ответы на вопрос ″ Не пересекается ли пустое семейство множеств попарно? ″
  7. ^ Боллобаш, Бела (1986), Комбинаторика: системы множеств, гиперграфы, семейства векторов и комбинаторная вероятность, Cambridge University Press, стр. 82, ISBN  9780521337038.
  8. ^ а б Халмос (1960), п. 28.
  9. ^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001), "Глава 21: Структуры данных для непересекающихся множеств", Введение в алгоритмы (Второе изд.), MIT Press, стр. 498–524, ISBN  0-262-03293-7.
  10. ^ Пейдж, Роберт; Тарьян, Роберт Э. (1987), "Три алгоритма уточнения раздела", SIAM Журнал по вычислениям, 16 (6): 973–989, Дои:10.1137/0216062, МИСТЕР  0917035.
  11. ^ Ферланд, Кевин (2008), Дискретная математика: введение в доказательства и комбинаторику, Cengage Learning, стр. 45, ISBN  9780618415380.
  12. ^ Arbib, Michael A .; Kfoury, A.J .; Молл, Роберт Н. (1981), Основа теоретической информатики, Серия AKM по теоретической информатике: тексты и монографии по информатике, Springer-Verlag, с. 9, ISBN  9783540905738.
  13. ^ Монен, Жан Франсуа; Хинчи, Майкл Джерард (2003), Понимание формальных методов, Springer, стр. 21, ISBN  9781852332471.
  14. ^ Ли, Джон М. (2010), Введение в топологические многообразия, Тексты для выпускников по математике, 202 (2-е изд.), Springer, p. 64, ISBN  9781441979407.

внешняя ссылка