Семейство ламинарных наборов
В комбинаторике семейство ламинарных множеств — это семейство множеств , в котором каждая пара множеств либо не пересекается , либо связана включением. [1] [2] Формально семейство множеств { , S1 S2 , i называется ламинарным, если для каждого j пересечение Si и Sj Sj либо пусто ... } , либо равно , либо равно , . Si
Пусть E — основное множество элементов. Ламинарное семейство множеств на E можно построить путем рекурсивного разделения E на части и подчасти. В частности, одноэлементное семейство { E } является ламинарным; если разбить E на несколько k попарно непересекающихся частей E 1 ,..., E k , то { E , E 1 ,..., E k } тоже будет ламинарным; если мы теперь разделим, например, E 1 на E 11 , E 12 , ... E 1j , то добавление этих подчастей даст еще одно ламинарное семейство; и т. д. Следовательно, ламинарное семейство множеств можно рассматривать как разделение основного множества на категории и подкатегории.
То же понятие можно применить к гиперграфам , чтобы определить «ламинарные гиперграфы» как те, набор гиперребер которых образует семейство ламинарных множеств. [3]
Ссылки
[ редактировать ]- ^ Чериян, Джозеф; Джордан, Тибор; Рави, Р. (1999). «О 2-покрытиях и 2-упаковках ламинарных семейств» . В Нешетриле, Ярослав (ред.). Алгоритмы - ЕСА'99 . Конспекты лекций по информатике. Том. 1643. Берлин, Гейдельберг: Springer. стр. 510–520. дои : 10.1007/3-540-48481-7_44 . ISBN 978-3-540-48481-3 .
- ^ Мадуэль, Яэль; Нутов, Зеев (6 июля 2010 г.). «Покрытие ламинарного семейства связями лист-лист» . Дискретная прикладная математика . 158 (13): 1424–1432. дои : 10.1016/j.dam.2010.04.002 . ISSN 0166-218X .
- ^ Раутенбах, Дитер; Сигети, Золтан (01 августа 2012 г.). «Жадные раскраски слов» . Дискретная прикладная математика . 160 (12): 1872–1874. дои : 10.1016/j.dam.2012.03.038 . ISSN 0166-218X .
 | Эта комбинаторике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |