En la teoría de grafos , un árbol es un gráfico no dirigido en el que dos vértices cualesquiera están conectados por exactamente un camino , o de manera equivalente, un gráfico no dirigido acíclico conectado . [1] Un bosque es un grafo no dirigido en el que dos vértices están conectados como máximo por un camino, o de manera equivalente un grafo no dirigido acíclico, o de manera equivalente una unión disjunta de árboles. [2]
Un poliárbol [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 grafo acíclico dirigido cuyo grafo no dirigido subyacente es un bosque.
Los diversos tipos de estructuras de datos a las 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 con raíz . Un árbol enraizado puede ser dirigido, llamado árbol enraizado dirigido , [8] [9] ya sea haciendo que todos sus bordes apunten lejos de la raíz, en cuyo caso se llama arborescencia [4] [10] o fuera de árbol [11 ] [12] —o hacer que todos sus bordes apunten hacia la raíz— en cuyo caso se denomina 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 inconexa 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 en cada árbol enraizado, en cuyo caso se denomina bosque ramificado o exterior, 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 gráfico de orden cero (gráfico sin vértices) generalmente no se considera un árbol: mientras que está conectado de forma vacía como un gráfico (dos vértices cualesquiera pueden estar conectados por un camino), 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 ser considerado como un bosque que consta de 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.