Политри

Полидерево

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

См. также

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

Ссылки

• Карр, Хэмиш; Снойинк, Джек; Аксен, Ульрике (2000), «Вычисление контурных деревьев во всех измерениях», в Proc. 11-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2000) , стр. 918–926.
• Дасгупта, Санджой (1999), «Изучение многодеревьев», в Proc. 15-я конференция по неопределенности в искусственном интеллекте (UAI 1999), Стокгольм, Швеция, июль-август 1999 г. (PDF) , стр. 134–141 .
• Део, Нарсингх (1974), Теория графов с приложениями к инженерии и информатике (PDF) , Энглвуд, Нью-Джерси: Прентис-Холл, ISBN  0-13-363473-6 .
• Харари, Фрэнк ; Самнер, Дэвид (1980), «Дихроматическое число ориентированного дерева», Журнал комбинаторики, информации и системных наук , 5 (3): 184–187, MR   0603363 .
• Ким, Джин Х.; Перл, Иудея (1983), «Вычислительная модель для причинных и диагностических рассуждений в машинах вывода», в Proc. 8-я Международная совместная конференция по искусственному интеллекту (IJCAI 1983), Карлсруэ, Германия, август 1983 г. (PDF) , стр. 190–193 .
• Кюн, Даниэла ; Майкрофт, Ричард; Остус, Дерик (2011), «Доказательство гипотезы Самнера об универсальном турнире для больших турниров», Proceedings of the London Mathematical Society , Third Series, 102 (4): 731–766, arXiv : 1010.4430 , doi : 10.1112/plms/pdq035 , МР   2793448 .
• Ребане, Джордж; Перл, Иудея (1987), «Восстановление причинных полидеревьев по статистическим данным», в Proc. 3-я ежегодная конференция по неопределенности в искусственном интеллекте (UAI, 1987), Сиэтл, Вашингтон, США, июль 1987 г. (PDF) , стр. 222–228 .
• Раски, Фрэнк (1989), «Транспозиционная генерация чередующихся перестановок», Order , 6 (3): 227–233, doi : 10.1007/BF00563523 , MR   1048093 .
• Симион, Родика (1991), «Деревья с 1-факторами и ориентированные деревья», Discrete Mathematics , 88 (1): 93–104, doi : 10.1016/0012-365X(91)90061-6 , MR   1099270 .
• Троттер, Уильям Т. младший ; Мур, Джон И. младший (1977), «Размерность плоских частично упорядоченных множеств», Журнал комбинаторной теории , серия B , 22 (1): 54–67, doi : 10.1016/0095-8956(77)90048-X .