Polytree - Polytree

Многодерево.

В математика, а точнее в теория графов, а многодерево[1] (также называемый направленное дерево,[2] ориентированное дерево[3][4] или же односвязная сеть[5]) это ориентированный ациклический граф чей основной неориентированный граф является дерево. Другими словами, если мы заменим его направленные края с неориентированными ребрами, мы получаем неориентированный граф, который одновременно связаны и ациклический.

А полифорест (или же направленный лес или же ориентированный лес) является ориентированным ациклическим графом, базовым неориентированным графом которого является лес. Другими словами, если мы заменим его ориентированные ребра неориентированными ребрами, мы получим неориентированный граф, который является ациклическим.

Многодерево - это пример ориентированный граф.

Период, термин многодерево был придуман в 1987 году Ребане и Жемчужина.[6]

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

  • An древообразование направленный укорененный дерево, т.е. ориентированный ациклический граф в котором существует единственный исходный узел, у которого есть уникальный путь к каждому другому узлу. Любое древовидное дерево является многодеревом, но не каждое многодерево является древовидным.
  • А многодерево - это ориентированный ациклический граф, в котором подграф, достижимый из любого узла, образует дерево. Каждое многодерево является многодерево.
  • В достижимость отношения между узлами многодерева образуют частичный заказ который имеет размер заказа максимум три. Если размер заказа равен трем, должно существовать подмножество из семи элементов. Икс, уя, и zя (за я = 0, 1, 2) такой, что для каждого я, либо Икс ≤ уя ≥ zя, или же Икс ≥ уя ≤ zя, с этими шестью неравенствами, определяющими структуру многодерева на этих семи элементах.[7]
  • А изгородь или же зигзагообразный позет является частным случаем многодерева, в котором лежащее в основе дерево является путем, а рёбра имеют чередующиеся ориентации вдоль пути. В достижимость упорядочивание в многодереве также называется общий забор.[8]

Перечисление

Количество различных многодеревьев на п немаркированные узлы, для п = 1, 2, 3, ..., является

1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180, ... (последовательность A000238 в OEIS ).

Гипотеза Самнера

Гипотеза Самнера, названный в честь Дэвида Самнера, утверждает, что турниры находятся универсальные графики для многодеревьев, в том смысле, что каждый турнир с 2п - 2 вершины содержат каждое многодерево с п вершины как подграф. Хотя он остается нерешенным, он был доказан для всех достаточно больших значений п.[9]

Приложения

Многодеревья использовались как графическая модель за вероятностное рассуждение.[1] Если Байесовская сеть имеет структуру многодерева, то распространение веры может использоваться для эффективного выполнения вывода.[5][6]

В контурное дерево вещественной функции на векторное пространство политическое дерево, описывающее наборы уровней функции. Узлами дерева контуров являются наборы уровней, которые проходят через критическая точка функции и ребра описывают смежные множества множеств уровня без критической точки. Ориентация кромки определяется путем сравнения значений функции на соответствующих двух наборах уровней.[10]

Смотрите также

Примечания

  1. ^ а б Дасгупта (1999).
  2. ^ Deo 1974, п. 206.
  3. ^ Харари и Самнер (1980).
  4. ^ Симион (1991).
  5. ^ а б Ким и Перл (1983).
  6. ^ а б Ребейн и жемчуг (1987).
  7. ^ Троттер и Мур (1977).
  8. ^ Раски, Франк (1989), "Генерация транспозиции чередующихся перестановок", Заказ, 6 (3): 227–233, Дои:10.1007 / BF00563523, МИСТЕР  1048093
  9. ^ Кюн, Майкрофт и Остхус (2011).
  10. ^ Карр, Snoeyink и Axen (2000).

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