Из Википедии, бесплатной энциклопедии
  (Перенаправлен из Парного непересекающегося )
Перейти к навигации Перейти к поиску
Эта статья о математической концепции. Для структуры данных см. Структура данных с несвязанным набором .
Два непересекающихся множества.

В математике два набора называются непересекающимися наборами, если у них нет общих элементов . Эквивалентно, два непересекающихся множества - это множества, пересечение которых является пустым множеством . [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]

Перекрестки [ править ]

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

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

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

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

Непересекающиеся союзы и разделы [ править ]

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

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ a b Halmos, PR (1960), Теория наивных множеств , Тексты для бакалавров по математике , Springer, стр. 15, ISBN 9780387900926.
  2. ^ a b Смит, Дуглас; Эгген, Морис; Сент-Андре, Ричард (2010), Переход к высшей математике , Cengage Learning, стр. 95, ISBN 978-0-495-56202-3.
  3. ^ Halbeisen, Лоренц J. (2011), комбинаторная теория множеств: С Gentle Введением в Принудительный , Springer монографии в области математики, Springer, стр. 184, ISBN 9781447121732.
  4. ^ Копсон, Эдвард Томас (1988), Метрические пространства , Кембриджские трактаты по математике, 57 , Cambridge University Press, стр. 62, ISBN 9780521357326.
  5. ^ Оберсте-Ворт, Ральф В .; Музакитис, Аристидес; Лоуренс, Бонита А. (2012), Мост к абстрактной математике , учебники MAA, Математическая ассоциация Америки, стр. 59, ISBN 9780883857793.
  6. ^ См. Ответы на вопрос «Не пересекается ли пустое семейство множеств попарно?»
  7. ^ Bollobás, Бел (1986), Комбинаторика: Set Systems, Гиперграфы, семейство векторов и комбинаторная Вероятность , 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, DOI : 10,1137 / 0216062 , МР 0917035 .
  11. ^ Ферланд, Кевин (2008), Дискретная математика: Введение в доказательства и комбинаторику , Cengage Learning, стр. 45, ISBN 9780618415380.
  12. ^ Арбиб, Майкл А .; Kfoury, AJ; Молл, Роберт Н. (1981), Основа теоретической информатики , Серия AKM по теоретической информатике: тексты и монографии по информатике, Springer-Verlag, стр. 9, ISBN 9783540905738.
  13. ^ Монен, Жан Франсуа; Хинчи, Майкл Джерард (2003), Понимание формальных методов , Springer, стр. 21, ISBN 9781852332471.
  14. ^ Ли, Джон М. (2010), Введение в топологические многообразия , Тексты для выпускников по математике, 202 (2-е изд.), Springer, стр. 64, ISBN 9781441979407.

Внешние ссылки [ править ]

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