Poliárbol

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En matemáticas, y más específicamente en teoría de grafos, un poliárbol (también llamado árbol dirigido, árbol orientado o árbol individualmente conectado) network) 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.

A poliforestal (o bosque dirigido o bosque orientado) es un gráfico acíclico dirigido cuyo gráfico no dirigido subyacente es un bosque. En otras palabras, si reemplazamos sus bordes dirigidos con bordes no dirigidos, obtenemos un gráfico no dirigido que es acíclico.

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

El término polytree fue acuñado en 1987 por Rebane y Pearl.

Estructuras relacionadas

Una arborescencia es un árbol arraigado dirigido, es decir, un gráfico acíclico dirigido en el que existe un único nodo fuente que tiene un camino único a cada otro nodo. Cada arborecencia es un polígono, pero no todo polígono es una arborescencia.
Un multiárbol es un gráfico acíclico dirigido en el que el subgrafo alcanzable de cualquier nodo forma un árbol. Cada polígono es un multiárbol.
La relación de alcanzabilidad entre los nodos de un polígono forma un orden parcial que tiene dimensión de orden a la mayoría de tres. Si la dimensión del orden es tres, debe existir un subconjunto de siete elementos ${displaystyle x}$ , ${displaystyle y_{i}}$ , y ${displaystyle z_{i}}$ (por ${displaystyle i=0,1,2}$ ) tal que, cada uno ${displaystyle i}$ , o ${displaystyle xleq y_{i}geq z_{i}}$ o ${displaystyle xgeq y_{i}leq z_{i}}$ , con estas seis desigualdades que definen la estructura del polígono en estos siete elementos.
Una pose de cerca o zigzag es un caso especial de un polígono en el que el árbol subyacente es un camino y los bordes tienen orientaciones que alternan a lo largo del camino. También se ha llamado la posibilidad de ordenar en un polígono valla generalizada.

Enumeración

El número de distintos polígonos ${displaystyle n}$ Nodos sin etiqueta, por ${displaystyle n=1,2,3,dots }$ , es

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

La conjetura de Summer

La conjetura de Sumner, llamada por David Sumner, afirma que los torneos son gráficos universales para polígonos, en el sentido de que cada torneo con ${displaystyle 2n-2}$ vertices contiene cada polígono con ${displaystyle n}$ vertices como subgrafo. Aunque sigue sin resolverse, se ha demostrado para todos los valores suficientemente grandes de ${displaystyle n}$ .

Aplicaciones

Los poliárboles se han utilizado como modelo gráfico para el razonamiento probabilístico. 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.

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.

Más resultados...