grafo y arboles

Arboles y Grafos


Un Grafo (o grafo no dirigido) es un conjunto V de vértices y un conjunto E de aristas tales que cada arista e ? E(queda asociada a un par no ordenado de vértices. Si existe una única arista e asociada con los vértices v y w, escribimos e = (v,w). En este contexto (v,w) denota una arista en un grafo no dirigido y no un par ordenado.
Un grafo dirigido (o digrafo) consta deun conjunto finito de vértices V y un conjunto de arcos E ? V × V (obsérvese que cada arco es un par ordenado de vértices).
Grafo conexo: un grafo G es conexo si dados cualesquiera dos vértices v y w en G, existe un camino de v a w.
Camino: sean v0 y vn vértices de un grafo. Un camino de v0 a vn de longitud n es una sucesión alternante de n+1 vértices y n aristas que comienza con el vértice v0 ytermina con el vértice vn.
Longitud del camino: es el número de aristas que contiene.
Ciclo: sean v y w vértices en un grafo G, un ciclo o circuito es un camino de longitud distinta de 0 de v a w, sin aristas repetidas.
Subgrafo: sea G (V, E) un grafo. (V", E") es un subgrafo de G si
• a) V" ( V y E"( E.
• b) Para cada arista e" ( E", si e" es incidente en v" y w", entonces v", w" ( V.
Grafocon pesos (o poderado): es un grafo en el cual se le asignan valores a las aristas y la longitud del camino de un grafo con pesos es la suma de todos los pesos de las aristas en la ruta (camino).
Árbol: es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino.
Sección 2:
Árboles de expansión
Definición: un árbol T es un árbol de expansión de un grafo G si Tes un subgrafo de G que contiene a todos los vértices de G.
Un grafo G tiene un árbol de expansión si y solo si G es conexo.
Sección 3: ARBOLES DE EXPANSION MINIMA
Definición: sea G un árbol con pesos. Un árbol de expansión mínimo de G es un árbol de expansión de G con mínimo peso, es decir cuya suma de pesos sea mínima.
Para calcular el árbol de peso mínimo existen 2 algoritmos:
• Prim:Consiste en ir borrando las aristas de mayor peso posible y que no sean aristas de separación.
• Kruskal: Se van escogiendo las aristas de menor peso hasta conseguir un árbol de peso mínimo
Algoritmo de Prim: Este algoritmo determina un árbol de expansión mínimo en un grafo conexo con pesos.
El algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el pesototal de todas las aristas en el árbol es el mínimo posible.
Pasos para realizar el algoritmo:
• 1. Se marca un nodo cualquiera, será el nodo de partida.
• 2. Seleccionamos la arista de menos valor incidente en el nodo marcado anteriormente, y marcamos el otro nodo en el que incide.
• 3. Repetir el paso 2 siempre que la arista elegida enlace un nodo y otro que no lo esté.
• 4. El procesotermina cuando tenemos todos los nodos del grafo marcados.
Al concluir el algoritmo, T es un árbol de expansión mínimo.


Algoritmo de Kruskal: Se eligen aristas de la forma más económica. Inicialmente se ordenan las aristas por su peso. A continuación se van eligiendo las aristas de menor peso de modo tal, que no formen ciclo con las aristas anteriormente seleccionadas. Para evitar que seformen ciclos se asignan etiquetas a los vértices de modo que los vértices que formen parte de las aristas ya elegidas tengan todos la misma etiqueta. Una etiqueta es una información asociada a un vértice que los hace distinguibles entre sí.
1. T= {}
2. Asignar etiquetas a todos los vértices t(i)=i, i=1, 2, ..., n.
3. Mientras haya vértices con etiquetas diferentes repetir.
a)Escoger la arista (u, v) de menor peso tal que t(u) sea diferente de t(v). Agregarla a T
b) Asignar a todos los vértices de una componente conexa de T la misma etiqueta.

Sección 4:
Árboles binarios
Definición: un árbol binario es un árbol con raíz en el cual cada vértice tiene cero, uno o dos hijos. Si un vértice tiene un hijo, ese hijo se designa como un hijo izquierdo o un hijo...