Poliárbol

Un poliárbol

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 individualmente conectada ^[4] ) es un gráfico acíclico dirigido cuyo gráfico no dirigido subyacente es un árbol . En otras palabras, si reemplazamos sus aristas dirigidas con aristas no dirigidas, obtenemos un grafo no dirigido que es a la vez conexo y acíclico .

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

Un poliárbol es un ejemplo de gráfico orientado .

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

Estructuras relacionadas

• Una arborescencia es un árbol con raíces dirigidas , es decir, un gráfico acíclico dirigido 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 gráfico acíclico dirigido en el que el subgrafo accesible desde cualquier nodo forma un árbol. Cada poliárbol es un multiárbol .
• La relación de accesibilidad entre los nodos de un poliárbol forma un orden parcial que tiene una dimensión de orden como máximo de tres. Si la dimensión del orden es tres, debe existir un subconjunto de siete elementos , y (para ) tal que, para cada uno , o o , con estas seis desigualdades definiendo la estructura de poliárbol en estos siete elementos. ^[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}}$
• Una valla o un poset en zigzag es un caso especial de un poliárbol en el que el árbol subyacente es un camino y los bordes tienen orientaciones que se alternan a lo largo del camino. El orden de accesibilidad en un poliárbol también se ha denominado valla generalizada . ^[7]

Enumeración

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

1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180, ... (secuencia A000238 en el OEIS ).

La conjetura de Sumner

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

Aplicaciones

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 se puede utilizar la propagación de creencias para realizar inferencias de manera eficiente sobre ella. ^{[4] [5]}

El árbol de contorno de una función de valor real en un espacio vectorial es un poliárbol que describe los conjuntos de niveles de la función. Los nodos del árbol de contorno son los conjuntos de niveles que pasan por un punto crítico de la función y los bordes describen conjuntos contiguos de conjuntos de niveles sin un punto crítico. La orientación de un borde se determina mediante la comparación entre los valores de función en los dos conjuntos de niveles correspondientes. ^[9]

Ver también

• Glosario de teoría de grafos

Notas

1. Dasgupta (1999).
2. Deo (1974), pág. 206.
3. Harary y Sumner (1980); Simón (1991).
4. Kim y Pearl (1983).
5. Rebane y Pearl (1987).
6. Trotter y Moore (1977).
7. Ruskey (1989).
8. Kühn, Mycroft y Osthus (2011).
9. Carr, Snoeyink y Axen (2000).

Referencias

• Carr, Hamish; Snoeyink, Jack; Axen, Ulrike (2000), "Cálculo de árboles de contorno en todas las dimensiones", en Proc. XI Simposio ACM-SIAM sobre algoritmos discretos (SODA 2000), págs. 918–926
• Dasgupta, Sanjoy (1999), "Aprendiendo poliárboles", en Proc. 15.ª Conferencia sobre la incertidumbre en la inteligencia artificial (UAI 1999), Estocolmo, Suecia, julio-agosto de 1999 (PDF) , 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, SEÑOR  0603363.
• Kim, Jin H.; Pearl, Judea (1983), "Un modelo computacional para el razonamiento causal y de diagnóstico en motores de inferencia", en Proc. Octava Conferencia Internacional Conjunta sobre Inteligencia Artificial (IJCAI 1983), Karlsruhe, Alemania, agosto de 1983 (PDF) , págs..
• Kuhn, Daniela ; Mycroft, Richard; Osthus, Deryk (2011), "Una prueba 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 , señor  2793448.
• Rebane, George; Pearl, Judea (1987), "La recuperación de poliárboles causales a partir de datos estadísticos", en Proc. Tercera Conferencia Anual sobre la Incertidumbre en la Inteligencia Artificial (UAI 1987), Seattle, WA, EE. UU., julio de 1987 (PDF) , págs..
• Ruskey, Frank (1989), "Generación de transposición de permutaciones alternas", Orden , 6 (3): 227–233, doi :10.1007/BF00563523, MR  1048093.
• Simion, Rodica (1991), "Árboles con 1 factor 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 posets planos", Journal of Combinatorial Theory , Serie B , 22 (1): 54–67, doi : 10.1016/0095-8956(77)90048-X.