Многодерево

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

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

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

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

• 1 Эквивалентность определений DAG и poset
• 2 семьи без бриллиантов
• 3 Связанные структуры
• 4 ссылки

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

Семейство множеств без ромбов - это семейство 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.

Polytree, направленный ациклический граф формируется путем присвоения ориентации к каждому краю неориентированного дерева, может быть рассмотрен как частный случай multitree.

Множество всех вершин, связанных с любой вершины в multitree образует древовидное.

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