Grafos - Parte 3

Vista previa del material en texto

Algoritmos y Estructuras de 
Datos
Departamento de Informática
LAS - TUP
Unidad N° 6: Grafos - Parte III
Sobre Camino más corto
Obtuvimos las distancias.
 ¿Los caminos?
S = {1, 6, 2, 5, 3, 4} π = (0, 4, 7, 8, 5, 3)
Árbol
Es un tipo de grafo particular, que tiene estas características:
● E=V−1 (la cantidad de aristas es uno menos que la cantidad de nodos)
● No tiene ciclos
● Al agregar una arista entre dos nodos no adyacentes, aparece un ciclo
● Al sacar cualquier arista existente, el grafo se desconecta
● Para cada par de nodos existe un único camino simple (que no repite 
vértices)
Árbol cubridor
Sea G=(V,E) un grafo conexo y ponderado, un árbol cubridor o abarcador de G es 
un árbol libre que conecta TODOS los vértices de V con un costo igual a la suma 
de los costos (de las aristas) del árbol obtenido.
Árbol cubridor
Un grafo y un árbol cubridor
El costo del árbol es 3+5+1+4+2=15. 
Árbol cubridor
Un grafo y un árbol cubridor
El costo del árbol es 3+5+1+4+2=15. 
Otro árbol puede ser (1,4),(4,3),(3,2),(2,5),(5,6) y su costo será 5+5+5+3+6=24.
Árbol mínimo - Aplicaciones
Diseño de redes: redes telefónicas, eléctricas, hidráulicas, informática, rutas, etc.
.
Árbol mínimo
Es un árbol de costo mínimo. El árbol de la figura es de costo mínimo.
A continuación, veremos dos algoritmos que obtienen un árbol de costo mínimo 
(Minimum Spanning Tree Problem).
.
Algoritmo de Prim
El algoritmo fue diseñado por el científico computacional Robert C. Prim en 1957.
Sea G=(V,E) un grafo conexo y ponderado,V={1,2,. . . , n}, el conjunto de vértices 
y E={1,2,. . . , m} el conjunto de aristas, el algoritmo de Prim es el siguiente:
Inicialmente, se asigna un vértice de V a un conjunto U.
En cada iteración, se busca la arista (u,v) de menor costo que conecta un 
vértice de U con otro de V-U. 
Luego, se agrega el vértice v al conjunto U
La arista (u,v) formará parte del árbol mínimo).
El proceso se repite hasta que U=V.
Algoritmo de Prim
1 2 3 4 5 6
1 - 6 1 5 - -
2 6 - 5 - 3 -
3 1 5 - 5 6 4
4 5 - 5 - - 2
5 - 3 6 - - 6
6 - - 4 2 6 -
T v V U V-U
∅ - {1,2,3,4,5,6} {1} {2,3,4,5,6}
Algoritmo de Prim
1 2 3 4 5 6
1 - 6 1 5 - -
2 6 - 5 - 3 -
3 1 5 - 5 6 4
4 5 - 5 - - 2
5 - 3 6 - - 6
6 - - 4 2 6 -
T v V U V-U
∅ - {1,2,3,4,5,6} {1} {2,3,4,5,6}
{(1,3)} 3 {1,2,3,4,5,6} {1,3} {2,4,5,6}
Algoritmo de Prim
1 2 3 4 5 6
1 - 6 1 5 - -
2 6 - 5 - 3 -
3 1 5 - 5 6 4
4 5 - 5 - - 2
5 - 3 6 - - 6
6 - - 4 2 6 -
T v V U V-U
∅ - {1,2,3,4,5,6} {1} {2,3,4,5,6}
{(1,3)} 3 {1,2,3,4,5,6} {1,3} {2,4,5,6}
{(1,3),(3,6)} 6 {1,2,3,4,5,6} {1,3,6} {2,4,5}
Algoritmo de Prim
1 2 3 4 5 6
1 - 6 1 5 - -
2 6 - 5 - 3 -
3 1 5 - 5 6 4
4 5 - 5 - - 2
5 - 3 6 - - 6
6 - - 4 2 6 -
T v V U V-U
∅ - {1,2,3,4,5,6} {1} {2,3,4,5,6}
{(1,3)} 3 {1,2,3,4,5,6} {1,3} {2,4,5,6}
{(1,3),(3,6)} 6 {1,2,3,4,5,6} {1,3,6} {2,4,5}
{(1,3),(3,6),(6,4)} 4 {1,2,3,4,5,6} {1,3,4,6} {2,5}
Algoritmo de Prim
1 2 3 4 5 6
1 - 6 1 5 - -
2 6 - 5 - 3 -
3 1 5 - 5 6 4
4 5 - 5 - - 2
5 - 3 6 - - 6
6 - - 4 2 6 -
T v V U V-U
∅ - {1,2,3,4,5,6} {1} {2,3,4,5,6}
{(1,3)} 3 {1,2,3,4,5,6} {1,3} {2,4,5,6}
{(1,3),(3,6)} 6 {1,2,3,4,5,6} {1,3,6} {2,4,5}
{(1,3),(3,6),(6,4)} 4 {1,2,3,4,5,6} {1,3,4,6} {2,5}
{(1,3),(3,6),(6,4),(3,2)} 2 {1,2,3,4,5,6} {1,2,3,4,6} {5}
Algoritmo de Prim
1 2 3 4 5 6
1 - 6 1 5 - -
2 6 - 5 - 3 -
3 1 5 - 5 6 4
4 5 - 5 - - 2
5 - 3 6 - - 6
6 - - 4 2 6 -
T v V U V-U
∅ - {1,2,3,4,5,6} {1} {2,3,4,5,6}
{(1,3)} 3 {1,2,3,4,5,6} {1,3} {2,4,5,6}
{(1,3),(3,6)} 6 {1,2,3,4,5,6} {1,3,6} {2,4,5}
{(1,3),(3,6),(6,4)} 4 {1,2,3,4,5,6} {1,3,4,6} {2,5}
{(1,3),(3,6),(6,4),(3,2)} 2 {1,2,3,4,5,6} {1,2,3,4,6} {5}
{(1,3),(3,6),(6,4),(3,2),(2,5)} 5 {1,2,3,4,5,6} {1,2,3,4,5,6} {}
Algoritmo de Prim
Prim()
{u,v son de tipoVertice, U y T de tipoConjunto y grafo de tipoGrafo}
T={} //Conjunto de aristas
U={1} //Conjunto de vértices. 1 es arbitrario
Mientras U ≠ V
Buscar una arista (u,v) del grafo tal que u ∈ U y v ∈ V-U
T=T+{(u,v)}
U=U+{v}
Algoritmo de Kruskal
Otra manera de obtener un árbol a costo mínimo, es mediante este algoritmo.
Idea inicial:
Ordenamos las aristas por su peso
Si agregar e a la solución no genera un ciclo
agrego e a la solución
return solucion
Algoritmo de Kruskal
La idea general es la siguiente: el árbol mínimo se obtiene a partir de la conexión 
de árboles mínimos (que forman un bosque).
Inicialmente, se dispone de n árboles, cada uno de ellos con un vértice v distinto y 
las aristas del grafo G ordenadas por costo.
En cada paso, se toma una arista (u,v) y si los vértices están en árboles distintos, 
ambos son combinados.
Este proceso se repite hasta combinar n-1 árboles.
Algoritmo de Kruskal
Algoritmo de Kruskal
Algoritmo de Kruskal
Algoritmo de Kruskal
Algoritmo de Kruskal
Kruskal()
{u,v son de tipoVertice, arista es de tipoArista, Cola es de tipoColaPrioridad, lista es de 
tipoConjunto, grafo de tipoGrafo}
Crea(Conjunto)
Para v en Vertices(grafo)
Meter(Lista[v], v)
Crea(Cola)
Para arista en Aristas(grafo)
Meter(Cola, arista)
n=orden(grafo)
Mientras n >1
Sacar(Cola,arista)
posu=Busca(Lista,inicio(arista))
posv=Busca(Lista,n(arista))
Si posu ≠ posv entonces
Combina(Lista[posu],Lista[posv],Lista)
n=n-1
Comparación entre los algoritmos de Prim y Kruskal 
Los algoritmos de Prim y Kruskal toman un tiempo de orden O(n²) y O(e log(e)) 
respectivamente (n, e: número de vértices y aristas del grafo, respectivamente). 
Por ésto si el grafo es denso, tiene muchas aristas con respecto a la cantidad de 
vértices (e ≈ n² ó e > n²), es aconsejable utilizar el algoritmo de Prim, de lo 
contrario, cuando la cantidad de aristas sea pequeña con respecto a los vértices 
(e <= n²), es mejor aplicar el algoritmo de Kruskal.
Problema del Viajante
Consideremos el siguiente 
problema: "Dado un conjunto de 
ciudades y conocidas las distancias 
entre dos ciudades cualesquiera, el 
Problema del Viajante (Travelling 
Salesman Problem) consiste en 
encontrar la mejor manera de visitar 
todas las ciudades una sola vez y 
volver a la ciudad inicial".
Problema del Viajante
Problema del Viajante
Problema del Viajante
Problemas de asignación
Apareo de grafos
Un ejemplo del problema de apareo es el siguiente: se dispone de un conjunto de 
profesores y un conjunto de materias a ser dictadas. Cada profesor tiene 
preferencias para dictar ciertas materias.
El problema consiste en asignar a cada materia un profesor adecuado para el 
dictado de clases. 
Es importante mencionar que pueden haber más materias que profesores. Por 
otra parte, consideraremos que una materia es dictada por un (único) profesor y 
que un profesor dicta una sola materia.
Problemas de flujo