Poliárbol

En teoría de grafos, un poliárbol^[1]​ (también conocido como árbol orientado(Harary y Sumner, 1980)^[2]​ o red conectada sencilla^[3]​) 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 no grafo 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.^[4]​

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.(Trotter y Moore, 1977)

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.^[5]​

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

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.(Kühn et al., 2011)

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

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.(Carr et al., 2000)

---