Treedit

Un árbol es un grafo G no dirigido que satisface cualquiera de las siguientes condiciones equivalentes:

• G está conectado y es acíclico (no contiene ciclos).
• G es acíclica, y se forma un ciclo simple si se agrega cualquier arista a G.
• G está conectada, pero se desconectaría si se elimina cualquier arista de G.
• G está conectada y el grafo completo de 3 vértices K3 no es menor de G.
• Dos vértices cualesquiera en G se pueden conectar mediante una ruta simple única.

Si G tiene varios vértices finitos, digamos n de ellos, entonces las sentencias anteriores también son equivalentes a cualquiera de las siguientes condiciones:

• G está conectada y tiene n − 1 aristas.
• G está conectado, y cada subgrafo de G incluye al menos un vértice con cero o un borde incidente. (Es decir, G está conectado y 1-degenerado.)
• G no tiene ciclos simples y tiene bordes n – 1.

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: mientras que está conectado vacuamente como un gráfico (dos vértices cualesquiera pueden estar conectados por un camino), no está conectado a 0 (o incluso conectado a (-1)) en topología algebraica, a diferencia de los árboles no vacíos, y viola la relación de «un vértice más que aristas». Sin embargo, puede considerarse como un bosque 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.

Un árbol irreducible (o árbol reducido en serie) es un árbol en el que no hay vértice de grado 2 (enumerado en la secuencia A000014 en el OEIS).

ForestEdit

Un bosque es un gráfico no dirigido en el que dos vértices cualesquiera están conectados como máximo por un camino. De manera equivalente, un bosque es un gráfico acíclico no dirigido, todos cuyos componentes conectados son árboles; en otras palabras, el gráfico consiste en una unión disjunta de árboles. Como casos especiales, el gráfico de orden cero (un bosque que consiste en árboles cero), un solo árbol y un gráfico sin bordes, son ejemplos de bosques.Dado que para cada árbol V-E = 1, podemos contar fácilmente el número de árboles que están dentro de un bosque restando la diferencia entre los vértices totales y los bordes totales. TV-TE = número de árboles en un bosque.

PolytreeEdit

Un polytree (o árbol dirigido u árbol orientado o red conectada individualmente) es un gráfico acíclico dirigido (DAG) cuyo gráfico subyacente no dirigido es un árbol. En otras palabras, si reemplazamos sus aristas dirigidas por aristas no dirigidas, obtenemos un gráfico no dirigido que está conectado y es acíclico.

Algunos autores restringen la frase «árbol dirigido» al caso en que los bordes están todos dirigidos hacia un vértice en particular, o todos dirigidos lejos de un vértice en particular (ver arborescencia).

PolyforestEdit

Un polyforest (o bosque dirigido u bosque orientado) es un gráfico acíclico dirigido cuyo gráfico subyacente no dirigido es un bosque. En otras palabras, si reemplazamos sus aristas dirigidas por aristas no dirigidas, obtenemos un gráfico no dirigido que es acíclico.

Algunos autores restringen la frase «bosque dirigido» al caso en el que los bordes de cada componente conectado están todos dirigidos hacia un vértice en particular, o todos dirigidos lejos de un vértice en particular (consulte ramificación).

Árbol enraizadoeditar

Un árbol enraizado es un árbol en el que un vértice ha sido designado raíz. A los bordes de un árbol enraizado se les puede asignar una orientación natural, ya sea lejos o hacia la raíz, en cuyo caso la estructura se convierte en un árbol enraizado dirigido. Cuando un árbol con raíces dirigidas tiene una orientación alejada de la raíz, se llama arborescencia o árbol externo; cuando tiene una orientación hacia la raíz, se llama anti-arborescencia o árbol interno. El orden de árbol es el orden parcial en los vértices de un árbol con u < v si y solo si la ruta única de la raíz a v pasa a través de u. Un árbol enraizado T que es un subgrafo de algún grafo G es un árbol normal si los extremos de cada ruta en T en G son comparables en este orden de árbol (Diestel 2005, p. 15). Los árboles enraizados, a menudo con estructura adicional, como el orden de los vecinos en cada vértice, son una estructura de datos clave en ciencias de la computación; véase estructura de datos de árbol.

En un contexto donde se supone que los árboles tienen una raíz, un árbol sin ninguna raíz designada se llama árbol libre.

Un árbol etiquetado es un árbol en el que cada vértice recibe una etiqueta única. Los vértices de un árbol etiquetado en n vértices suelen tener las etiquetas 1, 2,…, n. Un árbol recursivo es un árbol enraizado etiquetado donde las etiquetas de vértice respetan el orden de los árboles (i. e., si u < v para dos vértices u y v, entonces la etiqueta de u es más pequeña que la etiqueta de v).

En un árbol enraizado, el padre de un vértice v es el vértice conectado a v en el camino a la raíz; cada vértice tiene un padre único, excepto la raíz, que no tiene padre. Un hijo de un vértice v es un vértice del que v es el padre. Un ascendente de un vértice v es cualquier vértice que es el padre de v o es (recursivamente) el ascendente del padre de v. Un descendiente de un vértice v es cualquier vértice que sea hijo de v o descendiente (recursivamente) de cualquiera de los hijos de v. Un hermano de un vértice v es cualquier otro vértice del árbol que tenga el mismo padre que v. Una hoja es un vértice sin hijos. Un vértice interno es un vértice que no es una hoja.

La altura de un vértice en un árbol enraizado es la longitud del camino descendente más largo hacia una hoja desde ese vértice. La altura del árbol es la altura de la raíz. La profundidad de un vértice es la longitud de la ruta a su raíz (ruta de raíz). Esto se necesita comúnmente en la manipulación de los diversos árboles autoequilibrantes, en particular los árboles AVL. La raíz tiene profundidad cero, las hojas tienen altura cero, y un árbol con un solo vértice (por lo tanto, una raíz y una hoja) tiene profundidad y altura cero. Convencionalmente, un árbol vacío (un árbol sin vértices, si se permiten) tiene profundidad y altura -1.

Un árbol k-ario es un árbol enraizado en el que cada vértice tiene como máximo hijos k. los árboles de 2 arios a menudo se llaman árboles binarios, mientras que los árboles de 3 arios a veces se llaman árboles ternarios.

Árbol ordenadoeditar

Un árbol ordenado (o árbol plano) es un árbol enraizado en el que se especifica un orden para los hijos de cada vértice. Esto se llama un «árbol plano» porque un orden de los hijos es equivalente a una incrustación del árbol en el plano, con la raíz en la parte superior y los hijos de cada vértice más bajos que ese vértice. Dada la incrustación de un árbol enraizado en el plano, si se fija una dirección de los niños, digamos de izquierda a derecha, entonces una incrustación da un orden de los niños. Por el contrario, dado un árbol ordenado, y dibujando convencionalmente la raíz en la parte superior, entonces los vértices secundarios en un árbol ordenado se pueden dibujar de izquierda a derecha, produciendo una incrustación plana esencialmente única.