Arbol maximal
Páginas: 3 (646 palabras)
Publicado: 9 de diciembre de 2010
Á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]...
[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]...
Leer documento completo
Regístrate para leer el documento completo.