Arbol maximal

Solo disponible en BuenasTareas
  • Páginas : 3 (646 palabras )
  • Descarga(s) : 0
  • Publicado : 9 de diciembre de 2010
Leer documento completo
Vista previa del texto
ÁRBOLES

[pic]

EJEMPLO

[pic]
[pic]

ÁRBOL GENERADO

Dada una grafica G con conjunto de vértices V y conjunto de bordes E, una árbol generado a partir de G se define como un árbol cuyoconjunto de bordes es un subconjunto de V.

ÁRBOL DEGENERADO
[pic]

ALGORITMO PARA DETERMINAR ÁRBOLES GENERADOS – SPANTREE

Entrada: una gráfica con un conjunto de vértices V y un conjunto debordes E.
Salida: El conjunto de bordes de un árbol generado a partir de G.

Procedimiento:

Sea x(V, entonces V’= {x}, es el conjunto de vértices del árbol generado. F = (, es el conjunto debordes.
1) Elija un borde e que una un vértice v(V’ a un vértice y que no esté en V’.
2) Agregue y a V’.
3) Agregue e a F.

EJEMPLO

Dada la lista de adyacencia
[pic]

1. Construya lagráfica G.
2. Aplique el algoritmo Spantree para hallar un árbol generado, iniciando con x = a.

Solución.

La gráfica es:
[pic]

El árbol generado

Si inicia con V’ ={a} y se eligen los bordescorrespondientes a la lista de adyacencia de a.

[pic]

Entonces V’={a, b, d, e}
Se puede usar d o e para continuar el proceso, observe que d no se puede usar porque no es adyacente a ningúnvértice que no esté en V’. Si se usa d se pueden elegir los bordes {d, c} y {d, f} con lo que se obtiene

[pic]

[pic]

ÁRBOL MAXIMAL

[pic]

EJEMPLO

[pic]

[pic]

EJEMPLO

[pic]

[pic][pic]

[pic]

EJEMPLO
[pic]
[pic]

[pic]

[pic]

[pic]

[pic]

CARACTERÍSTICAS EQUIVALENTES PARA LOS ÁRBOLES

[pic]
ÁRBOLES GENERADORES

[pic]

EJEMPLO

[pic]
[pic]ARBOL MAXIMAL MINIMAL

[pic]

ALGORITMO DE KRUSKAL

Se usa para obtener árboles máximos de peso mínimo.
[pic]
[pic]

EJEMPLO
[pic]

[pic]
[pic]
[pic]

[pic]

[pic]
[pic]

[pic][pic]
[pic]

[pic]

[pic]
[pic]
[pic]

ÁRBOL MAXIMAL MÁXIMO

[pic]

EJEMPLO

[pic]
[pic]

[pic]
[pic]

[pic]

[pic]

[pic]

ÁRBOLES CON RAÍZ

[pic]

EJEMPLO

[pic]...
tracking img