estructura de datos grafos6_diapos]_=d.pdf · universidad técnica federico santa maría -...

Universidad Técnica Federico Santa María - Departamento de Informática

Estructura de Datos

Grafos

Prof.: Mauricio Solar Prof.: Lorna Figueroa

Primer Semestre, 2010


Grafos

• Árboles: generalización del concepto de lista, • permiten que un elemento tenga más de un sucesor.

• Grafos: extensión del concepto de árbol, • cada elemento puede tener, además de más de un sucesor,

varios elementos predecesores.• Esta propiedad hace que los grafos sean un TAD adecuado para

representar situaciones de relación arbitraria entre los elementos:• mapas de carreteras, • sistemas de telecomunicaciones, • circuitos impresos,• redes de computadores, etc.


Grafos

• Ampliamente utilizados en computación, ya que permiten resolver problemas complejos.

• Grafo de transiciones (AFD):


Grafos

• Planificación de tareas (Pert/CPM)

• Grafo asociado a un dibujo de líneas (visión artificial)


Grafos

• Tiempos de vuelo entre ciudades


Grafos

• Un grafo G = (V, A) consiste de un conjunto finito o vacío de vértices (o nodos) V y un conjunto de arcos (o aristas) A.

• V es el conjunto de nodos o vértices. • V ={v1, v2, …, vn}

• A es el conjunto de aristas o arcos, que son las conexiones que se encargan de relacionar los nodos para formar el grafo.

• A = { (vi, vk, cik) / vi, vk ∈ V, vi → vk, vi, vk están relacionados con un valor c }


Grafos

• Los vértices suelen usarse para representar información.• Los arcos para representar la relación entre ellos. • Ejemplo:

• vértices representan ciudades• los arcos las carreteras.


Ejemplo

• Red de vuelos de una compañía aérea entre diferentes ciudades, se tiene el grafo G = {V, A}:

V = {Concepción, Temuco, Pucón, Santiago, La Serena, Arica}; A = {(Santiago, Concepción), (Santiago, Temuco), (Santiago,

Pucón), (Santiago, La Serena), (Santiago, Arica)}.

Santiago

La Serena Concepción

Temuco Arica

Pucón


Ejemplo: La red de metro de Santiago

• Los mapas de las líneas del metro de Santiago son grafos que muestran la conectividad de las estaciones.

• Fuente: http://img390.imageshack.us/i/metro20062020ni6rt7.jpg/


Grafos - Clasificación

• Los grafos se pueden clasificar en diferentes tipos dependiendo de cómo se defina la relación entre los elementos:

• grafos dirigidos o no dirigidos• etiquetados o no etiquetados.

• También se pueden combinar ambas categorías.


• Si los arcos son pares ordenados (v, w) ∈ VxV, el grafo es dirigido.

• En un grafo dirigido los arcos tienen un único sentido.

Grafos Dirigidos

a

b c

En el ejemplo,

V = {a,b,c}

A = {(a,b), (a,c), (b,c), (c,a)}


• Un grafo dirigido se puede usar para representar bloques de un programa mediante los nodos y la transferencia del flujo de control mediante los arcos.

• Grafo que representa el sentido del tráfico entre diferentes plazas:

Grafos Dirigidos

Plaza de Armas

Vicuña MackennaConstitución

Brasil Almagro

Yungay


• Si los arcos son pares no ordenados (v, w) ⊆ V, v ≠ w, el grafo es no dirigido.

• En un grafo no dirigido los arcos conectan a los vértices en ambos sentidos.

Grafos No Dirigidos

a

b c

En el ejemplo,

V = {a,b,c}

A = {(a,b), (a,c), (b,a), (b,c), (c,a), (c,b)}


• En ciertas aplicaciones es necesario asociar información a los arcos.

• Esto se logra agregando una etiqueta que contenga cualquier información útil relativa al arco: • nombre, peso, costo o un valor de cualquier tipo de datos

dado.• Esta etiqueta puede representar el tiempo de vuelo entre dos

ciudades o indicar cuáles son los parámetros de entrada y de salida en la llamada a un subprograma.

Grafos Etiquetados


Grafos Etiquetados

En el ejemplo,

V = {a,b,c,d}

A ={(a,b,8),(a,c,3),(a,d,5),(b,a,8),(b,c,1),(c,a,3),(c,b,1),(d,a,5)}

a

bc

d

3

5

8

1


• En un grafo no etiquetado los arcos no tienen etiquetas.• En el caso de un grafo que representa el sentido del tráfico

se pueden etiquetar los arcos con el nombre de las calles.

Grafos no Etiquetados


Definiciones

• Dos vértices son adyacentes o vecinos si hay un arco que los conecta.

• Los nodos adyacentes pueden ser representados por pares (a, b).

c

ad

b

a es adyacente con b, c, db es adyacente con a y cc es adyacente con a y bd es adyacente con a

A = {{a,b}, {a,c}, {a,d}, {b,a}, {b,c}, {c,a}, {c,b}, {d,a}}


Definiciones

• Camino: secuencia de nodos n1, n2, ..., nm tal que ∀i, 1≤i≤(m-1), cada par de nodos (ni, ni+1) son adyacentes.

• Camino cerrado: si el primer y último vértice de la sucesión de vértices son el mismo.

• Camino simple: cada uno de sus nodos, excepto el primero y el último, aparece sólo una vez en la secuencia.

• Longitud de un camino: número de arcos de ese camino.• Un camino es de largo n-1, n = nº de nodos.

• Costo de un camino: la suma de los valores asociados con los arcos que lo componen.


Camino(a,c) =

Largo del camino(a,d) =

Camino simple =

Costo(a,c) =

a

bc

d

3

5

8

1

Definiciones


Camino(a,c) = { {a,c} }; {{a,b}, {b, c} } }

Largo del camino(a,d) =

Camino simple =

Costo(a,c) =

a

bc

d

3

5

8

1

Definiciones


Camino(a,c) = { {a,c} }; {{a,b}, {b, c} } }

Largo del camino(a,d) = 1

Camino simple =

Costo(a,c) =

a

bc

d

3

5

8

1

Definiciones


Camino(a,c) = { {a,c} }; {{a,b}, {b, c} } }


Camino simple = {a,b}

Costo(a,c) =

a

bc

d

3

5

8

1

Definiciones


Camino(a,c) = { {a,c} }; {{a,b}, {b, c} } }


Camino simple = {a,b}

Costo(a,c) = 3 o 9

a

bc

d

3

5

8

1

Definiciones


• En los caminos se permite la repetición de aristas, b-a-b-e-f-a-a-b es un camino.

• La longitud del camino b-a-b-e-f-a-a-bes la cantidad de aristas que tiene: 8

• El número de elementos de V es el orden del grafo G, • En el ejemplo, el orden es 4.

Definiciones


• Las aristas adyacentes en un camino tienen un vértice común. • Por lo tanto, un camino determina una sucesión de vértices.

Definiciones


• Ciclo: camino simple en el que el primer y último nodo es el mismo (n1 = nm).

• Un grafo sin ciclos se dice acíclico.

Definiciones


El problema de los puentes de Königsberg


• Esta ciudad esta recorrida por el río Pregel que crea dos islas. ¿Se puede recorrer toda la ciudad pasando una sola vez por todos y cada uno de los 7 puentes que unen la parte insular de la ciudad con el resto?



• En 1736 el matemático suizo Leonhard Euler resolvió el problema. Abstrajo los detalles de la forma de la ciudad y sus puentes para quedarse con la conectividad.

• El orden de todos los vértices es impar, lo que implica que es imposible recorrerlos pasando una sola vez por cada uno.

• Construyó el grafo reemplazando la tierra firme por vértices y los puentes por aristas; es decir Tierra 1 es el vértice a, Tierra 2 es b, la Isla 1 es el vértice c y la Isla 2 es el vértice d.



• La pregunta es: ¿existe un camino cerrado que contenga exactamente cada una de las aristas?

• Este camino se llama circuito de Euler o euleriano. • Un camino simple que contiene todas las aristas de un grafo G

se llama camino euleriano de G, • o de otra manera se dice que un grafo conexo no vacío es

un camino Euleriano si y solo si no tiene vértices de grado impar.

• Un camino euleriano cerrado se llama circuito euleriano.

Definiciones


• Un camino euleriano en un grafo es un camino que contiene a todas las aristas del grafo exactamente una vez.

• Un grafo es euleriano si contiene un camino euleriano cerrado. • Intuitivamente un camino es Euleriano si se puede recorrer el

grafo de un solo trazo sin levantar el lápiz del papel.

Definiciones


• La valencia de un vértice en un grafo es el número de aristas que confluyen en él.

• Teorema 1: En un grafo que tiene un circuito euleriano todos los vértices deben tener valencia par.

• Corolario 1: Un grafo que tenga un camino euleriano tiene 2 vértices de valencia impar, o no tiene vértices de valencia impar.

Definiciones


• Este grafo no tiene circuito euleriano ya que aunque u y vtienen valencia impar, pero b-a-c-d-g-f-e es un camino euleriano

Definiciones


• En este grafo todos los vértices tienen valencia par y de hecho hay un circuito euleriano.

Definiciones


• En este grafo todos los vértices tienen valencia par pero no hay un circuito euleriano,

• la razón obvia es que está formada por dos subgrafos que no están conectados entre sí.

• Sin embargo, cada uno de los subgrafos tiene su propio circuito euleriano.

Definiciones


• Camino hamiltoniano: sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez, (salvo v0 = vn, si el camino es cerrado).

• Ciclo hamiltoniano: camino hamiltoniano en que el último vértice visitado es adyacente al primero.

• Un grafo es hamiltoniano si tiene un ciclo hamiltoniano. • Un ciclo es hamiltoniano si pasa por todos los vértices solo una

vez.

Definiciones


• Grafo Hamiltoniano del dodecaedro:

Definiciones

• Grafo no hamiltoniano de Herschel:


Definiciones

• Grafo desconectado o inconexo: si en un grafo G = {V,A}, V estáformado por dos o más subconjuntos disjuntos de nodos (no hay arcos que conecten nodos de un subconjunto con nodos de otro subconjunto):

• Grafo es conectado o conexo si:• todos los pares de vértices distintos están

conectados por un camino en el grafo.


Definiciones

grafo desconectado o inconexo :1

2

3

5 6

41

3

5 6

2

4

grafo conectado o conexo :


• El grado de un vértice es el número de vértices adyacentes a él.

c

ad

b

Definiciones

grado (a) = 2

grado (b) = 2

grado (c) = 1

grado (d) = 1


• Un subgrafo G’ = (V’, A’) de un grafo G=(V,A) es un grafo tal que V’ ⊆ V, A’ ⊆ A.

• Ejemplo: si un grafo representa las ciudades y las carreteras de un país, un subgrafo es el grafo de las carreteras de una comuna.

Definiciones


a b c d

a 0 1 1 1b 0 0 0 0c 1 0 0 0d 1 1 1 0

Representaciones para Grafos

• Matriz de Adyacencia. Es una matriz A de ||V|| • ||V|| tal que,

1 si vj es adyacente a vi

A[ i, j ] =0 en caso contrario

Ejemplo :

ab

c d


• Lista de Adyacencia de un vértice v, es la lista de todos los vértices adyacentes a él.

Ejemplo:

a c dbbc ad b ca

ab

c d

Representaciones para Grafos


Recorridos

a

d

b cSe corre el peligro de quedarse en el ciclo a-b-c.

Solución: marcar los vértices por donde se va pasando.

• Muchos algoritmos de recorridos se implementan recursivamente• Surge un problema de control de la recursión, debido a que los

ciclos de un grafo pueden generar llamadas recursivas infinitas.• Ejemplo: Se desea ir desde el vértice a, al vértice d.

• Es necesario recordar los puntos por los cuales ya se ha pasado para evitar hacer nuevamente una llamada recursiva desde ese punto.


• Recorrer un grafo consiste en pasar una vez por cada vértice de la estructura.

• Existen varias maneras de realizar este proceso:• Recorrido en profundidad. (Es equivalente a un recorrido

en preorden de un árbol)• Recorrido por amplitud. (Es equivalente a recorrer un

árbol por niveles)

Recorridos


• Se procesa un nodo inicial n. • Después se procesa uno de los nodos adyacentes que no haya

sido previamente visitado iniciando un recorrido en profundidad desde él.

• Cuando se alcanza un nodo cuyos nodos adyacentes han sido todos visitados el algoritmo vuelve atrás al último nodo visitado al que le quede aún algún sucesor por procesar.

• Finalmente, se llega a un punto donde todos los nodos alcanzables habrán sido visitados.

Recorrido en Profundidad

Un nodo N se dice alcanzable desde un nodo M si y sólo si existe un camino desde M hasta N.


Recorridos en Profundidad - Ejemplo

• Recorrer todos los vértices del siguiente grafo:

a

d

c b

e

• Visitar el nodo a, marcar• Recorrido : a

a

d

c b

e



a

d

c b

e

• Localizar sucesores de a: b y c• Recorrido en profundidad del vértice

b, marcarlo.• Recorrido : a – b• Pendientes : c

a

d

c b

e

• Localizar sucesores de b: d y e• Recorrido en profundidad del vértice d,

marcarlo.• Recorrido : a – b - d• Pendientes : c, e



a

d

c b

e

• Localizar sucesores de d: no tiene• Se saca de la pila de pendientes: e• Recorrido en profundidad del vértice e,

marcarlo.• Recorrido : a – b – d - e• Pendientes : c

a

d

c b

e

• Localizar sucesores de c: b• Como el sucesor del vértice está

marcado y no existen pendientes finaliza el recorrido.

• Luego, el recorrido del grafo es: a – b – d – e – c


Recorrido en Profundidad - Algoritmo

Algoritmo PrimeroEnProfundidad(G: Grafo; n: Elemento) {Marcar n como visitado;MIENTRAS quede algún nodo m adyacente a n sin visitar

PrimeroEnProfundidad(G, m);}


Ejemplo

• Suponiendo que el orden en que están almacenados los nodos en la estructura de datos correspondiente es A-B-C-D-E-F... (el orden alfabético), el orden que seguiría el recorrido en profundidad es:

A-B-E-I-F-C-G-J-K-H-D• Se exploran primero los verdes y luego

los marrones, pasando primero por los de mayor intensidad de color.

• El nodo D es el último en explorarse en la búsqueda en profundidad pese a ser adyacente al nodo de origen (el A).• Esto es debido a que primero se

explora la rama del nodo C, que también conduce al nodo D.


• Similar al recorrido por niveles de un árbol, si se considera como un nivel el conjunto de los nodos adyacentes.

• En este recorrido, tras visitar un nodo, se visitan todos sus nodos adyacentes.

• Una vez visitados todos los nodos de este primer nivel, se repite el proceso visitando todos los nodos adyacentes del primer vecino de nivel recién recorrido y repitiéndolo para todos los nodos hasta que no quede ninguno por visitar.

Recorrido en Amplitud


Ejemplo

• Para el grafo del ejemplo, el orden del recorrido en amplitud es:A-B-C-D-E-G-H-I-J-K-F

• Se exploran primero los verdes, después los rojos, los naranjas y, por último, el rosa.


• En un grafo es habitual encontrar caminos redundantes. • Es decir, es posible llegar de un nodo a otro a través de

diferentes caminos. • Si en un grafo conexo se eliminan los caminos redundantes,

seguirá siendo conexo, • se podrá llegar de cualquier nodo a cualquier otro.

Árboles de extensión de costo mínimo


• Dado un grafo G = (V, A), conexo con los arcos etiquetados con su costo, un árbol de extensión asociado a G es un árbol libre que conecta todos los vértices de V.

• El costo del árbol es la suma de los costos de todos los arcos del árbol libre.


un árbol libre es un grafo conexo acíclico no dirigido.


• Aplicación típica: diseño de una red de comunicaciones (telefónica o de Internet, por ejemplo).

• El árbol de extensión de costo mínimo da la opción de conexión de todas las ciudades al menor costo, ya sea éste el precio del tendido de los cables, el mantenimiento, etc.



• Grafo etiquetado y su árbol de expansión de costo mínimo:



• La representación del árbol de expansión no es única.• Cada árbol abarcador muestra una manera de planear las rutas de

transporte de tal forma que cada ciudad pueda ser atendida.• Ejemplo 1: Costo 6845 millas



• Ejemplo 2: Costo 6567 millas



• Ejemplo 3: Arbol de expansión mínima. Costo 5479 millas.



• Algoritmo de tipo "voraz" o "greedy”. • Construir un árbol generador de peso mínimo

• Estrategia: añadir aristas de mínimo peso hasta conseguir un árbol generador

• En cada paso, al incorporar una nueva arista, se debe comprobar que no se forme ningún ciclo con las aristas previamente introducidas• no están permitidos en un árbol de expansión.

• Cuando todos los subgrafos estén unidos, se habrá encontrado el árbol de expansión de costo mínimo.

El algoritmo de Kruskal


• Para añadir los arcos se examina el conjunto de arcos en orden creciente según su costo.

• Si el arco inspeccionado conecta dos nodos de subgrafos diferentes, se añade al conjunto de nodos,• formará parte del árbol de extensión considerándolos como

un subgrafo conexo. • Si los dos nodos pertenecen al mismo subgrafo, no se añade

para evitar la aparición de ciclos en el árbol de extensión.• Cuando todos los nodos estén conectados, se habrá encontrado

el árbol de extensión buscado.



• Paso 1. Se elige la arista de mínimo peso e y se considera S= {e}.

• Paso 2. Sea e' la arista de peso mínimo tal que e' no pertenezca a S y S+e' es un grafo acíclico. Se hace S=S+e’.

• Paso 3. Si S tiene n-1 aristas, el algoritmo termina. En caso contrario se vuelve al paso 2.



Secuencia de aristas añadidas por el algoritmo de Kruskal.

El algoritmo de Kruskal – Ejemplo

S = {2} S = {2,3} S = {2,3,4}


Secuencia de aristas añadidas por el algoritmo de Kruskal.


S = {2,3,4,5} S = {2,3,4,5,6}


• Fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. • Por esta razón, el algoritmo es también conocido como

algoritmo DJP o algoritmo de Jarnik.

El algoritmo de Prim


• Encuentra un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.

• Idea básica: añadir, en cada paso, un nuevo vértice a un árbol previamente construido. Este nuevo vértice se une al árbol anterior con la arista de menor peso:• 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.

• Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman ese grafo no conexo.



• Suponga un grafo G = (V, A), con los arcos etiquetados con su costo.

• El algoritmo de Prim va construyendo un subconjunto de nodos U, aumentándolo hasta que contenga todos los nodos de V.

• Inicialmente, U contiene un único nodo de V, que puede ser cualquiera.

• En cada paso, se localiza el arco más corto (u, n) tal que u ∈ U y n ∈ V, repitiendo el proceso hasta que U = V.



Algoritmo Prim(Grafo G; Conjunto_de_Arcos *T) {Conjunto_de_arcos U;arcos u, v;T = {};U = {Cualquier v ∈ V};MIENTRAS U <> V {

Sea (u, v) el arco de costo mínimo tal que u ∈ U y v ∈ VT = T ∪ {(u, v)}U = U ∪ {v}

}}



Secuencia de aristas añadidas por el algoritmo de Prim.

El algoritmo de Prim – Ejemplo


Secuencia de aristas añadidas por el algoritmo de Prim.



• Problema: Determinar el costo del camino más corto del origen a todos los demás vértices de V, donde la longitud de un camino es la suma de los costos de los arcos del camino.

• Solución : Algoritmo de Dijkstra. • Este es un algoritmo iterativo, para encontrar los caminos

de costo mínimo que parten de un vértice dado y terminan en cada uno de los demás vértices del grafo.

Algoritmo de Dijkstra


Ejemplo: para el siguiente grafo, encontrar el camino de costo mínimo, que lleva del vértice 1 a todos los demás vértices.

1

2

3

4

5

95

60

20

10

30

50

10



1

2

3

4

5

95

60

20

10

30

50

10 1 2 3 4 50 10 30 95

Se anotan los costos de ir desde el nodo 1 a sus nodos adyacentes :

1 2 3 4 50 10 30 95

Se escoge el que tiene el costo menor, y se marca :



1

2

3

4

5

95

60

20

10

30

50

10

1 2 3 4 50 10 60 30 95

Se anotan los costos de ir desde el nodo 1 pasando por el vértice 2 a los nodos adyacentes (al 2) :

1 2 3 4 50 10 60 30 95


Costo(1-2-3) = 10 + 50 = 60



1

2

3

4

5

95

60

20

10

30

50

10

1 2 3 4 50 10 50 30 90

Se anotan los costos de ir desde el nodo 1 pasando por el vértice 4 a los nodos adyacentes (al 4); en caso que tenga un costo menor, se reemplaza :

1 2 3 4 50 10 50 30 90


Costo(1-4-3) = 30 + 20 = 50

Costo(1-4-5) = 30 + 60 = 90



1

2

3

4

5

95

60

20

10

30

50

10

1 2 3 4 50 10 50 30 60

Se anotan los costos de ir desde el nodo 1 pasando por el vértice 3 a los nodos adyacentes (al 3); en caso que tenga un costo menor, se reemplaza :

Dado que ya se han visitado todos los nodos, se termina el recorrido de Dijkstra.

Costo(1-2-3-5) = 10+50+10=70

Costo(1-4-3-5)=30+20+10=60



• G = (V, E)• V = {1, 2, ..., n}• origen = 1• S = conjunto de vértices cuya distancia más corta desde el

origen ya es conocida• C = arreglo bidimensional de costos• C[ i, j ] = costo de ir del vértice vi al vértice vj por el arco i j• D[ i ] = longitud del camino especial más corto actual para vi

• camino especial = camino más corto entre el origen y v que pasa sólo a través de los vértices de S

• D = contendrá la distancia más corta del origen a cada vértice



Dijkstra( ){ S = { 1 } ;

for( i = 2 ; i ≤ n, i++)D[ i ] = C[1, i ] ; // asigna valor inicial a D

for( i = 1 ; i ≤ n - 1, i++){ elegir un vértice w en V - S tal que D[ w ] sea mínimo ;

agregar w a S ;for( cada vértice v en V - S )

D[ v ] = mín(D[ v ], D[ w ] + C[ w, v ]) ;}

}



• Suponiendo que G = (V, E) es un grafo dirigido con nvértices y a aristas.

• Si se usa una matriz de adyacencia para representar el grafo dirigido : O(n2).

• Si se usa una lista de adyacencia para representar el grafo dirigido : O(a log n) ; • a es el número de actualizaciones (de las distancias en la

cola de prioridad).

Tiempo de Ejecución de Dijkstra


• Problema : Determinar el tiempo de vuelo menor entre dos ciudades cualquiera.

• Se tiene un grafo dirigido etiquetado que da el tiempo de vuelo para ciertas rutas entre ciudades.

• Se quiere encontrar el camino más corto entre todos los pares.

Solución: Algoritmo de Floyd. Se aplica el algoritmo de Dijkstra para cada vértice, como vértice de origen cada vez, por turno.

Algoritmo de Floyd


S

BA

NY2

8

3

5

2

Ejemplo:

Algoritmo de Floyd


Matriz inicial de costo:

S

BA

NY2

8

3

5

2

Algoritmo de Floyd

S BA NY

S 2 8 5

BA 3 ∞ ∞

NY ∞ 2 ∞

A =


Reemplazar por 0 los que van a sí mismos:

S

BA

NY2

8

3

5

2

Algoritmo de Floyd

S BA NY

S 0 8 5

BA 3 0 ∞

NY ∞ 2 0

A =


Pasando por el vértice S:

S

BA

NY2

8

3

5

2

Algoritmo de Floyd

S BA NY

S 0 8 5

BA 3 0 8

NY ∞ 2 0

A =


Pasando por los vértice S y BA :

S

BA

NY2

8

3

5

2

Algoritmo de Floyd

S BA NY

S 0 8 5

BA 3 0 8

NY 5 2 0

A =


Pasando por los vértice S, BA y NY :

S

BA

NY2

8

3

5

2

Algoritmo de Floyd

S BA NY

S 0 7 5

BA 3 0 8

NY 5 2 0

A =


Floyd ( int *A[n,n]; int c[n,n] ){ int i, j, k;

for (i = 1; i <= n; i++)for (j = 1; i <= n; j++)

A[i, j] = C[i, j] ; // se iniciliza A con todos los costosfor (i = 1; i <= n;i++)

A[ i, i ] = 0;for (k = 1; k <= n; k++)

for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)

if ( (A[i, k] + A[k, j]) < A[i, j] )A[i, j] = A[i, k] + A[k, j];

}

Algoritmo de Floyd

Vértices numerado 1 : nA[i, j]nxn = se calculan las longitudes de los caminos más cortos.C[ i, j ] = matriz de costos de arcos.


• Determinar la matriz de adyacencia para el siguiente grafo:

Ejercicios

Solución :

1 2 3 4

1 ∞ 1 ∞ 4

2 1 ∞ ∞ ∞

3 3 ∞ ∞ ∞

4 10 5 11 ∞


• Determinar el camino mínimo (de menor peso) usando el algoritmo de Dijkstra, usando como nodo inicial el nodo N1

Ejercicios

Nodo marca distancia

N1 true 0

N2 true 2

N3 true 3

N4 true 1

N5 true 3

N6 true 4

N7 true 3


• El nodo N1 será el primer nodo seleccionado. • En la tabla se marca como visitado y se inspeccionan los nodos

adyacentes, N2 y N4. • En ambos casos el costo mínimo hasta ese momento es infinito,

por lo que se encontró un camino mejor pasando por N1.

Solución :


• El costo de este camino es el costo del camino a N1 más el del arco que los une.

• Para N2 es d2 = d1 + c1, 2 = 0 + 2 = 2.• Para N4 es d4 = d1 + c1, 4 = 0 + 1 = 1. • En ambos casos, el campo camino se actualiza a N1. • De estos dos nodos, se selecciona N4 por ser el que tiene del

camino de menor costo. • Se marca y se analizan los nodos adyacentes a N4, que son N3,

N5, N6 y N7. • En todos los casos, como no había un camino previo, se toma

como mejor camino de forma provisional el camino a través de N4, actualizándose los campos distancia y camino.

Solución :


• El siguiente nodo seleccionado en N2, que tiene como nodos adyacentes N4 y N5.

• Como N4 está marcado como visitado, y tiene por tanto un camino mejor que N2, no se trabaja con él.

• El camino a N5 a través de N2 tiene peso d5 = d2 + c2, 5 = 2+10 = 12 no es mejor que el que ya tenía N5, por lo que no se modifica.

• El resto de los nodos se escogen en el siguiente orden: N5, N3, N7y N6

Solución :


Solución :

Nodo marca distancia camino

N1 true 0 -

N2 true 2 N1

N3 true 3 N4

N4 true 1 N1

N5 true 3 N4

N6 true 6 N7

N7 true 5 N4

• La tabla queda con los siguientes valores finales:


Ejercicios

• Dado el siguiente grafo, indicar la secuencia que se obtiene con:1. Recorrido en profundidad.2. Recorrido en amplitud.

en el recorrido suponer un orden alfabético entre los nodos adyacentes a uno dado.el elemento inicial es el nodo a

Solución: 1. a, d, g, e, f, c, b2. a, b, e, f, g, d, c


Ejercicios

10

4 2

10

30100 50

10

20603

-460-31020-2∞∞50-1

100

30∞10-043210

El siguiente grafo representa la conexión de una red :

Completar la traza de la aplicación del algoritmo de Dijkstra al grafo anterior.


Solución

10

4 2

10

30100 50

10

20603 -4

60-3

1020-2∞∞50-1

100

30∞10-0

43210

260030350010{0,1,2,3,4}42600303500102{0,1,2,3}33900303 500103{0,1,3}201000301600101{0,1}101000300∞010-{0}0P[4]D[4]P[3]D[3]P[2]D[2]P[1]D[1]nSIteración


Ejercicios

• El siguiente grafo representa la conexión de una red :

Hacer la traza de la aplicación del algoritmo de Dijkstra al grafo

10

4 2

10

30100 50

10

20603 -4

60-31020-2∞∞50-1

100

30∞10-043210


Ejercicios

• Aplicar Floyd al siguiente grafo:

3

25

A8

B

C


Solución:

3

25

A8

B

C

A0[i][j] A1[i][j]

A3[i][j]A2[i][j]

02-02-C803-03B580580ACBACBA

025025803803570580CBACBA


Solución:

3

25

A8

B

C

A0[i][j] A1[i][j]

A3[i][j]A2[i][j]

02-02-C803-03B580580ACBACBA

025025803803570580CBACBA


• Fuente: Los grafos como modelos matemáticos: ejemplos históricos y aplicaciones actuales. web.udl.es/usuaris/p4088280/teaching/grafos_modelos.pdf

• El problema de los siete puentes de Königsberg (Euler, 1736)• El problema del cartero chino (Kwan Mei-Ko, 1960)

• El juego del dodecaedro (Hamilton, 1857)• El problema del vendedor viajero. (Primeras referencias datan

de 1832; J.B. Robinson, “On the Hamiltonian game (a traveling-salesman problem)”, 1949. Es la primera referencia del problema tal como es conocido actualmente).

Algunas Aplicaciones


• Análisis de redes eléctricas (Kirchho, 1847).• Enumeración de isómeros químicos (Cayley, 1857).

• El problema del conector mínimo.• El problema de los de cuatro colores (Appel y Haken 1976)

• El problema de los horarios.• El problema de la asignación de frecuencias en una red

celular de telefonía móvil.• El problema del camino mínimo (Dijkstra, 1959)

• Análisis del camino crítico.• El problema del flujo máximo (Ford y Fulkerson, 1956)

• Modelización de la World-Wide Web

Algunas Aplicaciones


• ¿Se puede recorrer toda la ciudad pasando una sola vez por todos y cada uno de los 7 puentes que unen la parte insular de la ciudad con el resto?

El problema de los siete puentes de Königsberg


• Un cartero debe repartir la correspondencia a cada una de las manzanas de casas de su distrito siendo la oficina de correos su punto de partida y fin. Encontrar una ruta optima (distancia total recorrida mínima).

El problema del cartero chino


• Situaciones “reales”:

• ruta óptima para un camión de basuras • para un inspector de contadores de luz, etc., • trazado óptimo de un grafo mediante un plotter.

El problema del cartero chino


• Buscar un recorrido que dé la vuelta al mundo, representado por un dodecaedro, visitando cada ciudad, correspondiente a un vértice del dodecaedro, una sola vez. Solamente se puede desplazar de una ciudad a otra si los vértices correspondientes del dodecaedro están unidos por una arista.

El juego del dodecaedro


• Un representante de una editorial, con sede en la ciudad A, debe visitar una serie de clientes establecidos en distintas ciudades de manera que su itinerario tenga como principio y n A. ¿Qué ruta deberá seguir con el fin de minimizar costos?

• Modelización: Dado un grafo completo y ponderado (grafo de distancias), hallar un ciclo hamiltoniano de costo mínimo (longitud total mínima).

El problema del vendedor viajero


Ruta Vehicular• Bus Escolar.• Atención de Llamadas

de Emergencia.• Servicio de Correo

Expreso.

El problema del vendedor viajero; Aplicaciones


Secuenciamiento de genes.

El problema del vendedor viajero, Aplicaciones

Ordenamiento de observaciones en telescopios (NASA).


Diseño de chips.

El problema del vendedor viajero; Aplicaciones

Tour Mundial.


• Aplicaciones:• El problema del Viejo

Pascuero

El problema del vendedor viajero


• Método efectivo para el análisis de redes eléctricas entendido dicho análisis como el cálculo de la intensidad y la diferencia de potencial de cada elemento de la red (resistencia, bobina, condensador, fuente de tensión, etc.).

Análisis de redes eléctricas


• Método efectivo para el análisis de redes eléctricas entendido dicho análisis como el cálculo de la intensidad y la diferencia de potencial de cada elemento de la red (resistencia, bobina, condensador, fuente de tensión, etc.).

Enumeración de isómeros químicos


• Dado un conjunto de ciudades se desea construir una red de carreteras, que conecte a todas entre sí. ¿Cual es la red de costo mínimo?

• Modelización: Dado un grafo conexo y ponderado, hallar un árbol generador de peso mínimo.

El problema del conector mínimo


Conjetura (Francis Guthrie, 1852): Todo mapa trazado sobre una hoja de papel puede colorearse usando solamente cuatro tintas de manera que “países" con “frontera común" tengan colores diferentes.

El problema de los cuatro colores


Aplicaciones:• El problema de los horarios: Confeccionar un calendario de

exámenes, que comprenda el mínimo numero de días, teniendo en cuenta que un estudiante no puede realizar más de un examen en un mismo día.

• El problema de la asignación de frecuencias en una red celular de telefonía móvil: Asignar a cada celda un rango de frecuencias de manera que celdas contiguas tengan rangos disjuntos. ¿Cómo debe hacerse dicha asignación con el fín de minimizar el total de frecuencias usadas?

• Modelización: Dado el grafo de incompatibilidades, hallar una vértice coloración del mismo utilizando el menor numero de colores posible.

El problema de los cuatro colores


• Dada una red de transporte hallar la ruta óptima entre cada par de elementos de la misma.

• Modelización: Calcular la distancia y encontrar un camino mínimo entre cada par de vértices de un grafo conexo y ponderado.

El problema del camino mínimo


• Planificar las actividades de un proyecto de forma que el tiempototal para realizarlo sea el menor posible.

• Modelización: Dado el correspondiente grafo de actividades, hallar el camino mas largo entre los vértices que representan los estados “inicio” y “fín”.

Análisis del camino crítico


• Hallar el flujo máximo que fluye a través de una red, desde un nodo fuente hasta un nodo sumidero, cuando sus enlaces tienen una capacidad limitada de transporte.

El problema del flujo máximo


• Estudio de la topología de la Web (conectividad, diámetro, …).• Formulación de algoritmos de valoración de las páginas web

(algoritmo PageRank de Google, …).

Modelización de la World-Wide Web


1. Cormen, Leiserson, Rivest: Introducción a la Algorítmica, The MIT Press-Mc Graw Hill, 1990. 199 – 215.

2. Aho A. V., Hopcroft J.E., Ullman J.D.; Estructuras de Datos y Algoritmos. Ed. Addison-Wesley, 1998.

3. www.infovis.net/printMag.php?num=137&lang=14. web.udl.es/usuaris/p4088280/teaching/grafos_modelos.pdf5. users.dsic.upv.es/asignaturas/facultad/eda/teoria/tema4/t4eda.

pdf6. rua.ua.es/dspace/bitstream/10045/4411/28/ped-06_07-

tema5.pdf7. http://ccg.ciens.ucv.ve/~ernesto/nds/CotoND200302.pdf8. EL Problema del Vendedor Viajero (TSP) y Programación

Entera (IP). Daniel Espinoza, U.Ch., Fac.Cs Fís y Mat.,DeptoIng.Ind., 24 de julio de 2006

Bibliografía – Webgrafía

estructura de datos grafos6_diapos]_=d.pdf · universidad técnica federico santa maría -...

Documents