En la teoría de grafos , un árbol es un grafo no dirigido en el que dos vértices cualesquiera están conectados por exactamente una ruta , o equivalentemente un grafo no dirigido acíclico conectado . [1] Un bosque es un grafo no dirigido en el que dos vértices cualesquiera están conectados por como máximo un camino, o equivalentemente un grafo acíclico no dirigido, o equivalentemente una unión disjunta de árboles. [2]
Un polytree [3] (o árbol dirigido [4] o árbol orientado [5] [6] o red conectada individualmente [7] ) es un gráfico acíclico dirigido (DAG) cuyo gráfico subyacente no dirigido es un árbol. Un polibosque (o bosque dirigido o bosque orientado ) es un gráfico acíclico dirigido cuyo gráfico subyacente no dirigido es un bosque.
Los diversos tipos de estructuras de datos a los que se hace referencia como árboles en informática tienen gráficos subyacentes que son árboles en la teoría de gráficos, aunque tales estructuras de datos son generalmente árboles enraizados . Un árbol enraizado puede ser dirigido, llamado árbol enraizado dirigido , [8] [9] ya sea haciendo que todos sus bordes apunten en dirección opuesta a la raíz, en cuyo caso se llama arborescencia [4] [10] o fuera del árbol [11 ] [12] —o hacer que todos sus bordes apunten hacia la raíz — en cuyo caso se llama anti-arborescencia [13] o in-tree. [11] [14] Algunos autores han definido un árbol enraizado como un gráfico dirigido. [15] [16] [17] Un bosque enraizado es una unión desarticulada de árboles enraizados. Un bosque enraizado puede ser dirigido, llamado bosque enraizado dirigido , ya sea haciendo que todos sus bordes apunten en dirección opuesta a la raíz de cada árbol enraizado, en cuyo caso se le llama ramificación o bosque externo, o haciendo que todos sus bordes apunten hacia la raíz. en cada árbol enraizado, en cuyo caso se denomina anti-ramificación o en el bosque .
Si G tiene un número finito de vértices, digamos n de ellos, entonces las declaraciones anteriores también son equivalentes a cualquiera de las siguientes condiciones:
Como en otras partes de la teoría de grafos, el grafo de orden cero (grafo sin vértices) generalmente no se considera un árbol: si bien está conectado de forma vacía como un grafo (dos vértices cualesquiera pueden estar conectados por una ruta), no es 0 -conectado (o incluso (-1) -conectado) en topología algebraica, a diferencia de los árboles no vacíos, y viola la relación "un vértice más que bordes". Sin embargo, puede considerarse como un bosque compuesto por cero árboles.
Un vértice interno (o vértice interno o vértice de rama ) es un vértice de grado al menos 2. De manera similar, un vértice externo (o vértice externo , vértice terminal u hoja ) es un vértice de grado 1.