Политри - Polytree

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

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

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

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

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

• Древовидный является направленными корнями дерева , т.е. ориентированного ациклического графа , в котором существует единственный узел - источника , который имеет уникальный путь к каждому другому узлу. Каждое древовидное дерево - это многодерево, но не каждое многодерево является древовидным.
• Multitree представляет собой ориентированный ациклический граф , в котором подграф достижимы из любого узла образует дерево. Каждое многодерево является многодеревом .
• Отношения достижимости между узлами многодерева образуют частичный порядок , размерность которого не превышает трех. Если размерность порядка равна трем, должно существовать подмножество из семи элементов x , y _i и z _i (для i = 0, 1, 2 ), такое что для каждого i либо x ≤ y _i ≥ z _i , либо x ≥ y _i ≤ z _i , причем эти шесть неравенств определяют структуру многодерева на этих семи элементах.
• Забор или зигзагообразный ч.у.м. является частным случаем polytree , в котором основное дерево представляет собой путь и ребра имеют ориентацию , что альтернативную вдоль пути. Достижимости упорядочение в polytree также называется обобщен забором .

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

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

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

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

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

Приложения

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

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

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

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

Примечания

использованная литература

• Карр, Хэмиш; Snoeyink, Джек; Аксен, Ульрике (2000), «Вычисление контурных деревьев во всех измерениях», в Proc. 11-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2000) , стр. 918–926.
• Дасгупта, Санджой (1999), "Learning polydrees", in Proc. 15-я конференция по неопределенности в искусственном интеллекте (UAI 1999), Стокгольм, Швеция, июль-август 1999 г. (PDF) , стр. 134–141.
• Део, Нарсинг (1974), Теория графов с приложениями к технике и информатике (PDF) , Энглвуд, Нью-Джерси: Прентис-Холл, ISBN 0-13-363473-6.
• Харари, Фрэнк ; Самнер, Дэвид (1980), «Дихроматическое число ориентированного дерева», Журнал комбинаторики, информации и системных наук , 5 (3): 184–187, MR  0603363.
• Kim, Jin H .; Перл, Иудея (1983), «Вычислительная модель для причинно-следственных и диагностических рассуждений в механизмах вывода», в Proc. 8-я Международная совместная конференция по искусственному интеллекту (IJCAI 1983), Карлсруэ, Германия, август 1983 г. (PDF) , стр. 190–193.
• Кюн, Даниэла ; Майкрофт, Ричард; Остхус, Дерик (2011), «Доказательство гипотезы Самнера об универсальном турнире для крупных турниров», Труды Лондонского математического общества , Третья серия, 102 (4): 731–766, arXiv : 1010.4430 , doi : 10.1112 / plms / pdq035 , Руководство по ремонту  2793448.
• Ребане, Джордж; Перл, Иудея (1987), «Восстановление причинных полидеревьев из статистических данных», в Proc. 3-я ежегодная конференция по неопределенности в искусственном интеллекте (UAI 1987), Сиэтл, Вашингтон, США, июль 1987 г. (PDF) , стр. 222–228..
• Симион, Родика (1991), «Деревья с 1-факторами и ориентированные деревья», Дискретная математика , 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.