Grafos 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 de un 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 y termina 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.

Grafo con 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 T es 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 peso total 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 proceso termina cuando tenemos todos los nodos del grafo marcados.

Al concluir el algoritmo, T es un árbol de expansión mínimo.

Algoritmo

...