Bachiller

Arboles:
Un árbol es un grafo simple en el cual existe un único camino entre cada par de vértices.
Sea G =(V,A) un grafo no dirigido. G se denomina ARBOL, si es conexo y no contiene ciclos.
Un árbol con raíz, es un árbol que tiene un vértice particular designado como raíz.
Ejemplo de árbol:
En la figura anterior G1 corresponde a lo que llamamos mediante la definición ARBOL, en el caso de G2,éste no corresponde debido a que contiene un ciclo.
Podemos destacar que cuando un grafo G es un Arbol, se reemplaza G, por R.
En la figura mostrada G1 es un subgrafo de G2, en el que G1 contiene los vértices de G2 y es árbol, además lo llamaremos “árbol abarcador”, por que proporciona conexión minimal para el grafo y un esqueleto minimal que une los vértices.

Los árboles son una clase degrafos. Un claro ejemplo de un árbol es el siguiente:
Consideremos cuatro parejas de chismosos {a, A, b, B, c, C, d, D} donde a, b, c y d son los esposos y A, B, C y D son sus esposas respectivamente. Supongamos que a llama a su esposa para contarle algún chisme, entonces ella llama a las otras señoras para difundir el chisme, y cada una de ellas a su vez llama a su esposo para comunicárselo. Elsiguiente grafo muestra la propagación del chisme:

Un árbol es un grafo no dirigido conexo que no contiene circuitos, es decir que no existen dos o más paseos sobre un par de vértices.
Un conjunto de árboles disjuntos es llamado bosque. Un vértice de grado 1 en un árbol se llama hoja o un nodo terminal, y un vértice de grado mayor que 1 recibe el nombre de rama o nodo interno. Por ejemplo, sonhojas: b, c, d y los vértices a, A, B, C, D son nodos rama.
Las propiedades de los árboles son:
• Existe un único paseo entre dos vértices cualesquiera de un árbol.
• El número de vértices es mayor en uno al número de aristas de un árbol.
• Un árbol con dos o más vértices tiene al menos dos hojas.
Un árbol T (libre) es una gráfica simple que satisface lo siguiente; si v y w son vértices en T,existe una trayectoria simple única de v a w. Se muestra un ejemplo:

Un árbol con raíz es un árbol en el que un vértice específico se designa como raíz, se presenta un ejemplo:

Como la trayectoria simple de la raíz a cualquier vértice dado es única, cada vértice está en un nivel determinado de manera única. Así, el nivel de la raíz es el nivel 0, los vértices que están debajo de la raízestán en el nivel 1, y así sucesivamente. Por lo tanto podemos decir que: el nivel de un vértice v es la longitud de la trayectoria simple de la raíz a v.
La altura de un árbol con raíz es el número máximo de nivel que ocurre.
Ejemplo:
Tomando como referencia el gráfico del árbol con raíz determine el nivel del vértice a, b, g y determine también la altura del árbol.
Para el vértice a su nivel es0
Para el vértice b su nivel es 1
Para el vértice g su nivel es 2
La altura del árbol es de 2.
Ejercicio:
Construya dos árboles libres uno de 7 vértices y el otro de 5 vértices, luego determine cuantas aristas tiene cada árbol.

ÁRBOLES DE EXPANSIÓN
Un árbol T es un árbol de expansión de una gráfica G si T es una subgráfica de G que contiene a todos los vértices de G. Una gráfica G tieneun árbol de expansión si y solo si G es conexa.
El árbol de expansión para la gráfica G que se presenta, se muestra con línea seguida.

Existen dos métodos para encontrar el árbol de expansión de una gráfica G:
1. Por búsqueda a lo ancho: permite procesar todos los vértices en un nivel dado antes de moverse al nivel más alto que lo sigue; primero se selecciona un orden de los vértices,considerando el primer vértice de ese orden como raíz.
2. Por búsqueda en profundidad: o conocido también como de regreso.
Ejemplo
Utilice la búsqueda a profundidad con el orden h, g, f, e, d, c, b, a de los vértices para determinar un árbol de expansión de la gráfica G.
Tomado h como vértice raíz tenemos:

Árboles de expansión mínimo
Un árbol de expansión comprende un grafo que posee nodos,...