Arboles.

Arboles:

Un grafo que no tiene ciclos y que conecta a todos los puntos, se llama un árbol. En un grafo con n vértices, los árboles tienen exactamente n - 1 aristas, y hay nn-2 árboles posibles. Su importancia radica en que los árboles son grafos que conectan todos los vértices utilizando el menor número posible de aristas.

Un árbol es un grafo simple unidireccional G que satisface alguna de las siguientes condiciones equivalentes:

* G es conexo y no tiene ciclos simples.

* G no tiene ciclos simples y, si se añade alguna arista se forma un ciclo simple.

* G es conexo y si se le quita alguna arista deja de ser conexo.

* G es conexo y el grafo completo de 3 vértices K3 no es un menor de G.

* Dos vértices cualquiera de G están conectados por un único camino simple.

Si G tiene muchos vértices, n, entonces las definiciones anteriores son también equivalentes a cualquiera de las siguientes condiciones:

* G es conexo y tiene n − 1 aristas.

* G no tiene aristas simples y tiene n − 1 aristas.

* La cantidad de hojas de un árbol siempre es mayor o igual a la mitad de la totalidad de los nodos

En gráfico unidireccional simple G se recibe el nombre de bosque si no tiene ciclos simples.

Un importante campo de aplicación de su estudio se encuentra en el análisis filogenético, el de la filiación de entidades que derivan unas de otras en un proceso evolutivo, que se aplica sobre todo a la averiguación del parentesco entre especies; aunque se ha usado también, por ejemplo, en el estudio del parentesco entre lenguas.

Todo árbol es a su vez un grafo bipartito. Todo árbol con sólo un conjunto contable de vértices es además un grafo plano.

Todo grafo conexo G admite un árbol de cobertura, que es un árbol que contiene cada vértice de G y cuyas aristas son aristas de G.

En ciencias de la informática, un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo es padre de un nodo si existe un enlace desde hasta (en ese caso, también decimos que es hijo de ). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.

Una sucesión de nodos del árbol, de forma que entre cada dos nodos consecutivos de la sucesión haya una relación de parentesco, decimos que es un recorrido árbol. Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad y primero en anchura. En el primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una hoja, donde se vuelve al nodo anterior

...