tópicos i

61
Tópicos I Unidad I Semana 5 Grafos dirigidos, Flujo de red, Concordancia Árboles, montículos y grafos

Upload: vielka-diaz

Post on 01-Jan-2016

33 views

Category:

Documents


4 download

DESCRIPTION

Unidad I. Tópicos I. Árboles, montículos y grafos. Semana 5. Grafos dirigidos, Flujo de red, Concordancia. Objetivos Generales. Entender el manejo, uso de algoritmos y estructuras de datos avanzados, haciendo énfasis en los algoritmos de internet, seguridad y redes. Objetivo Específico. - PowerPoint PPT Presentation

TRANSCRIPT

Page 1: Tópicos I

Tópicos I

Unidad I

Semana 5

Grafos dirigidos, Flujo de red, Concordancia

Árboles, montículos y grafos

Page 2: Tópicos I

Objetivos Generales

Entender el manejo, uso de algoritmos y estructuras de datos avanzados, haciendo énfasis en los algoritmos de internet, seguridad y redes.

Page 3: Tópicos I

Objetivo Específico

Implementar algoritmos utilizando estructura de datos avanzadas.

Page 4: Tópicos I

Objetivo Instruccional

Implementar algoritmos fundamentales para la solución de problemas basados en la teoría de grafos.

Page 5: Tópicos I
Page 6: Tópicos I

DefiniciónSon aquellos en los que las aristas que conectan los nodos son de sentido único. También se les denomina como DIGRAFOS.

A menudo, la dirección de las aristas reflejan algún tipo de relación de precedencia en la aplicación que se esta modelando.

Por ejemplo, un grafo dirigido puede utilizarse como modelo para una cadena de fabricación, los nodos corresponden a las tareas a realizar.

El orden en el que aparecen los vértices al especificar las aristas tiene mucha importancia: la notación V1V2 describe una arista que apunta de V1 hacia V2, pero no de V2 hacia V1.

Page 7: Tópicos I

Búsqueda en profundidad

Los algoritmos de búsqueda en profundidad estudiados anteriormente pueden ser utilizados exactamente de igual forma con los grafos dirigidos.

De hecho, opera de una manera un poco mas directa que con los grafos no dirigidos dado que no se necesita tener en cuenta las dobles aristas entre nodos, a menos que estén incluidas explícitamente en el grafo.

Page 8: Tópicos I

Búsqueda en profundidad1 2 3 4 5 6 7 8 9 10 11 12

1

2

3

5

4

6

7

8

10

9

12

11

Page 9: Tópicos I

Búsqueda en profundidadComo en el caso de los grafos no dirigidos, existe gran interés en conocer las propiedades de conectividad de los grafos dirigidos. Debería ser posible responder a preguntas tales como:¿Existe un camino dirigido desde el vértice x al vértice y?, ¿Qué vértices son accesibles desde el vértice x por medio de un camino dirigido? y ¿Existe un camino dirigido desde el vértice x al vértice y y un camino dirigido desde y a x?

Page 10: Tópicos I

Clausura transitiva

El concepto de transitividad es el mismo que se utiliza en la teoría matemática , el cual postula que si a < b < c a < c, en el caso de la clausura transitiva, el concepto se refiere a que existe un camino que une el vértice x con el vértice y, no importando que para llegar desde x a y tengamos que visitar otros vértices del grafo (camino mas corto).

Page 11: Tópicos I

Clausura transitiva

Consiste en completar el grafo con todas las aristas que "acortan" el camino entre dos nodos x y y, si es que se puede llegar de x a y.

En digrafos muy grandes, el problema de encontrar caminos entre pares de vértices es demasiado complicado, sólo siguiendo el trazado del dibujo del mismo, de ahí la importancia de este algoritmo y el interés que generó su estudio.

Page 12: Tópicos I

Clausura transitivaMétodo de Warshall

Ejemplo

1 1

Page 13: Tópicos I

Clausura transitivaMétodo de Warshall

1 1

Page 14: Tópicos I

Clausura transitivaMétodo de Warshall

Page 15: Tópicos I

Clausura transitivaMétodo de Warshall

Se continua analizando hasta el vértice 9, obteniendo las siguientes etapas finales

Page 16: Tópicos I

Todos los caminos mas cortos

La clausura transitiva de un grafo no ponderado (dirigido o no) responde a la pregunta “¿Existe un camino desde x a y?” para todos los pares de vértices x, y.

Para los grafos ponderados (dirigidos o no) se puede desear construir una tabla que permita encontrar el camino mas corto desde x a y para todos los pares de vértices.

Este es el “problema de todos los pares de caminos cortos”.

Page 17: Tópicos I

Todos los caminos mas cortos

El algoritmo del camino mas corto (warshall) encuentra el camino mas corto desde el vértice de partida a cada uno de los otros vértices, por lo que para hallar todos los caminos mas cortos, se necesita solamente ejecutar este procedimiento V veces, comenzando una vez en cada vértice.

Page 18: Tópicos I

Todos los caminos mas cortos

• El algoritmo representa una red de n nodos como una matriz cuadrada de orden n, la llamaremos matriz C. De esta forma, el valor Cij representa el coste de ir desde el nodo i al nodo j, inicialmente en caso de no existir un arco entre ambos, el valor Cij será infinito.

• Definiremos otra matriz D, también cuadrada de orden n, cuyos elementos van a ser los nodos predecesores en el camino hacia el nodo origen, es decir, el valor Dij representará el nodo predecesor a j en el camino mínimo desde i hasta j. Inicialmente se comienza con caminos de longitud 1, por lo que Dij = i.

• Las diagonales de ambas matrices representan el coste y el nodo predecesor para ir de un nodo a si mismo, por lo que no sirven para nada, estarán bloqueadas.

Los pasos a dar en la aplicación del algoritmo de Floyd son los siguientes: Formar las matrices iniciales C y D. Se toma k=1. Se selecciona la fila y la columna k de la matriz C y entonces, para i y j, con i<>k, j<>k e i<>j, hacemos:

Si (Cik + Ckj) < Cij Dij = Dkj y Cij = Cik + Ckj

En caso contrario, dejamos las matrices como están.

Si k <= n, aumentamos k en una unidad y repetimos el paso anterior, en caso contrario paramos las iteraciones.

La matriz final C contiene los costes óptimos para ir de un vértice a otro, mientras que la matriz D contiene los penúltimos vértices de los caminos óptimos que unen dos vértices, lo cual permite reconstruir cualquier camino óptimo para ir de un vértice a otro.

Método de Floyd

Page 19: Tópicos I

Todos los caminos mas cortos

Método de FloydAplicar el algoritmo de Floyd sobre el siguiente grafo para obtener las rutas más cortas entre cada dos nodos.

Page 20: Tópicos I

Todos los caminos mas cortos

Método de Floyd

C 1 2 3 4 5

1 - 3 10 ∞ ∞

2 3 - ∞ 5 ∞

3 10 ∞ - 6 15

4 ∞ 5 6 - 4

5 ∞ ∞ ∞ 4 -

D 1 2 3 4 5

1 1 1 1 1 1

2 2 2 2 2 2

3 3 3 3 3 3

4 4 4 4 4 4

5 5 5 5 5 5

Se inicializan las matrices C y D

Page 21: Tópicos I

Todos los caminos mas cortos

Método de Floyd

C 1 2 3 4 5

1 - 3 10 ∞ ∞

2 3 - ∞ 5 ∞

3 10 ∞ - 6 15

4 ∞ 5 6 - 4

5 ∞ ∞ ∞ 4 -

D 1 2 3 4 5

1 1 1 1 1 1

2 2 2 2 2 2

3 3 3 3 3 3

4 4 4 4 4 4

5 5 5 5 5 5

Iteración: k = 1 2 3 4 5

Si (Cik + Ckj) < Cij Cij = Cik + Ckj y Dij = Dkj = k

Para i=2, j=3 se tiene calcular C[2,3]: C[2,1]+C[1,3] = 3 + 10 = 13

(Cik + Ckj) < Cij 13 < ∞ Cij = 13 y Dij = 1

Page 22: Tópicos I

Todos los caminos mas cortos

Método de Floyd

C 1 2 3 4 5

1 - 3 10 ∞ ∞

2 3 - 13 5 ∞

3 10 ∞ - 6 15

4 ∞ 5 6 - 4

5 ∞ ∞ ∞ 4 -

D 1 2 3 4 5

1 1 1 1 1 1

2 2 2 1 2 2

3 3 3 3 3 3

4 4 4 4 4 4

5 5 5 5 5 5

Iteración: k = 1 2 3 4 5

De forma análoga se analiza los demás elementos de la matriz, obteniéndose al final de la iteración 1 los siguientes resultados:

C 1 2 3 4 5

1 - 3 10 ∞ ∞

2 3 - 13 5 ∞

3 10 13 - 6 15

4 ∞ 5 6 - 4

5 ∞ ∞ ∞ 4 -

D 1 2 3 4 5

1 1 1 1 1 1

2 2 2 1 2 2

3 3 1 3 3 3

4 4 4 4 4 4

5 5 5 5 5 5

Page 23: Tópicos I

Todos los caminos mas cortos

Método de Floyd

Iteración: k = 1 2 3 4 5 C 1 2 3 4 5

1 - 3 10 ∞ ∞

2 3 - 13 5 ∞

3 10 13 - 6 15

4 ∞ 5 6 - 4

5 ∞ ∞ ∞ 4 -

D 1 2 3 4 5

1 1 1 1 1 1

2 2 2 1 2 2

3 3 1 3 3 3

4 4 4 4 4 4

5 5 5 5 5 5

De forma análoga se analiza los demás elementos de la matriz, obteniéndose al final de la iteración 2 los siguientes resultados:

C 1 2 3 4 5

1 - 3 10 8 ∞

2 3 - 13 5 ∞

3 10 13 - 6 15

4 8 5 6 - 4

5 ∞ ∞ ∞ 4 -

D 1 2 3 4 5

1 1 1 1 2 1

2 2 2 1 2 2

3 3 1 3 3 3

4 2 4 4 4 4

5 5 5 5 5 5

Page 24: Tópicos I

Todos los caminos mas cortos

Método de Floyd

Iteración: k = 1 2 3 4 5

De forma análoga se analiza los demás elementos de la matriz, obteniéndose al final de la iteración 3 los siguientes resultados:

C 1 2 3 4 5

1 - 3 10 8 25

2 3 - 13 5 28

3 10 13 - 6 15

4 8 5 6 - 4

5 ∞ ∞ ∞ 4 -

D 1 2 3 4 5

1 1 1 1 2 3

2 2 2 1 2 3

3 3 1 3 3 3

4 2 4 4 4 4

5 5 5 5 5 5

C 1 2 3 4 5

1 - 3 10 8 ∞

2 3 - 13 5 ∞

3 10 13 - 6 15

4 8 5 6 - 4

5 ∞ ∞ ∞ 4 -

D 1 2 3 4 5

1 1 1 1 2 1

2 2 2 1 2 2

3 3 1 3 3 3

4 2 4 4 4 4

5 5 5 5 5 5

Page 25: Tópicos I

Todos los caminos mas cortos

Método de Floyd

Iteración: k = 1 2 3 4 5

De forma análoga se analiza los demás elementos de la matriz, obteniéndose al final de la iteración 4 los siguientes resultados:

C 1 2 3 4 5

1 - 3 10 8 12

2 3 - 11 5 9

3 10 11 - 6 10

4 8 5 6 - 4

5 12 9 10 4 -

D 1 2 3 4 5

1 1 1 1 2 4

2 2 2 4 2 4

3 3 4 3 3 4

4 2 4 4 4 4

5 4 4 4 5 5

C 1 2 3 4 5

1 - 3 10 8 25

2 3 - 13 5 28

3 10 13 - 6 15

4 8 5 6 - 4

5 ∞ ∞ ∞ 4 -

D 1 2 3 4 5

1 1 1 1 2 3

2 2 2 1 2 3

3 3 1 3 3 3

4 2 4 4 4 4

5 5 5 5 5 5

Page 26: Tópicos I

Todos los caminos mas cortos

Método de Floyd

Iteración: k = 1 2 3 4 5

De forma análoga se analiza los demás elementos de la matriz, obteniéndose al final de la iteración 5 los siguientes resultados:

C 1 2 3 4 5

1 - 3 10 8 12

2 3 - 11 5 9

3 10 11 - 6 10

4 8 5 6 - 4

5 12 9 10 4 -

D 1 2 3 4 5

1 1 1 1 2 4

2 2 2 4 2 4

3 3 4 3 3 4

4 2 4 4 4 4

5 4 4 4 5 5

C 1 2 3 4 5

1 - 3 10 8 12

2 3 - 11 5 9

3 10 11 - 6 10

4 8 5 6 - 4

5 12 9 10 4 -

D 1 2 3 4 5

1 1 1 1 2 4

2 2 2 4 2 4

3 3 4 3 3 4

4 2 4 4 4 4

5 4 4 4 5 5

Page 27: Tópicos I

Todos los caminos mas cortos

Método de FloydC 1 2 3 4 5

1 - 3 10 8 12

2 3 - 11 5 9

3 10 11 - 6 10

4 8 5 6 - 4

5 12 9 10 4 -

D 1 2 3 4 5

1 1 1 1 2 4

2 2 2 4 2 4

3 3 4 3 3 4

4 2 4 4 4 4

5 4 4 4 5 5

Las matrices finales C y D contienen toda la información necesaria para determinar la ruta más corta entre dos nodos cualquiera de la red. Por ejemplo, la distancia más corta del nodo 1 al nodo 5 es C[1,5] = 12.

Para determinar la ruta asociada del camino mínimo entre el nodo 1 y el nodo 5 haremos lo siguiente:Consultamos D[1,5]=4, por tanto el nodo predecesor al 5 es el 4, es decir, 4 5.Consultamos D[1,4]=2, por tanto el nodo predecesor al 4 es el 2, es decir, 2 4 5.Consultamos D[1,2]=1, por tanto el nodo predecesor al 2 es el 1, es decir, 1 2 4 5,

Entonces así ya tenemos la ruta completa.

Matrices finales

Page 28: Tópicos I

Ordenación topológica

Los grafos cíclicos aparecen en muchas de las aplicaciones en las que intervienen los grafos dirigidos. El grafo descrito modela una cadena de producción, esto implica que la tarea A debe hacerse antes de la tarea G, esta antes que la C, y esta antes que la A. Pero tal situación es inconsistente.

A

B

C

G

F

ED

En estos casos hay que invocar grafos dirigidos con ciclos no dirigidos (todas las aristas apuntando en la misma

dirección). Tales grafos se denominan grafos dirigidos acíclicos (gda).

Page 29: Tópicos I

Ordenación topológica

Los gdas pueden tener numerosos ciclos, si no se tienen en cuenta las direcciones de las aristas; pero por su propia definición es evidente que no se puede llegar nunca a un ciclo siguiendo las aristas en la dirección indicada.

A

B

C

G

F

ED

Una operación fundamental sobre los gdas es el tratamiento de los vértices del grafo en un orden tal que ningún vértice se procese antes de cualquier otro que apunte hacia el.En el grafo anterior, los nodos podrían procesarse en el siguiente orden:

A G C F E D BEsta operación se denomina ORDENACION TOPOLOGICA

Page 30: Tópicos I

Ordenación topológicaLa ordenación topológica es un sistema de ordenamiento de un grafo acíclico, es decir, que no tiene ciclos; el cual consiste, en organizar de forma lineal ó en lista ascendente ó descendente, una serie de vértices en desorden, para lo cual primero debe de empezar de un "vértice padre" o sea, un vértice sin predecesores, y después visitar a sus vecinos, después de que haya visitado a todos sus vecinos, pasa a analizar otro vértice, y de igual forma identifica todos sus vecinos, y así recursivamente, hasta que haya visitado a todos los vértices. En pocas palabras no se visitara un vértice, hasta que todos sus predecesores hayan sido visitados.

Después de que ya han sido visitados todos los vértices del grafo dirigido, se acomodan en lista ya sea de forma ascendente o descendente, según se requiera, y se acomodan en base a el coste de tiempo de los vértices.

Page 31: Tópicos I

Grafos dirigidos acíclicos (gda)

Definición: Es un grafo dirigido sin ciclos.

Ejemplos: grafo de planificación de tareas, expresiones aritméticas (con subexpresiones comunes), grafo de prerrequisitos, etc.

Licenciade obras 6

Aplanarterreno 4

Comprarpiedras 2

Cincelarpiedras

Hacercamino 3

Colocarpiedras 9Pintar

pirámide 3

8

*

+

A B D

+

*

(A+B)*(D+D*(A+B))

Page 32: Tópicos I

Grafos dirigidos acíclicos (gda)

54

3

2

1

Sea G un grafo conexo, dirigido y acíclico. Y sean a y b vértices del grafo. Si existe un camino de a hasta b, entonces b aparece después de a en el ordenamiento topológico.

Page 33: Tópicos I

Grafos dirigidos acíclicos (gda)

54

3

2

1

Ejemplo:

Encontrar el orden topológico del siguiente grafo.

Page 34: Tópicos I

Grafos dirigidos acíclicos (gda)

54

3

2

1

Ejemplo:

Encontrar el orden topológico del siguiente grafo.

Page 35: Tópicos I

Grafos dirigidos acíclicos (gda)

54

3

2

1

Inicialmente el algoritmo se inicializa con una cola vacía. Se agregan los “nodos iniciales” que no tienen arcos entrantes.

Lista =

Page 36: Tópicos I

Grafos dirigidos acíclicos (gda)

54

3

2Se elimina el nodo insertado y todas las aristas que salen de el. Se agregan los nuevos “nodos iniciales” que no tienen arcos entrantes.

Lista = 1-

Page 37: Tópicos I

Grafos dirigidos acíclicos (gda)

54

2De forma análoga:

Lista = 1- 3

Page 38: Tópicos I

Grafos dirigidos acíclicos (gda)

54

Lista = 1- 3 - 2

De forma análoga:

Page 39: Tópicos I

Grafos dirigidos acíclicos (gda)

5

Lista = 1- 3 – 2 - 4

De forma análoga:

Page 40: Tópicos I

Grafos dirigidos acíclicos (gda)

Finalmente:

El orden topológico del grafo es 1 - 3 - 2 - 4 - 5

54

3

2

1

Page 41: Tópicos I

Componentes fuertemente conexas

Si un grafo contiene un ciclo dirigido entonces no es un gda y no puede ordenarse topológicamente: cualquier vértice del ciclo que se imprima primero tendrá otro vértice que apunta hacia el y que todavía no se ha impreso.

Los nodos del ciclo son mutuamente accesibles en el sentido de que existe una forma de ir desde cualquier nodo a otro y regresar.

Page 42: Tópicos I

Componentes fuertemente conexas

De hecho, los nodos se dividen ellos mismos en conjuntos denominados componentes fuertemente conexas que tienen la propiedad de que todos los nodos del interior de una componente son mutuamente accesibles, pero no existe ningún medio de ir desde un nodo de una de las componentes a otro de otra componente y regresar.

Las componentes fuertemente conexas del grafo son los nodos sencillos K, el par H, I, etc. Por ejemplo, el vértice A esta en una componente diferente de la del vértice F porque, aunque existe un camino desde A hacia F, no lo hay para ir de F hacia A.

Page 43: Tópicos I

Componentes fuertemente conexas

Método de Tarjan

Page 44: Tópicos I

ProblemáticaLos grafos dirigidos ponderados son modelos muy útiles en ciertos tipos de aplicaciones que implican flujo de productos a través de una red de interconexión. Considérese, por ejemplo, una red de oleoductos de distintos tamaños, interconectados de forma compleja, con válvulas que controlen la dirección del flujo en las derivaciones. Supóngase además que la red tiene una fuente única (como

un campo de petróleo) y un único destino (como una gran

refinería) al que convergen finalmente todos los conductos. ¿Qué ajuste de válvula hará máxima la cantidad de petróleo que fluye de la fuente hacia el destino?

Page 45: Tópicos I

El problema del flujo de red

B

F

A

D E

C B

F

A

D E

C B

F

A

D E

C

Flujo máximo en una red simple

Page 46: Tópicos I

El problema del flujo de redEn la grafica idealizada anterior de la pequeña red de oleoducto, las canalizaciones tienen una capacidad fija proporcional a su tamaño y el petróleo solamente puede fluir en forma descendente. Además las válvulas de cada derivación controlan la capacidad de petróleo que va en cada dirección. Sin importar la forma en la que estén puestas las válvulas, el sistema alcanza un estado de equilibrio cuando la capacidad de petróleo que fluye al sistema por arriba es igual a la cantidad que fluye hacia afuera por la parte inferior y cuando la cantidad de petróleo que fluye hacia cada derivación es igual a la que sale de ella.

Page 47: Tópicos I

El problema del flujo de red

El objetivo es desarrollar un algoritmo que pueda encontrar el reglaje de las válvulas “adecuado” para cualquier red y de esta manera evitar “embotellamientos”. Además, se desea estar seguros de que ningún otro reglaje dará un flujo mayor.

B

F

A

D E

C B

F

A

D E

C B

F

A

D E

C

Page 48: Tópicos I

El problema del flujo de redRed: Se define como un grafo dirigido ponderado con dos vértices principales: uno, que no tiene aristas que apunte a el (la fuente), y otro que no tiene aristas que apunten afuera de el (el pozo). Los pesos de las aristas, que se supone que no son negativos, se denominan capacidades de las aristas.

Flujo: Se define como un conjunto de pesos en las aristas tal que el flujo en cada una de ellas es igual o menor que la capacidad, y el flujo que entra en cada vértice es igual al que sale de el. El valor del flujo es el que entra en la fuente (o sale del pozo).

“El problema del flujo de red consiste en encontrar un FLUJO DE VALOR MÁXIMO para una red dada” .

Page 49: Tópicos I

Método de Ford-FulkersonEl algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo máximo. La idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos origen y destino.

Consideraremos las capacidades iniciales del arco que une el nodo i y el nodo j como Cij y Cji. Estas capacidades iniciales irán variando a medida que avanza el algoritmo, denominaremos capacidades residuales a las capacidades restantes del arco una vez pasa algún flujo por él, las representaremos como cij y cji.Para un nodo j que recibe el flujo del nodo i, definimos una clasificación [aj,i] donde aj es el flujo del nodo i al nodo j.

Page 50: Tópicos I

Método de Ford-FulkersonPASOS:1.Identificar los nodos origen y destino2.Identificar la capacidad mas alta que sale del nodo origen3.Identificar el nodo intermediario con [af,i] (af es el flujo máximo de ingreso y i el nodo de donde proviene dicho flujo máximo)

4.Repetir paso 3, como si el nodo intermediario fuera el nodo origen5.Actualizar los flujos: Cij , Cji = (Ci – k, Cj + k) donde:

C = Capacidadi , j = índices de los nodosK = flujo mínimo del camino seleccionado6.Retornar al paso 2 si al menos hay una salida de flujo del nodo fuente7.La suma de los K corresponde al Flujo Máximo.

Page 51: Tópicos I

Método de Ford-Fulkerson

1

2 3

4

510

30

20

0

0

40

20

0

10

0

0

030

0

020

Fuente

Sumidero

Capacidad de flujo máximo del nodo 1 al

nodo 4

Del nodo 4 al nodo 1 no hay

flujo

[ ∞,-]

Por ser la fuente se

considera la cantidad de

flujo máximo de ingreso (∞)

Por no tener nodo conocido como inicio se

considera (-)

[ ∞,-]

PASO 1

Page 52: Tópicos I

Método de Ford-Fulkerson

1

2 3

4

510

30

20

0

0

40

20

0

10

0

0

030

0

020

[ ∞,-]

Iteración 1

[ 30,1]

Paso 2Paso 3

[ 20,3]

Actualizando las capacidades

K = min (∞,30,20) = 20 i = 1 , j = 3

Cij , Cji = (30 – 20, 0 + 20) = (10,20)i = 3 , j = 5Cij , Cji = (20 – 20, 0 + 20) = (0,20)

30

0

020

1

2 3

4

510

20

0

0

40

20

0

10

0

030

0

[ ∞,-]

[ 30,1]

[ 20,3]

10

20

20

0

Page 53: Tópicos I

Método de Ford-Fulkerson

1

2 3

4

510

10

20

0

0

40

20

0

10

0

20

030

0

20

0

[ ∞,-]

Iteración 2K = min (∞,20,40,10,20) = 10

1

2 3

4

510

10

10

0

10

30

10

10

0

0

20

1030

10

20 0

[ ∞,-]

[ 10,3]

[ 40,2]

C12 , C21 = (20 – 10, 0 + 10) = (10,10)C23 , C32 = (40 – 10, 0 + 10) = (30,10)C34 , C43 = (10 – 10, 0 + 10) = ( 0,10)C45 , C54 = (20 – 10, 0 + 10) = (10,10)

[ 20,4]

[ 20,1]

Page 54: Tópicos I

Método de Ford-Fulkerson

1

2 3

4

510

10

10

0

10

30

10

1 0

0

0

20

1030

10

20

0

[ ∞,-]

Iteración 3

K = min (∞,10,30) = 10

1

2 3

4

510

10

0

0

10

30

10

10

0

10

20

2020

10

20 0

[ ∞,-]

C12 , C21 = (10 – 10, 10 + 10) = (0,20)C23 , C32 = (30 – 10, 0 + 10) = (20,10)

[ 10,1]

[ 30,2]

Page 55: Tópicos I

Método de Ford-Fulkerson

1

2 3

4

510

10

0

0

10

30

10

1 0

0

10

20

2020

10

20

0

[ ∞,-]

Iteración 4

K = min (∞,10,10,20) = 10

1

2 3

4

510

0

0

0

10

40

10

10

0

20

20

2010

0

30

0

[ ∞,-]

C13 , C31 = (10 – 10, 20 + 10) = (0,30)C32 , C23 = (10 – 10, 30 + 10) = (0,40)C25 , C52 = (20 – 10, 10 + 10) = (10,20)

[ 10,3]

[ 20,2]

[ 10,1]

Page 56: Tópicos I

Método de Ford-Fulkerson

1

2 3

4

510

0

0

0

10

40

10

1 0

0

20

20

2010

0

30

0

[ ∞,-]

Iteración 5

K = min (∞,10,10) = 10

1

2 3

4

50

0

0

10

10

40

0

20

0

20

20

2010

0

30

0

[ ∞,-]

C14 , C41 = (10 – 10, 0 + 10) = (0,10)C45 , C54 = (10 – 10, 10 + 10) = (0,20)

[ 10,4]

[ 10,1]

Page 57: Tópicos I

Método de Ford-Fulkerson

1

2 3

4

50

0

0

10

10

40

0

2 0

0

20

20

2010

0

30

0

[ ∞,-]

Flujo Máximo = Ʃ k = 20+10+10+10+10 = 60

Page 58: Tópicos I

Problemática

• Es una …

Page 59: Tópicos I

Grafos bipartidos

• Es una …

Page 60: Tópicos I

Problema del matrimonio estable

• Es una …

Page 61: Tópicos I

Tópicos I

Unidad I

Semana 5

Grafos dirigidos, Flujo de red, Concordancia

Árboles, montículos y grafos