Arboles

6.
Árbol libre: es un grafo no dirigido acíclico conexo.

7. Arboles de expansión
En el campo matemático de la teoría de grafos, un árbol de expansión T de un grafo conexo, no dirigido G es unárbol compuesto por todos los vértices y algunas (quizá todas) de las aristas de G. Informalmente, un árbol de expansión de G es una selección de aristas de G que forman un árbol que cubre todos losvértices. Esto es, cada vértice está en el árbol, pero no hay ciclos.
Por otro lado, todos los puentes de G deben estar contenidos en T.
Un árbol de expansión de un grafo conexo G puede ser tambiéndefinido como el mayor conjunto de aristas de G que no contiene ciclos, o como el mínimo conjunto de aristas que conecta todos los vértices.
En ciertos campos de la teoría de grafos es útil encontrar elmínimo árbol de expansión de un grafo ponderado.

7.1
La idea es procesar todos los vértices de un nivel dado antes de pasar al siguiente nivel superior.
Tomemos la grafica G del ejemplo:Elegimos un orden (cualquiera) digamos abcdefgh, de los vértices de G
Elegimos el primer vértice a y lo etiquetamos como la raíz, siendo T la grafica formada por el único vértice a sinaristas.
Luego,agregamos a T todas las aristas (a,x) y los vértices sobre los cuales son incidentes, desde x = b hasta h, que no produzcan un ciclo al agregarse a T.
Repetimos este procedimiento con los vérticesdel nivel 1, examinándolos en orden.
7.2
Este método pasa a los niveles sucesivos de un árbol en la primera oportunidad posible.
a) Elegimos el primer vértice a y lo llamamos la raíz
b) Agregamosa nuestro árbol la arista (a, x) con x mínimo. En nuestro caso, agregamos la arista (a, b)
c) Repetimos este proceso. Agregamos las aristas (b, d) (d, c) (c, e)
(e, f) y (f, h)
d) Aquínos damoscuenta que no podemos agregar (h, x), así que retrocedemos al padre f de h e intentamos agregar una arista de la forma (f, x)
e) Nuevamente, no podemos lograr esto, de modo que regresamos al padre...