Из Википедии, бесплатной энциклопедии
  (Перенаправлено из ориентированного дерева )
Перейти к навигации Перейти к поиску
Многодерево.

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

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

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

Термин политерево был придуман в 1987 году Ребэйном и Перлом . [6]

Связанные структуры [ править ]

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

Перечисление [ править ]

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

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

Гипотеза Самнера [ править ]

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

Приложения [ править ]

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

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

См. Также [ править ]

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

Примечания [ править ]

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

Ссылки [ править ]

  • Карр, Хэмиш; Snoeyink, Джек; Аксен, Ульрике (2000), «Вычисление контурных деревьев во всех измерениях», в Proc. 11-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2000) , стр. 918–926
  • Дасгупта, Санджой (1999), "Learning polydrees", in Proc. 15-я конференция по неопределенности в искусственном интеллекте (UAI 1999), Стокгольм, Швеция, июль-август 1999 г. (PDF) , стр. 134–141.
  • Део, Нарсинг (1974), Теория графов с приложениями к технике и информатике (PDF) , Энглвуд, Нью-Джерси: Prentice-Hall, 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 , MR  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.