В комбинаторике и теоретико-упорядоченной математике мультидерево может описывать любую из двух эквивалентных структур: ориентированный ациклический граф (DAG), в котором набор вершин, достижимых из любой вершины, индуцирует дерево , или частично упорядоченное множество (poset), которое не иметь четыре элемента a , b , c и d, образующие алмазный подотряд с a ≤ b ≤ d и a ≤ c ≤ d, но с b и cнесравнимые друг с другом (также называемый посет без алмаза [1] ).
В теории сложности вычислений мультидеревья также называются строго однозначными графами или мангровыми деревьями ; их можно использовать для моделирования недетерминированных алгоритмов, в которых существует не более одного вычислительного пути, соединяющего любые два состояния. [2]
Мультидеревья могут использоваться для представления нескольких перекрывающихся таксономий в одном и том же наборе. [3] Если генеалогическое древо может содержать несколько браков от одной семьи к другой, но не содержит браков между любыми двумя кровными родственниками, то оно образует многодерево. [4]
Эквивалентность определений DAG и poset
В ориентированном ациклическом графе, если набор вершин, достижимых из любой вершины, индуцирует дерево или, что то же самое, если существует не более одного направленного пути между любыми двумя вершинами в любом направлении, то его отношение достижимости является частичным порядком без алмаза. И наоборот, в частичном порядке, если он не содержит ромбов, его транзитивная редукция идентифицирует ориентированный ациклический граф, в котором набор вершин, достижимых из любой вершины, индуцирует дерево
Семьи без бриллиантов
Семейство множеств без ромбов - это семейство F множеств, порядок включения которых образует чугуны без ромбов. Если D ( n ) обозначает максимально возможное не содержащее ромбов семейство подмножеств n -элементного множества, то известно, что
и предполагается, что предел равен 2. [1]
Связанные структуры
Polytree , направленный ациклический граф формируется путем присвоения ориентации к каждому краю неориентированного дерева, может быть рассмотрен как частный случай multitree.
Множество всех вершин , связанных с любой вершины в multitree образует древовидное .
Слово «multitree» также используется для обозначения частичного порядка последовательно-параллельно , [5] , или к другим структурам , сформированных путем объединения нескольких деревьев.
Рекомендации
- ^ a b Griggs, Jerrold R .; Ли, Вэй-Тянь; Лу, Линьюань (2010), Семейства без бриллиантов , arXiv : 1010.5311 , Bibcode : 2010arXiv1010.5311G.
- ^ Аллендер, Эрик ; Ланге, Клаус-Йорн (1996), «StUSPACE (log n ) ⊆ DSPACE (log 2 n / log log n )», Алгоритмы и вычисления, 7-й Международный симпозиум, ISAAC '96, Осака, Япония, 16–18 декабря 1996 г. , Proceedings , Lecture Notes in Computer Science, 1178 , Springer-Verlag, pp. 193–202, doi : 10.1007 / BFb0009495.
- ^ Фурнас, Джордж У .; Закс, Джефф (1994), "Многодеревья: обогащение и повторное использование иерархической структуры", Proc. SIGCHI конференция по Factors человека в вычислительных системах (CHI '94) , стр 330-336,. Да : 10,1145 / 191666,191778 , S2CID 18710118.
- ^ Макгаффин, Майкл Дж .; Балакришнан, Равин (2005), «Интерактивная визуализация генеалогических графов», Симпозиум IEEE по визуализации информации , Лос-Аламитос, Калифорния, США: IEEE Computer Society, стр. 3, DOI : 10,1109 / INFOVIS.2005.22 , S2CID 15449409.
- ^ Юнг, HA (1978), «Об одном классе множеств и соответствующих графах сопоставимости», Журнал комбинаторной теории, серия B , 24 (2): 125–133, DOI : 10.1016 / 0095-8956 (78) 90013-8 , MR 0491356.