Polytree

En matemáticas , y más específicamente en teoría de grafos , un poliárbol ^{[ 1 ]} (también llamado árbol dirigido , ^{[ 2 ]} árbol orientado ^{[ 3 ]} o red conexa simple ^{[ 4 ]} ) es un grafo dirigido acíclico cuyo grafo subyacente no dirigido es un árbol . En otras palabras, un poliárbol se forma asignando una orientación a cada arista de un grafo conexo y acíclico no dirigido.

Un polibosque (o bosque dirigido u orientado ) es un grafo dirigido acíclico cuyo grafo subyacente no dirigido es un bosque . En otras palabras, si reemplazamos sus aristas dirigidas por aristas no dirigidas, obtenemos un grafo no dirigido que es acíclico.

Un poliárbol es un ejemplo de grafo orientado .

El término poliárbol fue acuñado en 1987 por Rebane y Pearl . ^{[ 5 ]}

• Una arborescencia es un árbol dirigido con raíz , es decir, un grafo dirigido acíclico en el que existe un único nodo fuente que tiene una ruta única hacia todos los demás nodos. Toda arborescencia es un poliárbol, pero no todo poliárbol es una arborescencia.
• Un multiárbol es un grafo dirigido acíclico en el que el subgrafo alcanzable desde cualquier nodo forma un árbol. Todo poliárbol es un multiárbol .
• La relación de alcanzabilidad entre los nodos de un poliárbol forma un orden parcial que tiene una dimensión de orden como máximo tres. Si la dimensión de orden es tres, debe existir un subconjunto de siete elementos.${\displaystyle x}$,${\displaystyle y_{i}}$, y${\displaystyle z_{i}}$(para${\displaystyle i=0,1,2}$) de tal manera que, para cada${\displaystyle i}$, cualquiera${\displaystyle x\leq y_{i}\geq z_{i}}$o${\displaystyle x\geq y_{i}\leq z_{i}}$, con estas seis desigualdades definiendo la estructura del poliárbol en estos siete elementos. ^{[ 6 ]}
• Un conjunto parcialmente ordenado en zigzag o cerca es un caso especial de un poliárbol en el que el árbol subyacente es un camino y las aristas tienen orientaciones que se alternan a lo largo del camino. El orden de alcanzabilidad en un poliárbol también se ha denominado cerca generalizada . ^{[ 7 ]}

El número de poliárboles distintos en${\displaystyle n}$nodos sin etiquetar, para${\displaystyle n=1,2,3,\dots }$, es

La conjetura de Sumner , que lleva el nombre de David Sumner , afirma que los torneos son grafos universales para poliárboles, en el sentido de que todo torneo con${\displaystyle 2n-2}$vértices contiene cada poliárbol con${\displaystyle n}$vértices como un subgrafo. Aunque sigue sin resolverse, se ha demostrado para todos los valores suficientemente grandes de${\displaystyle n}$. ^{[ 8 ]}

Los poliárboles se han utilizado como modelo gráfico para el razonamiento probabilístico . ^{[ 1 ]} Si una red bayesiana tiene la estructura de un poliárbol, entonces la propagación de creencias puede utilizarse para realizar inferencias de manera eficiente sobre ella. ^{[ 4 ] [ 5 ]}

El árbol de contorno de una función de valores reales en un espacio vectorial es un poliárbol que describe los conjuntos de nivel de la función. Los nodos del árbol de contorno son los conjuntos de nivel que pasan por un punto crítico de la función, y las aristas describen conjuntos contiguos de conjuntos de nivel sin un punto crítico. La orientación de una arista se determina comparando los valores de la función en los dos conjuntos de nivel correspondientes. ^{[ 9 ]}

• Glosario de teoría de grafos

• Carr, Hamish; Snoeyink, Jack; Axen, Ulrike (2000), "Cálculo de árboles de contorno en todas las dimensiones" , Actas del 11.º Simposio ACM-SIAM sobre Algoritmos Discretos (SODA 2000) , Association for Computing Machinery, págs. 918–926 , ISBN  978-0-89871-453-1
• Dasgupta, Sanjoy (1999), "Aprendizaje de poliárboles" (PDF) , Actas de la 15.ª Conferencia sobre Incertidumbre en Inteligencia Artificial (UAI 1999), Estocolmo, Suecia, julio-agosto de 1999 , págs. 134-141 . .
• Deo, Narsingh (1974), Teoría de grafos con aplicaciones a la ingeniería y la informática (PDF) , Englewood, Nueva Jersey: Prentice-Hall, ISBN 0-13-363473-6.
• Harary, Frank ; Sumner, David (1980), "El número dicromático de un árbol orientado", Journal of Combinatorics, Information & System Sciences , 5 (3): 184–187 , MR 0603363 .
• Kim, Jin H.; Pearl, Judea (1983), "Un modelo computacional para el razonamiento causal y diagnóstico en motores de inferencia" (PDF) , Actas de la 8.ª Conferencia Internacional Conjunta sobre Inteligencia Artificial (IJCAI 1983), Karlsruhe, Alemania, agosto de 1983 , págs. 190-193 . .
• Kühn, Daniela ; Mycroft, Richard; Osthus, Deryk (2011), "Una demostración de la conjetura del torneo universal de Sumner para torneos grandes", Actas de la Sociedad Matemática de Londres , Tercera Serie, 102 (4): 731– 766, arXiv : 1010.4430 , doi : 10.1112/plms/pdq035 , MR 2793448 .
• Rebane, George; Pearl, Judea (1987), "La recuperación de poliárboles causales a partir de datos estadísticos" (PDF) , Actas de la 3.ª Conferencia Anual sobre Incertidumbre en Inteligencia Artificial (UAI 1987), Seattle, WA, EE. UU., julio de 1987 , págs. 222-228 . .
• Ruskey, Frank (1989), "Generación por transposición de permutaciones alternas", Order , 6 (3): 227– 233, doi : 10.1007/BF00563523 , MR 1048093 .
• Simion, Rodica (1991), "Árboles con 1-factores y árboles orientados", Matemáticas Discretas , 88 (1): 93– 104, doi : 10.1016/0012-365X(91)90061-6 , MR 1099270 .
• Trotter, William T. Jr .; Moore, John I. Jr. (1977), "La dimensión de los conjuntos parcialmente ordenados planares", Journal of Combinatorial Theory, Serie B , 22 (1): 54–67 , doi : 10.1016/0095-8956(77)90048-X.