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

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

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

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

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

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

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

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

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

,

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

Связанные структуры [ править ]

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

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

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

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

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

[gll-1] Перейти обратно: ^а ^б Григгс, Джеррольд Р.; Ли, Вэй-Тянь; Лу, Линьюань (2010), Семьи без алмазов , arXiv : 1010.5311 , Bibcode : 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 .

[1]

[2]

[3]

[4]

[5]