Download Grafo Un grafo G es un par G=(V, E) donde V es un

Unidad III. Grafos
Teoría de grafos 2-2010
Definiciones, representaciones, tipos de grafos y árboles
UNEFA-Núcleo Mérida
Grafo Un grafo G es un par G=(V, E) donde V es un conjunto finito de elementos llamados vértices o nodos y E un conjunto de pares no ordenados de vértices que se denominan aristas o arcos.
Propiedades
• El número de vértices de un grafo G, es el orden del grafo.
• El número de aristas de un grafo G, es su tamaño.
• Dos aristas son independientes si no tienen vértices en común.
• Si una arista relaciona dos vértices (u,v) se dicen que u y v son vértices adyacentes.
• Un lazo o bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.
Ejemplo: Para el siguiente grafo, determine el número de vértices y aristas; escriba además, dos vértices adyacentes y dos independientes.
Figura 1: Grafo con 5 vértices y 8 aristas
•
•
•
•
Número de vértices = 5
Número de aristas = 8
Los vértices u y v son vértices adyacentes.
Los vértices u y w son vértices independientes.
Grado de un vértice en un grafo Se denomina grado de un vértice v de un grafo no dirigido G al número de aristas que inciden en v, y se designará g(v) (un lazo en v contribuye de manera doble al grado de v). Grado de un vértice en un digrafo
En un grafo dirigido, el grado de salida es el número de aristas que salen de él, y el grado de entrada es el número de aristas que entran en él. A un vértice de grado 0 se le denomina vértice aislado. A un vértice de grado 1 se le denomina vértice terminal o extremo.
Incidencia de un Grafo
Si (u, v) es una arista de un grafo dirigido, decimos que incide desde o sale de el vértice u, que será su vértice inicial, y que incide hacia o entra en el vértice v, que será su vértice final. Si se trata de un grafo no dirigido, decimos que (u,v) simplemente incide en los vértices u y v, que serán sus vértices extremos.
Unidad III. Grafos
Teoría de grafos 2-2010
Definiciones, representaciones, tipos de grafos y árboles
UNEFA-Núcleo Mérida
Representaciones de los Grafos Existen diversas maneras de representar un grafo. Las más destacadas por su uso son las siguientes:
1.­ Representación Gráfica Consiste en un gráfico en que los vértices se representan mediante puntos. En función del tipo de grafo que se tenga, ocurre:
­ Los vértices se unen mediante segmentos si el grafo es no orientado.
­ Los vértices se unen mediante flechas indicando el vértice origen y final si el grafo es orientado.
Este tipo de representación es adecuada para la interpretación y resolución de problemas en grafos pequeños o medianos.
Ejemplos:
Figura 2: Grafo no dirigido Figura 3:Grafo dirigido
2.­ Representación relacional
Se basa en la aplicación de representación en pares ordenados de la relación que compone el grafo. Figura 4:Grafo dirigido para el ejemplo de representación en forma de relación.
R={(v7,v6),(v7,v1),(v1,v2),(v6,v2),(v2,v5),(v2,v3),(v3,v4),(v5,v4)}
3.­ Representación Matricial
3.1.­ Matriz de Adyacencia: la matriz de adyacencia asociada al grafo G = (V,E) es la matriz M=(mij) de orden pxp y definida en función del tipo de grafo que se tenga.
Si el grafo es no dirigido se tiene: Unidad III. Grafos
Teoría de grafos 2-2010
Definiciones, representaciones, tipos de grafos y árboles
UNEFA-Núcleo Mérida
1 si Vi Vj Є E (Si Vi Vj se relacionan)
mij = 0 si Vi Vj no pertenece E (Si Vi Vj no se relacionan)
Si el grafo es dirigido se tiene:
1 si Vi Vj Є E y la orientación de tal arista es Vi → Vj mij = 0 si Vi Vj no pertenece o Vi Vj Є E y la orientación de tal arista es Vj → Vi
Ejemplo:
Un ejemplo de representación gráfica de un grafo no dirigido es el grafo formado por el conjunto de vértices que representan las poblaciones anteriores: v1= {Cerecinos de Campos}, v2 = {Villalpando}, v3 = {Valladolid}, v4 = {Pozaldez}, v5 = {Medina del Campo}, v6 = {Villafáfila} y v7 = {Revellinos}, y, el conjunto de aristas que representa la dirección en que una persona puede ir de una población a otra queda descrito a continuación:
e1 ={Cerecinos de Campos, Villapando}, e2 ={Villapando, Valladolid}, e3 ={Valladolid, Pozaldez}, e4 ={ Medina del Campo, Pozaldez},
e5 ={Villalpando, Medina del Campo}, e6 ={Villafáfila, Villapando},
e7 ={ Revellinos, Villafáfila}
Figura 5:Grafo dirigido para ejemplo de representación relacional y matriz de adyacencia.
Una persona puede ir de Revellinos a Cerecinos de Campos o a Villafáfila, pero no puede ir de Cerecinos de Campos a Revellinos.
La matriz de adyacencia que forma el grafo anterior es el siguiente:
Unidad III. Grafos
Teoría de grafos 2-2010
Definiciones, representaciones, tipos de grafos y árboles
UNEFA-Núcleo Mérida
3.2.­ Matriz de Incidencia: sea G=(V,E) un grafo con v vertices y e aristas, entonces le corresponde una matriz v × e denominada la matriz de incidencia de G. Si denotamos los vertices de G por v1, v2, . . . , vv y las aristas por e1, e2, . . . , ee. Entonces la matriz de incidencia de G es la matriz M(G) = [mij] donde mij es el numero de veces que la arista ej incide en el vertice vi; los valores son 0,1 ó 2 (2 en el caso que la arista sea un lazo).
Si G es un digrafo la matriz de incidencia se define como sigue:
1, si vi es incidente hacia el arco aj
Bij = ˉ1, si vi es incidente desde el arco aj
0, en otro caso
4.­ Lista de Adyacencia Consiste en una lista de los vértices del grafo y además para cada vértice una lista de sus vértices vecinos.
Ejemplo:
Figura 6: Grafo. Matriz de adyacencia. Lista de Adyacencia
Caminos, trayectorias, circuitos y ciclos
Los grafos son usados de manera habitual para representar redes de transporte. Para poder recorrer las redes de transporte es necesario conocer algunas definiciones básicas. Sea un grafo G. Se denomina un camino en G a una sucesión de vértices y de aristas v0 ,e1, v1, e2 ,..., vn­1, en, vn , o, simplemente v0, v1,..., vn­1, vn donde ei es el arco de extremos Vi­1 y vi , i = 1,2,…,n. Los vértices v0 y v1 se denominan vértice inicial y vértice final. La longitud del camino es el número de aristas n que lo contiene.
Un camino se dice que es cerrado si v0 = vn .
• Un camino se dice que es simple si no hay ninguna arista repetida.
• Una trayectoria es un camino simple en el que no se repite ningún vértice.
Unidad III. Grafos
Teoría de grafos 2-2010
•
•
Definiciones, representaciones, tipos de grafos y árboles
UNEFA-Núcleo Mérida
Un ciclo es un camino cerrado en el que no se repite ningún vértice excepto el primero y el último.
Un circuito es un camino cerrado en el que no se repite ninguna arista.
Ejemplo:
Figura 6: Camino. Ciclo. Circuito
Analíticamente, un camino C podría ser C ={v1,v2,v6,v7,v1,v6}, un camino cerrado puede ser C1={v1,v2,v6,v7,v6,v1}, un camino simple es C2={v1,v2,v3,v4,v5,v3}, una trayectoria es C3={v1,v2,v3,v4,v5}, un ciclo será C4={v1,v2,v6,v1} y un circuito es C5 ={v1,v2,v3,v5,v2,v6,v1}.
Tipos de Grafos
1.­ Grafos Planares: se dice que un grafo G es planar si se puede dibujar en el plano sin que los lados se crucen fuera de sus extremos.
Figura 7: Grafo Planar
2.­ Grafos Conexos: decimos que un vértice u de un grafo es accesible (o alcanzable) desde otro vértice v si existe un camino de u a v.
Un grafo no dirigido es conexo si cada par de vértices está conectado por un camino (es decir, todos los vértices son mutuamente accesibles). Las componentes conexas de un grafo son las clases de equivalencia de los vértices bajo la relación de accesibilidad. El grafo de la figura anterior es conexo ya que cada par de vértices están conectados por un camino. Sin embargo, el siguiente grafo no es conexo y tiene dos componentes conexas. Esto se debe a que, por ejemplo, al vértice 3 no se puede acceder desde el vértice 1.
Figura 8: Grafo no conexo
Unidad III. Grafos
Teoría de grafos 2-2010
Definiciones, representaciones, tipos de grafos y árboles
UNEFA-Núcleo Mérida
En una componente conexa, todos los vértices son mutuamente accesibles; es evidente, por tanto, que un grafo es conexo si y solamente si tiene una única componente conexa. Intuitivamente, las componentes son los diferentes “trozos” conexos en que el grafo se descompone.
En conclusión, Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une. Un grafo dirigido es fuertemente conexo si cualquier vértice es accesible desde cualquier otro.
3.­ Grafo Completo: de orden n, que se denota por Kn, es el grafo que tiene n vértices y cada vértice está unido a los demás por exactamente una arista. Un grafo completo de n vértices tiene exactamente (n(n­1))/2 aristas.
Figura 9: Grafos Completos
4.­ Grafo Bipartito: sea un grafo G y sea su conjunto de vértices que puede ser expresado como la unión disjunta de dos subconjuntos de vértices V1 y V2 de forma que cada arista de G une un vértice de V1 con otro de V2, entonces se dice que G es un grafo bipartito. Se cumple que V1∩V2=0, V1UV2=V. Un grafo bipartito en el cual todos los elementos de V1 están unidos con todos los elementos de V2 se denomina grafo bipartito completo.
Figura 10: Grafo Bipartito
Unidad III. Grafos
Teoría de grafos 2-2010
Definiciones, representaciones, tipos de grafos y árboles
UNEFA-Núcleo Mérida
5.­ Grafo Simple: se denomina grafo simple al grafo G= {V, E} que verifica que para todo u,v que pertenece a V, existe a lo sumo una única arista {u,v} de E que los une. En caso contrario se llama multígrafo. El grafo de la derecha es un grafo simple y el grafo de la izquierda es un multígrafo.
Figura 11: Grafo Simple
6.­ Grafo Nulo: se denomina grafo nulo a un grafo donde E es vacío, es decir; el conjunto de aristas es el conjunto vacío. Obviamente en este tipo de grafo todo vértice es aislado.
Figura 12: Grafo Nulo
7.­ Subgrafo: un subgrafo de un grafo G es un grafo formado por un subconjunto de vértices de G y todas las aristas de G que los unen.
Figura 13: Subgrafo
8.­ Grafo Regular: se llama grafo regular a un grafo cuyos vértices tienen todos el mismo grado. Si el grado de cada vértice es r, se tiene un grafo regular de grado r. Todo grafo nulo es un grafo regular de grado 0. Todo grafo completo con n vértices es un grafo regular de grado n – 1.
Figura 3.13: Grafo Regular
Figura 14: Grafo regular
9.­ Pseudografo (dirigido): un pseudografo es un grafo no dirigido (dirigido) que acepta bucles en G.
Figura 15: Pseudografo
Unidad III. Grafos
Teoría de grafos 2-2010
Definiciones, representaciones, tipos de grafos y árboles
UNEFA-Núcleo Mérida
10.­ Grafos Isomorfos (Isomorfismo de grafos): dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.  Si dos grafos G1 y G2 son isomorfos, tienen el mismo número de vértices, el mismo número de aristas, el mismo número de vértices de cualquier grado, el mismo número de ciclos de cualquier longitud, etc.
Propiedad:
Dos grafos simples G1 y G2 son isomorfos si y sólo si para cierto orden de sus vértices las matrices de adyacencia son iguales.
Ejemplos:
1.­ Grafos isomorfos a través de definición de funciones que los hacen isomorfos
Figura 16: Grafos Isomorfos
Un posible Isomorfismo: f (u1) = v1; f (u2) = v4; f (u3) = v3; f (u4) = v2
2.­ Varios grafos isomorfos sin definición de función alguna
Figura 17: Grafos Isomorfos
11.­ Grafos Orientados o dígrafos: se denomina grafo dirigido o dígrafo cuando cada arista tiene un orden en sus extremos. El orden se indica en la gráfica mediante una flecha. Se llama origen al primer vértice de la arista y fin al segundo.
Unidad III. Grafos
Teoría de grafos 2-2010
Definiciones, representaciones, tipos de grafos y árboles
UNEFA-Núcleo Mérida
Figura 18: Dígrafo
12.­ Grafo de Euler: En 1736, Euler resolvió el problema conocido como problema de los puentes de Königsberg, que consiste en lo siguiente:
Dos islas en el río Pregel que cruza Königsberg se unen entre ellas y con la tierra firme mediante siete puentes. Se planteó la posibilidad de dar un paseo empezando por una cualquiera de las cuatro partes de tierra firme, cruzando cada puente una sola vez y volviendo al punto de partida. Fue resuelto por el matemático Leonhard Euler en 1736. Además, dió una caracterización general.
Figura 19: Puentes de Königsberg
Los puentes de Königsberg de manera gráfica y mediante un grafo es la siguiente:
Figura 20: Grafo Puentes de Königsberg
Sea G un grafo no dirigido. Denominamos recorrido euleriano de G a un camino que pasa por todas las aristas de G apareciendo cada una de ellas exactamente una vez. Si, además, el recorrido es cerrado, se denomina que hay un circuito euleriano y el grafo es euleriano. El grafo correspondiente a los puentes de Königsberg no es un grafo euleriano (no todos los vértices tienen grado par). Un grafo euleriano está caracterizado por la paridad de los grados de los vértices de la siguiente manera:
• Un grafo conexo es euleriano si y solo si cada vértice tiene grado par.
• Todo grafo conexo cuyos vértices son de grado par es un grafo euleriano.
Un grafo (digrafo) euleriano es aquel en que pueden recorrerse todas sus aristas (arcos) de manera consecutiva y sin repetirlas.
Unidad III. Grafos
Teoría de grafos 2-2010
Definiciones, representaciones, tipos de grafos y árboles
UNEFA-Núcleo Mérida
13.­ Multígrafo: un multígrafo (no dirigido) G es un par G = (V;A) donde V es un conjunto no vacío de vértices y A es un conjunto de aristas que se identifican con conjuntos de uno o dos vértices. Es decir, para cada arista a Є A existen vértices x; y Є V (no necesariamente distintos) tales que a = {x,y}.
Cola Euleriana: llamaremos cola euleriana en un multígrafo a una cola (trayectoria sin aristas repetidas) que recorra todas las aristas del multígrafo. Si la cola euleriana es cerrada la llamaremos circuito euleriano.
Algoritmo de Fleury Si un multígrafo (V,A) tiene una cola euleriana C, puede construirse mediante el siguiente algoritmo:
1.­ Empezar en un vértice x de grado impar. Si no lo hay, empezar en cualquier vértice x. Hacer C=x.
2.­ Si gr(x)=0 parar, donde gr es el grado del vértice.
3.­ Si gr(x)=1 con a={x,y}, tomar (V,A)=(V−{x},A−{a}), hacer C=Cay y continuar en 5.
4.­ Si gr(x)>1 elegir una arista a={x,y}, cuya eliminación no desconecte el multígrafo. Tomar (V,A)=(V,A−{a}) y hacer C=Cay.
5.­ Reemplazar x por y y volver a 2.
14.­ Grafos de Hamilton: Sea G un grafo (dirigido o no). Un camino simple en G se dice que es hamiltoniano si el camino pasa por cada vértices del grafo exactamente una vez. Un ciclo que pasa exactamente una vez por cada vértice (excepto el vértice inicial, que aparece también como final), se denomina ciclo hamiltoniano. Un grafo que contiene un ciclo hamiltoniano se dice que es un grafo hamiltoniano.
Ejemplo: W.R. Hamilton (1805­1865) inventó (y patentó) un juego en el que se trataba de hacer un recorrido por 20 ciudades del mundo sin pasar por ninguna más de una vez. Las ciudades estaban unidas por 30 aristas, formando el grafo de un icosaedro. Es decir, se trataba de construir un camino Hamiltoniano en el grafo del dodecaedro.
Unidad III. Grafos
Teoría de grafos 2-2010
Definiciones, representaciones, tipos de grafos y árboles
UNEFA-Núcleo Mérida
Figura 21: Juego Hamilton
El dodecaedro es hamiltoniano; el grafo de Herschel no es hamiltoniano porque es bipartito y tienen un número impar de vertices.
Figura 22: a) dodecaedro. b) grafo de Herschel
Árboles
El concepto general de árbol implica una estructura en la que los datos se organizan de modo que los elementos de información están relacionados entre sí a través de ramas. El árbol genealógico es el ejemplo típico más representativo del concepto de árbol general.
Definición 1: un árbol es un grafo no dirigido conexo sin ciclos. Un bosque es un grafo no dirigido sin ciclos pero no conexo. Una definición equivalente es que un bosque es una unión disjunta de árboles (de aquí el nombre). Un árbol a veces recibe el nombre de árbol libre.
Unidad III. Grafos
Teoría de grafos 2-2010
Definiciones, representaciones, tipos de grafos y árboles
UNEFA-Núcleo Mérida
Figura 23: Grafo. Bosque. Árbol
Definición 2: un árbol consta de un conjunto finito de elementos, llamados nodos y un conjunto finito de líneas dirigidas llamadas ramas que conectan los nodos. Definición 3: n árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.
Ejemplo:
Figura 24: Árbol con nodos y ramas
Algunas definiciones dentro de los árboles:
Figura 25: Árbol con nodos y ramas
En cuanto a los nodos:
● Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'.
Unidad III. Grafos
Teoría de grafos 2-2010
●
●
Definiciones, representaciones, tipos de grafos y árboles
UNEFA-Núcleo Mérida
Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.
Los árboles con los que trabajaremos tienen otra característica importante: cada nodo sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto hace que estos árboles estén fuertemente jerarquizados, y es lo que en realidad les da la apariencia de árboles.
En cuanto a la posición dentro del árbol:
● Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'.
● Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.
● Nodo rama: son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.
Características del árbol, en relación a su tamaño:
● Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc.
● Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol de la Figura 25, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos.
● Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el árbol de la Figura 25, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3.
● Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.
Propiedades de los Árboles
Algunas de las propiedades características de los árboles son las siguientes:
Teorema: sea G=(V,E) un grafo con n vértices. Los siguientes enunciados son equivalentes:
1.­ G es un árbol.
2.­ Dos vértices cualesquiera de G están conectados por un único camino simple (Dados dos nodos cualesquiera de un árbol, existe exactamente un camino que los conecta.)
3.­ G es conexo y si se suprime una arista deja de serlo.
4.­ G es conexo y E=V−1 (un árbol con N nodos tiene N­1 aristas)
Unidad III. Grafos
Teoría de grafos 2-2010
Definiciones, representaciones, tipos de grafos y árboles
UNEFA-Núcleo Mérida
Árboles Generadores
Un árbol T es un árbol generador de un grafo G si T es un subgrafo de G que contiene todos los vértices de G. Un grafo puede tener varios árboles generadores.
Figura 26: Grafo
Problema: se desea determinar que rutas pueden ser cerradas de tal manera que se pueda seguir viajando entre cualquier par de ciudades.
Un árbol generador para el problema original es el siguiente:
Figura 27: Árbol generador
Los algoritmos más usados para construir arboles generadores son: búsqueda en profundidad y búsqueda en amplitud, los cuales se enuncian a continuación:
1.­ Algoritmo búsqueda en profundidad
En la búsqueda en profundidad se avanza de vértice en vértice, marcando cada vértice visitado. La búsqueda siempre avanza hacia un vértice no marcado, internándose “profundamente” en el grafo sin repetir ningún vértice. Cuando se alcanza un vértice cuyos vecinos han sido marcados, se retrocede al anterior vértice visitado y se avanza desde éste.
Sea G(V, E) un grafo conexo y v un vértice de V. El algoritmo de búsqueda en profundidad puede detallarse de la siguiente manera:
1.­ Se comienza en un vértice v (vértice activo) y se toma como la raíz del árbol generador T que se construirá. Se marca el vértice v.
2.­ Se elige un vértice u, no marcado, entre los vecinos del vértice activo. Si no existe tal vértice, ir a 4.
Unidad III. Grafos
Teoría de grafos 2-2010
Definiciones, representaciones, tipos de grafos y árboles
UNEFA-Núcleo Mérida
3.­ Se añade la arista (v,u) al árbol T. Se marca el vértice u y se toma como activo. Ir al paso 2.
4.­ Si se han alcanzado todos los vértices de G el algoritmo termina. En caso contrario, se toma el vértice padre del vértice activo como nuevo vértice activo y se vuelve al paso 2.
2.­ Algoritmo búsqueda en anchura (amplitud)
La búsqueda en anchura es otro procedimiento para visitar sistemáticamente todos los vértices de un grafo. Es adecuado especialmente para resolver problemas de optimización, en los que se deba elegir la mejor solución entre varias posibles. Al igual que en la búsqueda en profundidad se comienza en un vértice v (la raíz) que es el primer vértice activo. En el siguiente paso se etiquetan como visitados todos los vecinos del vértice activo que no han sido etiquetados. Se continúa etiquetando todos los vecinos de los hijos de v (que no hayan sido visitados aún). En este proceso nunca se visita un vértice dos veces por lo que se construye un grafo sin ciclos, que será un árbol generador de la componente conexa que contiene a v.
Sea G(V, E) un grafo conexo y v un vértice de V. El algoritmo de búsqueda en anchura puede detallarse de la siguiente manera:
1.­ Designamos a v como vértice activo y como raíz del árbol generador T que se construirá. Se le asigna a v la etiqueta 0.
2.­ Sea i=0 y S={v}.
3.­ Hallar el conjunto M de todos los vértices no etiquetados que son adyacentes a algún vértice de S.
4.­ Si M es vacío el algoritmo termina. En caso contrario, se etiquetan todos los vértices de M con i+1, se añaden a T las aristas entre cada vértice de S y su vecino en M y se hace S=M.
5.­ i=i+1 y volver al paso 3.
Árboles Generadores Minimales
Un árbol generador mínimo de un grafo ponderado es un árbol generador tal que la suma de los pesos de sus aristas es la mínima posible de entre todos los árboles generadores.
Se parte de un grafo ponderado (con peso) con n vértices. La idea es construir un subgrafo que una a todos los puntos pero con el mínimo de peso (el peso se refiere al valor que se le da a cada uno de los lados de un grafo). Este subgrafo debe ser un árbol generador, ya que debe unir todos los vértices, debe ser conexo y debe haber un único camino entre cada par de vértices, por lo tanto, lo que se necesita es un árbol generador con el mínimo de peso, es a esto lo que se llama árbol generador minimal.
Ejemplo:
Sea el grafo G que se muestra a continuación, se desea encontrar dos árboles generadores de G y entre ellos escoger el árbol generador minimal.
Unidad III. Grafos
Teoría de grafos 2-2010
Definiciones, representaciones, tipos de grafos y árboles
UNEFA-Núcleo Mérida
Figura 28: Grafo G
Dos árboles generadores del grafo G son los siguientes:
Figura 29: Árbol T1
Figura 30: Árbol T2
Como se dijo previamente los árboles T1 y T2 son árboles generadores de G, sin embargo el peso de ambos es distinto (T1=32 y T2=41). Por lo tanto el árbol Generador Minimal de G es T1.
Unidad III. Grafos
Teoría de grafos 2-2010
Definiciones, representaciones, tipos de grafos y árboles
UNEFA-Núcleo Mérida
Ejercicio:
Figura 30: Grafo Ponderado
¿Qué aristas deberían mantenerse, para asegurar que hay un camino entre cualquier par de ciudades y el costo total sea el menor posible?
Existen dos algoritmos voraces para encontrar árboles generadores mínimos:
• Algoritmo de Prim
• Algoritmo de Kruskal
1.­ Algoritmo de Prim
Este algoritmo fué propuesto por Robert Prim en 1957. La idea del algoritmo es la siguiente:
• Ordenar arcos de menor a mayor.
• Insertar la menor arista a partir del nodo dado.
• Recorrer la lista de menor a mayor e ir insertando aquellas aristas que sean incidentes con un vértice que ya está en el árbol y se evalúa la condición de que no se formen ciclos con las que ya han sido incorporadas.
• El algoritmo se detiene cuando se han añadido n­1 aristas.
2.­ Algoritmo de Kruskal
Este algoritmo fue descubierto por Joseph Kruskal en 1956. Los pasos que se deben seguir para construir un árbol generador minimal a partir del algoritmo de Kruskal son los siguientes:
• Ordenar arcos de menor a mayor.
• Añadir sucesivamente aristas de peso mínimo que no forme ciclos con las que ya han sido incorporadas.
• El algoritmo se detiene cuando se han añadido n­1 aristas.