Мультидерево

Ориентированный ациклический граф с ≤1 направленными путями между любыми двумя узлами

Сеть -бабочка , мультидерево, используемое в распределенных вычислениях, показывает красным неориентированное дерево, порожденное подграфом, достижимым из одной из его вершин.

В комбинаторике и теории порядка мультидерево может описывать любую из двух эквивалентных структур: ориентированный ациклический граф (DAG), в котором существует не более одного направленного пути между любыми двумя вершинами , или, что то же самое, в котором подграф , достижимый из любой вершины , индуцирует ненаправленный путь. дерево или частично упорядоченный набор (poset), который не имеет четырех элементов a , b , c и d , образующих ромбовидный подпорядок с a ≤ b ≤ d и a ≤ c ≤ d , но с b и c, несравнимыми друг с другом ( также называется безромбовым чуз-множеством ^[1] ).

В теории сложности вычислений мультидеревья также называют строго однозначными графами или мангровыми зарослями ; их можно использовать для моделирования недетерминированных алгоритмов , в которых существует не более одного вычислительного пути, соединяющего любые два состояния. ^[2]

Мультидеревья могут использоваться для представления нескольких перекрывающихся таксономий в одном и том же наборе оснований. ^[3] Если генеалогическое древо может содержать несколько браков из одной семьи в другую, но не содержит браков между какими-либо двумя кровными родственниками, то оно образует мультидерево. ^[4]

Эквивалентность между определениями DAG и чузета

В ориентированном ациклическом графе, если существует не более одного направленного пути между любыми двумя вершинами или, что то же самое, если подграф, достижимый из любой вершины, порождает неориентированное дерево, то его отношение достижимости представляет собой частичный порядок без алмазов. И наоборот, в частичном порядке без алмазов транзитивная редукция идентифицирует ориентированный ациклический граф, в котором подграф, достижимый из любой вершины, индуцирует неориентированное дерево.

Семьи без бриллиантов

Семейство множеств без алмазов — это семейство F множеств, порядок включения которых образует частичное множество без алмазов. Если D ( n ) обозначает максимально возможное безромбовое семейство подмножеств n -элементного множества, то известно, что

${\displaystyle 2\leq \lim _{n\to \infty }D(n){\Big /}{\binom {n}{\lfloor n/2\rfloor }}\leq 2{\frac {3}{11}}}$,

и предполагается, что предел равен 2. ^[1]

Связанные структуры

Полидерево , ориентированный ациклический граф, образованный ориентацией ребер неориентированного дерева, является частным случаем мультидерева.

Подграф, достижимый из любой вершины мультидерева, представляет собой древовидное дерево с корнем в вершине, то есть полидерево, в котором все ребра ориентированы от корня.

Слово «мультидерево» также использовалось для обозначения последовательно-параллельного частичного порядка [ ^5] или других структур, образованных путем объединения нескольких деревьев.

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

1. Григгс, Джеррольд Р.; Ли, Вэй-Тянь; Лу, Линьюань (2010), Семьи без алмазов , arXiv : 1010.5311 , Бибкод : 2010arXiv1010.5311G.
2. Аллендер, Эрик ; Ланге, Клаус-Йорн (1996), «StUSPACE(log n ) ⊆ DSPACE(log ² n /log log n )», «Алгоритмы и вычисления», 7-й Международный симпозиум, ISAAC '96, Осака, Япония, 16–18 декабря 1996 г. , Труды , Конспекты лекций по информатике, вып. 1178, Springer-Verlag, стр. 193–202, номер документа : 10.1007/BFb0009495. .
3. Фернас, Джордж В .; Закс, Джефф (1994), "Мультидеревья: обогащение и повторное использование иерархической структуры", Proc. Конференция SIGCHI по человеческому фактору в вычислительных системах (CHI '94) , стр. 330–336, doi : 10.1145/191666.191778, S2CID  18710118.
4. Макгаффин, Майкл Дж.; Балакришнан, Рэвин (2005), «Интерактивная визуализация генеалогических графиков», Симпозиум IEEE по визуализации информации , Лос-Аламитос, Калифорния, США: Компьютерное общество IEEE, стр. 3, номер документа : 10.1109/INFOVIS.2005.22, S2CID  15449409.
5. Юнг, Х.А. (1978), «Об одном классе частично упорядоченных множеств и соответствующих графах сравнимости», Журнал комбинаторной теории, серия B , 24 (2): 125–133, doi : 10.1016/0095-8956(78)90013- 8 , МР  0491356.