Poliárbol

Un poliárbol.

En teoría de grafos, un poliárbol​ (también conocido como árbol orientado​​ o red conectada sencilla​) es un grafo acíclico dirigido cuyo grafo no dirigido subyacente es un árbol. En otras palabras, si se remplazan sus arcos dirigidos con aristas no dirigidas, se obtiene un grafo no dirigido que es tanto conectado como 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.​

Estructuras relacionadas

Cada arborescencia (un árbol dirigido radicado, p. ej. un grafo acíclico dirigido en el que existe un solo nodo fuente que tiene una ruta única hacia cada otro nodo) es un poliárbol, pero no todo poliárbol es una arborescencia. Cada poliárbol es un multiárbol, un grafo acíclico dirigido en el cual el subgrafo accesible desde cualquier nodo forma un árbol. La relación de accesibilidad entre los nodos de un poliárbol forma un orden parcial de dimensión de orden tres a lo sumo. Si la dimensión de orden es tres, debe existir un subconjunto de siete elementos x, y_i, y z_i (para i = 0, 1, 2) de tal modo que, para cada i, ya sea x ≤ y_i ≥ z_i, o x ≥ y_i ≤ z_i, en el cual estas seis desigualdades determinan la estructura poliárbol en estos siete elementos.​

Una valla o conjunto parcialmente ordenado en zigzag es un caso especial de poliárbol en el que el árbol subyacente es una ruta y las orientaciones de las aristas alternan a lo largo de la ruta. Al orden (la secuencia) de accesibilidad en un poliárbol se le ha denominado también valla generalizada.​

Enumeración

El número de distintos poliárboles en n nodos no etiquetados, para n = 1, 2, 3, ..., es

1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180, ... (sucesión A000238 en OEIS).

Conjetura de Sumner

En la conjetura de Sumner (por David Sumner) se establece que los torneos son grafos universales para poliárboles, en el sentido que cada torneo con 2n - 2 vértices contiene cada poliárbol con n vértices como subgrafo. Aunque permanece no resuelto, se ha probado para todos los valores suficientemente grandes de n.​

Aplicaciones

En lógica probabilística se han usado poliárboles como modelos en grafo.​ Si una red bayesiana tiene la estructura de poliárbol, para realizar inferencia eficiente acerca de ella se puede usar propagación de credibilidad.​​

El grafo de Reeb de una función de valor real en un vector espacial es un poliárbol que describe los conjuntos de nivel de la función. Los nodos del grafo de Reeb son los conjuntos de nivel que pasan a través de un punto crítico de la función, y las aristas describen conjuntos contiguos de conjuntos de nivel sin punto crítico. La orientación de una arista es determinada por la comparación entre los valores de la función en lo correspondiente a dos conjuntos de niveles.​

Véase también

• Glosario de teoría de grafos

Referencias

• Carr, Hamish; SnoeyEnk, Jack; Ax en, Ulrike (2000), «Computing contour trees in all dimensions», en Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pp. 918-926 .
• Dasgupta, Sanjoy (1999), «Learning polytrees», en Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Sweden, July-August 1999, pp. 134-141 ..
• Harary, Frank; Sumner, David (1980), «The dichromatic number of an oriented tree», Journal of Combinatorics, Information & System Sciences 5 (3): 184-187, MR 603363 ..
• Kim, J en H.; Pearl, Judea (1983), «A computational model for causal and diagnostic reason in inference engines», en Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI 1983), Karlsruhe, Germany, August 1983, pp. 190-193 . (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última)..
• Kühn, Daniela; Mycroft, Richard; Osthus, Deryk (2011), «A proof of Sumner's universal tournament conjecture for large tournaments», Proceedings of the London Mathematical Society, Third Series 102 (4): 731-766, MR 2793448, arXiv:1010.4430, doi:10.1112/plms/pdq035 ..
• Rebane, George; Pearl, Judea (1987), «The recovery of causal poly-trees from statistical data», in Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987, pp. 222-228 . (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última)..
• Simion, Rodica (1991), «Trees with 1-factors and oriented trees», Discrete Mathematics 88 (1): 93-104, MR 1099270, doi:10.1016/0012-365X(91)90061-6 ..
• Trotter, William T., Jr.; Moore, John I., Jr. (1977), «The dimension of planar posets», Journal of Combinatorial Theory, Series B 22 (1): 54-67, doi:10.1016/0095-8956(77)90048-X ..

• Datos: Q7227115