Arboles graficos

17-mayo-2010
Pastor Tecuapa Luis G.
Árbol de expansión mínima
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 portodos 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 los vértices. Esto es, cadavé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én definido como el mayorconjunto 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 el mínimo árbol deexpansión de un grafo ponderado. También se han abordado otros problemas de optimización relacionados con los árboles de expansión, como el máximo árbol de expansión, el máximo árbol que cubre al menos kvértices, el mínimo árbol de expansión con k aristas por vértice como máximo (árbol de expansión de mínimo grado, MDST por sus siglas en inglés), el árbol de expansión con el máximo número de hojas(estrechamente relacionado con el problema del menos conjunto dominante y conexo), el árbol de expansión con el menor número de hojas (relacionado con el problema del camino hamiltoniano), el árbol deexpansión de mínimo diámetro o el árbol de expansión de la mínima dilación.

Recorrido de arboles
Hay tres manera de recorrer un árbol : en inorden, preorden y postorden. Cada una de ellas tieneuna secuencia distinta para analizar el árbol como se puede ver a continuación:
1. INORDEN
* Recorrer el subarbol izquierdo en inorden.
* Examinar la raíz.
* Recorrer elsubarbol derecho en inorden.
2. PREORDEN
* Examinar la raíz.
* Recorrer el subarbol izquierdo en preorden.
* recorrer el subarbol derecho en preorden.
3. POSTORDEN...