Политри

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

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

Полидерево является примером ориентированного графа .

Термин полидерево был придуман в 1987 году Ребане и Перлом . ^[5]

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

Древовидность — это направленное корневое дерево , то есть ориентированный ациклический граф , в котором существует единственный исходный узел, имеющий уникальный путь к каждому другому узлу . Каждое древовидное дерево является полидеревом, но не каждое полидерево является древовидным.
Мультидерево — это ориентированный ациклический граф, в котором подграф, достижимый из любого узла , образует дерево. Каждое полидерево является мультидеревом .
Отношения достижимости между узлами полидерева образуют частичный порядок , размерность которого не превышает трех. Если размерность порядка равна трем, должно существовать подмножество из семи элементов , и (для ) такое, что для каждого либо или , с этими шестью неравенствами, определяющими структуру полидерева на этих семи элементах . ^[6] $х$ $y_{i}$ $z_{i}$ $я=0,1,2$ $я$ $x\leq y_{i}\geq z_{i}$ $x\geq y_{i}\leq z_{i}$
Заборное или зигзагообразное частичное множество — это частный случай полидерева, в котором базовое дерево является путем, а ориентации ребер чередуются вдоль пути . Порядок достижимости в полидереве также называют обобщенным забором . ^[7]

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

Число различных полидеревьев на непомеченных узлах для , равно $n$ $n=1,2,3,\dots$

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

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

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

Приложения

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

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

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

Глоссарий теории графов

Примечания

^ аб Дасгупта (1999).
^ Део (1974), с. 206.
^ Харари и Самнер (1980); Симион (1991).
^ аб Ким и Перл (1983).
^ аб Ребане и Перл (1987).
^ Троттер и Мур (1977).
^ Раски (1989).
^ Кюн, Майкрофт и Остус (2011).
^ Карр, Снойинк и Аксен (2000).