Полидерево

Полидерево

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

Примечания

1. Дасгупта (1999).
2. Део (1974), стр. 206.
3. Харари и Самнер (1980); Симион (1991).
4. Ким и Перл (1983).
5. Rebane & Pearl (1987).
6. Троттер и Мур (1977).
7. Раски (1989).
8. Кюн, Майкрофт и Остус (2011).
9. Карр, Снойинк и Аксен (2000).

Ссылки

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