U3._Redes

Programa desarrollado Unidad 3. Redes

Educacin Abierta y a Distancia * Ciencias Exactas, Ingenieras y Tecnologas

1

1

Universidad Abierta y a Distancia de Mxico

Licenciatura en Matemticas

Computacin I

6 Cuatrimestre

Unidad 3. Redes

Clave:

050920621/060920621



2

2

ndice

Presentacin de la unidad .......................................................................................................................... 3

Propsitos ................................................................................................................................................... 3

3.1. Fundamentos ........................................................................................................................................ 3

3.1.1. Conceptos Bsicos .......................................................................................................................... 4

3.1.2. Caractersticas ................................................................................................................................. 9

Actividad 1. Fundamentos de redes......................................................................................................... 17

3.2. Flujo ..................................................................................................................................................... 18

3.2.1. Flujo Mximo .................................................................................................................................. 19

3.2.2. Teorema del Corte Mnimo y Flujo Mximo .................................................................................... 22

3.2.3. Algoritmo de Corte Mnimo y Flujo Mximo .................................................................................... 24

Actividad 2. Teoremas y algoritmos de flujo ........................................................................................... 28

3.3. Conexidad ........................................................................................................................................... 29

3.3.1. Conexidad Puntual ......................................................................................................................... 31

3.3.2. Conexidad Lineal ........................................................................................................................... 33

3.3.3. Teorema de Menger ....................................................................................................................... 34

3.4. Programacin ..................................................................................................................................... 36

3.4.1. Solucin de Problemas de Redes .................................................................................................. 37

Actividad 3. Anlisis de conexidad .......................................................................................................... 49

Autoevaluacin .......................................................................................................................................... 50

Evidencia de Aprendizaje. Programacin de algoritmos para resolver problemas de redes .............. 51

Cierre de la Unidad .................................................................................................................................... 51

Para saber ms .......................................................................................................................................... 51

Fuentes de consulta .................................................................................................................................. 52



3

3

Presentacin de la unidad

Las redes aparecen en casi cualquier rea del quehacer humano, desde los circuitos elctricos hasta las

redes sociales, y requieren soluciones para sus problemas. En esta unidad tendrs la oportunidad de

aprender los fundamentos de las redes para que seas capaz de analizarlas y proponer soluciones a sus

problemas de flujo.

La Teora de grficas aporta una plataforma para representar las redes en el mbito matemtico.

Aprenders conceptos, teoremas y algoritmos para computadora alrededor de esta teora que te ayudarn

a resolver problemas de las representaciones de las redes.

Tambin estudiars conceptos, mtodos y algoritmos que te permitirn analizar la conexidad de las

grficas. Finalmente conocers el cdigo ejecutable en una computadora de algoritmos relacionados con

grficas y flujo en redes.

Propsitos

Al finalizar esta unidad sers capaz de:

Identificar los fundamentos de las redes.

Identificar teoremas y algoritmos de flujo en las redes.

Analizar la conexidad de grficas.

Programar algoritmos para resolver problemas de redes.

Competencia especfica

Utilizar algoritmos sobre grficas dirigidas para determinar flujos y rutas mediante herramientas

informticas.

3.1. Fundamentos

Los procesos y algoritmos que discutiremos en esta unidad son, de muchas maneras, el producto directo

de la necesidad de resolver esta clase especfica de problemas. En el libro (Network Flows: Theory,

Algorithms, and Applications.) de Ahuja, Ravindra K., Thomas L. Magnanti, and James B. Orlin. (1993).

Contiene una discussion extensa de de numerosas aplicaciones de los algoritmos de flujo en redes:

Entre las aplicaciones que se discuten en el libro se encuentran las siguientes:

Dado un conjunto de tareas a ser realizado por un conjunto de empleados, encontrar una tarea que

minimiza el gasto global cuando diferentes empleados cuestan diferentes cantidades dependiendo

de la tarea a la que fueron asignados.



4

4

Dado un conjunto de solicitantes que han sido entrevistados para un conjunto de puestos

disponibles, encontrar un esquema que maximiza el nmero de solicitantes seleccionados para los

trabajos para los cuales estn calificados.

Determinar la forma ms efectiva en costo para embarcar bienes desde un conjunto de fbricas

proveedoras hacia un conjunto de tiendas minoristas que venden esos bienes.

Determinar la forma ms efectiva en costo para embarcar bienes desde un conjunto de fbricas

proveedoras hacia un conjunto de tiendas minoristas que venden esos bienes, considerando el uso

potencial de un conjunto de almacenes como estaciones intermedias.

Dada una red que muestra la capacidad potencial para que bienes puedan ser embarcados entre

dos localidades, calcular el flujo mximo soportado por la red.

Como un ejemplo ms, podemos estar examinando un mapa de rutas de una lnea area y formulando

preguntas como Cul es la forma ms rpida de llegar de esta ciudad a esta otra? O quizs estamos

interesados en la manera ms barata de llegar, no en el tiempo. Para responder a estas preguntas

necesitamos informacin acerca de las interconexiones entre los objetos.

Los circuitos elctricos son otro ejemplo de la importancia de las conexiones entre objetos. Los dispositivos

elctricos pueden ser representados y procesados dentro de una computadora para responder preguntas

simples como Ya todo est conectado? O preguntas ms complejas como Funcionar este circuito si se

construye?

La estructura o patrn de interconexin de una red puede ser representada por una grfica. Las

propiedades de la grfica de una red se relacionan a menudo con las caractersticas especficas de esa

red; por ejemplo, siendo el ruteo una funcionalidad esencial en muchas redes, la complejidad

computacional del ruteo de la trayectoria ms corta depende de la cuenta de saltos en la grfica

subyacente. La Teora de Grficas es una rama de las matemticas iniciada por Euler en 1736 y ha

encontrado muchas aplicaciones en la ingeniera y en la ciencia para resolver problemas de redes.

3.1.1. Conceptos bsicos

En Matemticas discretas tuviste la oportunidad de trabajar con la teora de grficas, as que slo

revisaremos a continuacin algunos conceptos que seguramente ya conoces y que conectaremos con

representaciones en computadora; utilizaremos ms adelante esas representaciones para desarrollar

algoritmos capaces de resolver problemas de redes.

Una grfica consiste de un conjunto de objetos llamados vrtices, con ciertos pares de estos objetos

conectados por enlaces llamados aristas (edges, en ingls). Por ejemplo, la grfica de la figura siguiente

contiene cuatro vrtices (A, B, C, D), con B conectado a cada uno de los otros tres vrtices, y C y D

conectados tambin. Decimos que dos vrtices son vecinos si estn conectados por una arista.



5

5

Nota. La expresin vrtice es propia de la Teora de Grficas; en la Teora de Redes se utiliza el trmino

nodo. Como estaremos utilizando grficas y programando algoritmos alrededor de ellas para resolver

problemas de redes, mantendremos el uso de "vrtice" para evitar confusiones.

En la figura anterior se considera que la relacin entre los dos extremos de una arista es simtrica; la arista

simplemente los conecta. En otras situaciones, sin embargo, queremos expresar relaciones asimtricas

por ejemplo, que A apunta a B pero no viceversa. Para esto, definimos una grfica dirigida como un

conjunto de vrtices y aristas dirigidas; cada arista dirigida es un enlace de un vrtice al otro en el que la

direccin es importante. Las grficas dirigidas se trazan generalmente como muestra la figura siguiente,

con las aristas representadas por flechas.

Cuando queramos enfatizar que una grfica no es dirigida, la podemos llamar precisamente grfica no-

dirigida; pero en general las grficas que discutamos sern no-dirigidas a menos que se especifique otra

cosa.

Las Grficas como Modelos de Redes

Las grficas son tiles porque sirven como modelos matemticos de las estructuras de red. Por ejemplo, la

figura siguiente muestra la primera estructura de internet llamada entonces Arpanet en diciembre de

1970, cuando solamente tena 13 sitios (trazamos las localidades slo de forma aproximada). Si ests

interesado, puedes encontrar diagramas acerca de este proyecto en

(http://som.csudh.edu/cis/lpress/history/arpaMaps/).



6

6

Los vrtices representan computadoras y aparece una arista uniendo dos vrtices si existe un enlace de

comunicacin entre ellos. El diagrama puede reducirse a una grfica de 13 vrtices similar a las grficas

simples de las figuras anteriores.

Notars que el patrn de conexiones no depende de la posicin de los vrtices; lo que importa es cules

vrtices estn conectados a cules otros. Obtenemos la grfica siguiente:

Las grficas aparecen en muchos dominios, siempre que es til representar cmo las cosas estn fsica o

lgicamente enlazadas unas con otras en una estructura de red. El caso de los 13 vrtices de Arpanet es

un ejemplo de una red de comunicaciones, en la cual los vrtices son computadoras u otros dispositivos

que pueden trasmitir mensajes, y las aristas representan los enlaces a travs de los cuales los mensajes

son transmitidos.

Existen otros tipos de redes como las redes sociales, en las cuales los vrtices son personas o grupos de

personas y las aristas representan alguna clase de interaccin social; y las redes de informacin, en las

cuales los vrtices son recursos de informacin tales como pginas web o documentos, y las aristas



7

7

representan conexiones lgicas tales como hipervnculos, citas o referencias cruzadas. La lista de reas en

las que las grficas tienen una presencia es muy larga; te presentamos a continuacin dos imgenes que

se encuentran a menudo y que contienen grficas.

a) Red del Metro (Cd. de Mxico) b) Rutas areas de Aeromxico

Trayectorias y Conectividad

Repasemos ahora algunos de los conceptos y definiciones fundamentales que rodean a las grficas.

Trayectorias

Hemos estado exponiendo algunos ejemplos de grficas en diferentes reas, y seguramente habrs notado

que surgen naturalmente algunos temas con el uso de grficas en estas reas. Uno de los ms notorios es

la idea de que las cosas viajan a travs de las aristas de una grfica, movindose de vrtice a vrtice en

secuencia podra ser un pasajero siguiendo una secuencia de vuelos de una aerolnea, una pieza de

informacin siendo pasada de persona a persona en una red social, o un usuario de computadora o pieza

de software visitando una secuencia de pginas web a travs de hipervnculos.

Esta idea motiva la definicin de camino en una grfica: un camino es simplemente una secuencia de

vrtices con la propiedad de que cada par consecutivo en la secuencia est conectado por una arista.

Algunas veces tambin es til pensar que el camino contiene no slo los vrtices sino tambin la secuencia

de aristas que conectan esos vrtices.



8

8

En el ejemplo anterior de Arpanet, la secuencia de vrtices MIT, BBN, RAND, UCLA es un camino, como

lo es tambin la secuencia CASE, LINCOLN, MIT, UTAH, SRI, UCSB. En esta definicin, un camino puede

repetir vrtices, por ejemplo: SRI, STAN, UCLA, SRI, UTAH, MIT. Pero la mayora de caminos que

consideraremos no hacen esto; si queremos enfatizar que el camino que estamos discutiendo no repite

vrtices podemos referirnos a l como una trayectoria.

Ciclos

Un tipo particularmente importante de camino es un ciclo, el cual informalmente es una estructura de

anillo como la de la secuencia de vrtices LINC, CASE, CARN, HARV, BBN, MIT, LINC.

Ms precisamente, un ciclo es un camino con al menos tres aristas, en la cual el primer vrtice y el ltimo

son el mismo; el resto de los vrtices son distintos. En la grfica de Arpanet se pueden encontrar muchos

ciclos: SRI, STAN, UCLA, SRI o SRI, STAN, UCLA, RAND, BBN, MIT, UTAH, SRI.

De hecho, cada arista en la red de Arpanet de 1970 pertenece a un ciclo, y esto fue hecho por diseo:

significa que si alguna arista falla todava habra una forma de llegar de un vrtice a cualquier otro.

De forma ms general, los ciclos en las redes de comunicaciones y transporte estn presentes a menudo

para permitir la redundancia para proporcionar rutas alternativas.

Tambin en las redes sociales de amistad notamos a menudo ciclos en la vida diaria. Cuando descubres,

por ejemplo, que el amigo de la secundaria del primo de tu esposa es alguien que trabaja con tu hermano,

ests hablando de un ciclo que te contiene a ti, a tu esposa, a su primo, a su amigo de la secundaria, a su

compaero de trabajo (tu hermano), y finalmente a ti de nuevo.

Conectividad o Conexidad

Dado una grfica, es natural preguntar si cada vrtice puede alcanzar a todos los dems vrtices a travs

de una trayectoria. De acuerdo a esto, podemos decir que una grfica es conexa cuando todos sus

vrtices estn conectados. Dos vrtices estn conectados si existe un camino que los une.

Por ejemplo, la grfica de Arpanet es conexa. De forma general, se espera que la mayora de redes de

comunicaciones y de transporte estn conectadas dado que su meta es mover trfico de un vrtice a otro.

Por otro lado, no existe una razn a priori para esperar que las grficas en otros casos estn conectadas

por ejemplo, en una red social, es razonable esperar que existan dos personas para los cuales no es

posible construir una trayectoria entre ellas. La siguiente figura muestra un ejemplo de una grfica

disconexa:



9

9

Componentes

La figura anterior hace visualmente aparente un hecho bsico acerca de las grficas disconexas: si una

grfica es disconexa, se divide naturalmente en un conjunto de piezas conexas, grupos de vrtices que

estn conectados cuando se les considera como grficas aisladas, de modo que no se traslapan. En la

misma figura anterior, puedes ver que la grfica consiste de tres de tales piezas: una que contiene los

vrtices A y B, otra que contiene los vrtices C, D, y E, y otra ms que contiene el resto de los vrtices.

Con el fin de precisar esta nocin, decimos que una componente conexa de una grfica (a menudo llamada

simplemente componente) es una subgrfica conexa maximal tal que:

a. Cada vrtice en el subconjunto tiene una trayectoria hacia cada uno de los otros

b. El subconjunto no es parte de un conjunto ms grande con la propiedad de que cada vrtice puede

llegar a cualquier otro.

Nota que tanto (a) como (b) son necesarios para formalizar la definicin intuitiva: (a) indica que el

componente est conectado internamente, y (b) indica que realmente es una pieza independiente de la

grfica, no una parte conexa de una pieza ms grande. Por ejemplo, al conjunto de vrtices F, G, H y J de

la figura anterior no lo podemos considerar como un componente, porque viola la parte (b) de la definicin:

aunque existen trayectorias entre todos los pares de vrtices, el conjunto pertenece a un conjunto ms

grande (vrtices F a M), en el cual tambin existen trayectorias para todos los pares.

El dividir una grfica en sus componentes es solamente una primera forma de describir su estructura.

Dentro de un componente dado, puede existir una estructura interna ms rica que sea importante para la

interpretacin de la red.

3.1.2. Caractersticas

Una grfica est formada por dos conjuntos, V el conjunto de vrtices que debe ser a lo ms

numerable (y en este caso podemos pedir que sea finito), y A el conjunto de aristas que est



10

10

formado por parejas de elementos de V. La grfica se define independientemente de la

representacin. Por ejemplo, las dos figuras siguientes representan la misma grfica.

Un camino del vrtice x al y en una grfica, es una lista de vrtices en la cual vrtices sucesivos

se conectan a travs de aristas. Por ejemplo BAFEG es una trayectoria de B a G en la grfica

anterior.

Una grfica es conexa si existe una trayectoria desde cada uno de los vrtices hacia todos los otros

vrtices.

Una grfica disconexa est formado de componentes conexos, por ejemplo la grfica de la figura

anterior tiene tres componentes conexos.

Una trayectoria es un camino en el cual ningn vrtice est repetido. Por ejemplo, BAFEGAC no es

una trayectoria simple.

Un ciclo es una trayectoria que es simple excepto que el primero y el ltimo vrtice son el mismo.

Por ejemplo, la trayectoria AFEGA es un ciclo.

Una grfica conexa sin ciclos se denomina rbol.

Un grupo de rboles disconexos entre s se denomina bosque.

Un rbol generador (spanning tree) es una subgrfica generadora a toda subgrfica que contiene a

todos los vrtices. Por ejemplo, las aristas AB AC AF FD DE EG forman un rbol generador para el

componente grande de la grfica anterior.

Si se agrega una arista a un rbol, se forma un nico ciclo.

Un rbol con v vrtices tiene exactamente v-1 aristas.

Si una grfica con v vrtices tiene menos de v-1 aristas, no es conexa. Si tiene ms de v-1 aristas,

debe tener un ciclo.

Estamos utilizando v para denotar el nmero de vrtices en una grfica y utilizaremos a para denotar el

nmero de aristas (edges en ingls). a puede variar desde 0 hasta

. Tambin se suele utilizar la

letra p para referirse a la cardinalidad del conjunto V.



11

11

Las grficas con relativamente pocas aristas son llamadas escasas.

Las grficas con una falta relativamente baja de las aristas posibles son llamadas densas.

Las grficas que hemos mostrado hasta el momento son llamados grficas no-dirigidas, el tipo ms

simple de grfica. Existen otros tipos de grficas ms complejos que tienen ms informacin asociada con

los vrtices y las aristas:

En las grficas ponderadas, se asignan cantidades (pesos o valores) a cada arista para

representar, por ejemplo, distancias o costos.

En las grficas dirigidas, las aristas son de un solo sentido: una arista puede ir de x a y pero no

de y a x.

Las grficas ponderadas dirigidas son llamadas a veces redes.

La informacin extra que contienen las grficas ponderadas y las dirigidas las hace obviamente un poco

ms difciles de manipular que las grficas simples no-dirigidas.

Representaciones en Computadora

Para poder procesar grficas con un programa de computadora, es necesario decidir cmo representarlos

dentro de la computadora. Discutiremos dos de las representaciones ms comunes; la seleccin de cul

usar depende principalmente de si la grfica es densa o escasa aunque, como es lo usual, la naturaleza de

las operaciones a efectuar juega un papel importante.

El primer paso para representar una grfica es mapear los nombres de los vrtices a nmeros enteros

entre 1 y v. La razn principal del mapeo es hacer posible el acceso rpido a la informacin

correspondiente a cada vrtice, a travs de un indexado de arreglos.

Se puede utilizar cualquier esquema estndar de bsqueda; por ejemplo, podemos trasladar los nombres

de los vrtices a enteros entre 1 y v manteniendo una tabla hash o un rbol binario que puede ser

examinado para encontrar el entero correspondiente a un determinado nombre de vrtice.

Recuerdas que estudiamos estas clases de algoritmos en la unidad anterior? Asumimos entonces que

una funcin indice est disponible para convertir nombres de vrtice a enteros entre 1 y v, y una funcin

nombre para convertir enteros a nombres de vrtice.

Para hacer los algoritmos fciles de seguir, utilizamos aqu nombres de vrtice de una letra, con la i-sima

letra del alfabeto correspondiendo al entero i. Aunque nombre e indice son simples en nuestros

ejemplos, su uso facilita la extensin de los algoritmos para manipular grficas con nombres reales de

vrtice por medio de las tcnicas de bsqueda que aprendiste.

La representacin ms directa de las grficas es la llamada matriz de adyacencia: se mantiene un arreglo v

por v de valores booleanos, con a[x][y] establecido en 1 si existe una arista del vrtice x al vrtice y, y

establecido en 0 en otro caso.



12

12

La matriz de adyacencia para la grfica que hemos estado usando se muestra a continuacin.

A B C D E F G H I J K L M

A 1 1 1 0 0 1 1 0 0 0 0 0 0

B 1 1 0 0 0 0 0 0 0 0 0 0 0

C 1 0 1 0 0 0 0 0 0 0 0 0 0

D 0 0 0 1 1 1 0 0 0 0 0 0 0

E 0 0 0 1 1 1 1 0 0 0 0 0 0

F 1 0 0 1 1 1 0 0 0 0 0 0 0

G 1 0 0 0 1 0 1 0 0 0 0 0 0

H 0 0 0 0 0 0 0 1 1 0 0 0 0

I 0 0 0 0 0 0 0 1 1 0 0 0 0

J 0 0 0 0 0 0 0 0 0 1 1 1 1

K 0 0 0 0 0 0 0 0 0 1 1 0 0

L 0 0 0 0 0 0 0 0 0 1 0 1 1

M 0 0 0 0 0 0 0 0 0 1 0 1 1

Notars que cada arista est representada en realidad por dos bits: una arista que conecta x y y est

representada por valores verdaderos tanto en a[x][y] como en a[y][x]. Puede ahorrarse espacio

almacenando solamente la mitad de esta matriz simtrica, pero los algoritmos resultan un poco ms

simples cuando se utiliza la matriz completa. Asimismo, es usualmente conveniente asumir que existe una

arista en cada vrtice con s mismo, as a[x][x] est establecido en 1 para x desde 1 a v.

Introduciendo una Grfica a la Computadora

Para introducir una grfica a la computadora, necesitamos convenir en un formato de entrada. Una

posibilidad es usar la matriz de adyacencia como el formato de entrada, pero esto resulta inapropiado para

grficas escasas. Usaremos entonces un formato ms directo: primero leemos los nombres de los vrtices,

y luego pares de nombres de vrtices (lo cual define las aristas).

Una manera sencilla de proceder es leer los nombres de los vrtices y guardarlos en una tabla hash o en

un rbol de bsqueda binaria y asignar a cada nombre de vrtice un entero que se usar para acceder a

los arreglos de vrtices indexados, como la matriz de adyacencia. A la lectura del i-simo vrtice se le

puede asignar el entero i.

Por simplicidad, primero leemos v y a, luego los vrtices y las aristas. Como alternativa, la entrada podra

ser organizada con un delimitador que separe los vrtices de las aristas, y entonces el programa podra

determinar v y a de la entrada.

El orden en el que aparecen las aristas no es importante, dado que cualquier ordenamiento de las aristas

representa la misma grfica y resulta en la misma matriz de adyacencia. Para construir en la computadora

la matriz de adyacencia, se puede utilizar el siguiente programa (en estas secciones detallaremos slo las

partes ms relevantes de los programas y usaremos algo de pseudocdigo para facilitar las explicaciones;

en la ltima seccin de la unidad encontrars programas completamente funcionales).

int V, A;



13

13

int a[maxV][maxV];

void matrizady(){

int j, x, y;

// Instrucciones para leer V y A

for (x = 1; x



14

14

ady[j] = z;

for (j = 1; j v = x; t->sig = ady[y]; ady[y] = t;

t = new vertice;

t->v = y; t->sig = ady[x]; ady[x] = t;

}

}

La figura siguiente muestra la representacin con estructura de adyacencia construida por el programa

anterior.

La representacin de lista de adyacencia es mejor para grficas escasas porque el espacio requerido es

menor comparado con el espacio requerido por la representacin de matriz de adyacencia.

Nota que, de nuevo, cada arista est representada dos veces. Es importante incluir ambas porque, de otra

manera, preguntas simples como Cules vrtices estn conectados directamente al vrtice x? no

pueden ser respondidas eficientemente.

Para esta representacin, el orden en el que las aristas aparecen en la entrada es muy importante:

determina el orden (junto con el mtodo de insercin de lista utilizado) en el cual los vrtices aparecen en

las listas de adyacencia. Debido a esto, la misma grfica puede ser representada de muy diversas formas

en una estructura de este tipo.

El orden en el cual las aristas aparecen en la lista de adyacencia afecta, a su vez, el orden en el cual las

aristas son procesadas por los algoritmos. Mientras que un algoritmo debe producir una respuesta correcta

sin importar cmo estn ordenadas las aristas en las listas de adyacencia, puede llegar a la respuesta a

travs de secuencias muy diferentes de clculos. Si hay ms de una respuesta correcta, los diferentes

rdenes de entrada pueden producir diferentes resultados de salida.



15

15

Algunas operaciones simples no son soportadas por esta representacin. Por ejemplo, si se desea eliminar

un vrtice x, y todas las aristas conectadas a l, no es suficiente eliminar vrtices de la lista de adyacencia:

cada vrtice en esta lista especifica otro vrtice cuya lista de adyacencia debe ser examinada para eliminar

un vrtice correspondiente a x. Este problema puede ser corregido enlazando los dos vrtices que

corresponden a una arista en particular y haciendo las listas de adyacencia doblemente enlazadas. As, si

una arista va a ser removida, los dos vrtices correspondientes a esa arista pueden ser eliminados

rpidamente. Por supuesto, estos enlaces extra son incmodos de procesar, y no deberan ser incluidos a

menos que se requieran operaciones como la eliminacin.

Tales consideraciones tambin aclaran por qu no utilizamos una representacin directa para las grficas:

una estructura de datos que modele la grfica exactamente, con vrtices representados por registros

asignados y listas de aristas conteniendo enlaces a los vrtices en lugar de nombres de vrtice. Sin un

acceso directo a los vrtices, las operaciones simples se vuelven desafiantes. Por ejemplo, para agregar

una arista a una grfica representado de esta manera, se tendra que buscar de alguna manera a travs de

la grfica para encontrar los vrtices.

Las grficas dirigidas y ponderadas se representan con estructuras similares. Para las grficas dirigidas,

todo es lo mismo, excepto que cada arista est representada slo una vez: una arista de x a y est

representada por un 1 en a[x][y] en la matriz de adyacencia o por la aparicin de y en la lista de

adyacencia de x dentro de la estructura de adyacencia.

Para las grficas ponderadas, de nuevo todo es lo mismo excepto que se llena la matriz de adyacencia con

pesos en lugar de valores booleanos (utilizando algn peso no existente para representar la ausencia de

una arista), o incluir en la estructura de adyacencia un campo para el peso de la arista dentro de los

registros de la lista de adyacencia.

Es a menudo necesario asociar otra informacin con los vrtices de una grfica para permitirle modelar

objetos ms complicados o para ahorrar informacin de control en algoritmos complicados. La informacin

extra asociada con cada vrtice puede ser acomodada utilizando arreglos auxiliares indexados por el

nmero de vrtice o haciendo ady un arreglo de registros en la representacin de estructura de

adyacencia.

La informacin extra asociada con cada arista puede ser colocada en los vrtices de la lista de adyacencia

(o en un arreglo a de registros en la representacin de matriz de adyacencia), o en arreglos auxiliares

indexados por el nmero de arista (esto requiere la numeracin de las aristas).

Recorrido en Profundidad

Cuando hablamos de redes y grficas, empezamos inmediatamente a hacernos preguntas: Es la grfica

conexa? Si no, Cules son sus componentes conexos? La grfica tiene un ciclo? Estos y otros

problemas pueden ser resueltos con diversos algoritmos. Discutiremos a continuacin un mtodo llamado

bsqueda en profundidad (depth-first search en ingls), el cual visita cada vrtice y revisa cada arista de

la grfica sistemticamente.



16

16

Comencemos por concentrarnos en la forma de examinar cada pieza de la grfica de una manera

organizada:

Utilizamos un arreglo vid[V] para registrar el orden en el que los vrtices son visitados.

Cada entrada o celda en el arreglo se inicializa con el valor de novisitado para indicar que ningn

vrtice ha sido visitado todava.

La meta es visitar sistemticamente todos los vrtices de la grfica, estableciendo en la entrada vid

correspondiente el id del vrtice i visitado, en el que id = 1, 2,, v. El siguiente programa utiliza una

funcin visitar que visita todos los vrtices del mismo componente conexo con el vrtice dado como

argumento.

void recorrer()

{

int k;

for (k = 1; k v] == novisitado)

visitar(t->v);

}



17

17

En la figura siguiente se puede seguir la operacin del algoritmo. Estn trazadas las llamadas recursivas

durante la funcin visitar. Cada componente conexo lleva a un rbol, denominado rbol de bsqueda

en profundidad del componente.

Es importante notar que este bosque de rboles de recorrido en profundidad es slo otra manera de trazar

la grfica: el algoritmo examina todos los vrtices y aristas de la grfica. Las lneas slidas indican que el

vrtice inferior fue encontrado por el algoritmo en la lista de aristas del vrtice superior y que no haba sido

visitado en ese momento, as que una llamada recursiva fue hecha. Las lneas punteadas corresponden a

aristas de vrtices que ya haban sido visitados, as que la prueba if en visitar fall, y la arista no fue

seguida con una llamada recursiva. Estos comentarios se aplican a la primera vez en que cada arista es

encontrada; la prueba if en visitar tambin evita que se siga la arista la segunda vez que es

encontrada.

Existen algoritmos similares que pueden utilizarse alternativamente como el de bsqueda en profundidad

no recursivo o el de bsqueda en amplitud.

Actividad 1. Fundamentos de redes

A travs de esta actividad podrs identificar dos tipos de bsqueda que se mencionan en el contenido,

pero no se definen (Bsqueda en Profundidad No Recursivo (Nonrecursive Depth-First Search) y

Bsqueda en Amplitud (Breadth-First Search).

Instrucciones:

1. Formen equipos de 4 o 5 integrantes.

2. Colabora con tu equipo en el diseo de una wiki que responder al ttulo: Algoritmos de Recorrido

3. Investiga sobre los siguientes temas:

a. Recorrido en Profundidad No Recursivo (Nonrecursive Depth-First Search).

i. Descripcin.

ii. Diferencia con el algoritmo Recorrido en Profundidad (Depth-First Search).



18

18

iii. Cdigo en C o en Java de la funcin bsica.

b. Recorrido en Anchura (Breadth-First Search).

i. Descripcin.

ii. Diferencia con el algoritmo Recorrido en Profundidad No Recursivo (Nonrecursive

Depth-First Search).

iii. Cdigo en C o en Java de la funcin bsica.

4. La wiki que ayudes a construir debe contener al menos, los siguientes elementos: introduccin,

desarrollo (informacin generada por ti), explicacin del funcionamiento de los algoritmos,

diferencia con el otro algoritmo que se menciona, el cdigo en C o en Java de la funcin bsica

(suele ser expresable en 15-20 lneas de cdigo), dos links para conocer ms algunos de los

temas, conclusiones, las fuentes de informacin que consultaste para el desarrollo de la misma y

los nombres de los participantes.

5. Participa, al menos con tres aportaciones.

6. Tienes la posibilidad de ingresar, modificar y eliminar informacin ingresada por ti y por tus

compaeros, es importante que respetes las aportaciones de tus compaeros y cualquier

modificacin sea con fundamentos.

.

3.2. Flujo

Ya que repasamos un poco la teora de grficas, que discutimos la forma en que las grficas pueden

representarse dentro de una computadora y que nos introdujimos a algoritmos que son capaces de

proporcionar respuestas a preguntas bsicas acerca de las grficas, podemos volver a lo que dio origen a

todo este trabajo: las redes.

Existe una infinidad de problemas originados por las redes, pero uno de los problemas tpicos es el del flujo

de materias primas u otros elementos a travs de ellas. Podemos considerar, por ejemplo, una red

petrolera con tubera de diversos tamaos interconectada de formas complejas con vlvulas controlando la

direccin del flujo en las uniones. Para simplificar el trabajo que iniciaremos acerca de esto podemos

suponer tambin que la red tiene una sola fuente (digamos, un campo petrolero) y un solo destino

(digamos, una refinera) a los cuales se conectan la tubera. Los entornos reales, por supuesto, pueden

tener varias fuentes y varios destinos, as que los algoritmos deben ajustarse a la situacin.

Cules son las configuraciones de vlvulas que maximizan la cantidad de petrleo fluyendo de la fuente al

destino? Interacciones complejas que implican el flujo de material en las uniones hacen que este problema

de flujo en una red no sea trivial en su solucin.

Este escenario general tambin puede ser usado para describir el flujo de trfico en las autopistas, de

materiales movindose dentro de las fbricas, etc. Se han estudiado muchas diferentes versiones del

problema, dependiendo de las situaciones prcticas en las que se presenta. Puedes ver que existe una



19

19

motivacin muy fuerte para encontrar un algoritmo eficiente que ofrezca una solucin adecuada. El flujo en

las redes es un ejemplo tpico de problemas del rea de investigacin de operaciones.

Existen mtodos matemticos complejos para tratar los problemas de investigacin de operaciones, pero la

solucin de problemas especficos como el del flujo en una red, est estrechamente relacionada a los

algoritmos de grficas, as que es posible desarrollar un programa que resuelva el problema utilizando las

herramientas algortmicas que ya hemos empezado a examinar. El problema contina siendo estudiado

activamente; la mejor solucin todava no ha sido encontrada y nuevos algoritmos siguen siendo

descubiertos.

3.2.1. Flujo mximo

Considera el diagrama idealizado de una pequea red de tuberas de petrleo que se muestra a

continuacin:

Las tuberas son de capacidad fija proporcional a su tamao y el petrleo puede fluir solamente de arriba

hacia abajo. Adems, vlvulas en cada unin controlan cunto petrleo pasa en cada direccin. Sin

importar el estado de las vlvulas el sistema alcanza un punto de equilibrio cuando la cantidad de petrleo

entrando al sistema por la parte superior es igual a la cantidad saliendo por la parte inferior (esta es la

cantidad que queremos maximizar), y cuando la cantidad de petrleo fluyendo hacia cada unin es igual a

la cantidad saliendo de ella. Medimos tanto el flujo como la capacidad de la tubera en trminos de

unidades enteras (por ejemplo, litros por segundo).

No es obvio inmediatamente que la configuracin de las vlvulas pueda afectar realmente el flujo mximo

total. La figura siguiente ilustra que s afecta.

Primero, supongamos que se abre la vlvula que controla el tubo AB, llenando ese tubo, el tubo BD, y casi

llenando DF, como se muestra en el diagrama izquierdo de la figura. A continuacin supongamos que el

tubo AC se abre y la vlvula C se mueve para cerrar el tubo CD y abrir el tubo CE (quizs el operador de la

vlvula D ha informado al operador de la vlvula C que ya no puede aceptar ms debido a la carga desde

B). El flujo resultante se muestra en el diagrama central de la figura: los tubos BD y CE estn llenos. Ahora,



20

20

el flujo podra ser incrementado en alguna medida enviando lo suficiente a travs de la trayectoria ACDF

para llenar el tubo DF, pero hay una mejor solucin, como se muestra en el tercer diagrama. Cambiando la

vlvula B para redirigir suficiente flujo para llenar BE, proporcionamos suficiente capacidad en el tubo DF

para permitir a la vlvula C abrir completamente el tubo CD. El flujo total entrando y saliendo de la red se

incrementa encontrando la configuracin adecuada de vlvulas.

Nuestro desafo es desarrollar un algoritmo que pueda encontrar la configuracin apropiada de vlvulas

para cualquier red. Adems, queremos estar seguros que ninguna otra configuracin de vlvulas permitir

un flujo mayor. Esta situacin puede ser modelada por una grfica dirigida.

Definimos una red como una grfica ponderada dirigida con dos vrtices distinguibles: uno sin aristas

apuntando hacia el interior (la fuente) y otro sin aristas apuntando hacia el exterior (el destino). Los pesos

en las aristas, que asumimos como no-negativos, se denominan capacidades de vrtice. Un flujo se

define como otro conjunto de pesos en las aristas de manera que el flujo en cada arista es igual a o menor

que la capacidad, y el flujo entrando en cada vrtice es igual al flujo saliendo de ese vrtice. El valor del

flujo es el flujo de la fuente. El problema del flujo de red es encontrar un flujo con valor mximo para

una red dada.

Las redes pueden ser representadas por medio de la matriz de adyacencia o por la lista de adyacencia que

utilizamos para grficas anteriormente. En lugar de un solo peso, dos pesos estn asociados con cada

arista, el tamao y el flujo. Estos pueden ser representados por dos campos en un vrtice de la lista de

adyacencia, como dos matrices en la matriz de adyacencia, o por dos campos dentro de un solo registro en

cualquier representacin. Aunque las redes son grficas dirigidas, los algoritmos necesitan atravesar las

aristas en la direccin equivocada, as que utilizamos una representacin de grfica no-dirigida: si existe

una arista de x a y con tamao s y flujo f, tambin mantenemos una arista de y a x con tamao s y flujo f.

En una representacin de lista de adyacencia, es necesario mantener enlaces conectando los dos vrtices

de lista que representan cada arista, de manera que cuando cambiemos el flujo en uno podamos

actualizarlo en el otro.

Podemos definir el problema del flujo mximo de una forma ms precisa como sigue.



21

21

Redes de Flujo y Flujos

Una red de flujo es una grfica dirigida en la cual cada arista tiene una capacidad

no-negativa .

Requerimos adems que si A contiene una arista , entonces no existe una arista en la direccin

inversa.

Si , entonces por conveniencia definimos , y no aceptamos auto-ciclos.

Distinguimos dos vrtices en una red de flujo: una fuente s y un destino t. Por conveniencia, asumimos

que cada vrtice se encuentra en alguna trayectoria de la fuente al destino. Esto es, para cada vrtice

, la red de flujo contiene una trayectoria . La grfica es por lo tanto conexa y, dado que cada

vrtice diferente de s tiene al menos una arista entrante, entonces | | | | .

Estamos listos ahora para definir los flujos ms formalmente.

Sea una red de flujo con una funcin de capacidad c. Sea s la fuente de la red, y sea t el destino.

Un flujo en G es una funcin con valor real que satisface las siguientes dos propiedades:

Restriccin de la capacidad: Para todo , se requiere .

Conservacin del flujo: Para todo { }, se requiere

Cuando , no puede haber flujo desde u a v, y

Llamamos a la cantidad no-negativa el flujo del vrtice u al vrtice v. El valor | | de un flujo f se

define como

| |

esto es, el flujo total saliendo de la fuente menos el flujo entrando a la fuente (aqu, la notacin | f | denota

el valor del flujo, no valor absoluto o cardinalidad.) Tpicamente, una red de flujo no tendr aristas hacia la

fuente, y el flujo hacia la fuente dado por la sumatoria

ser 0. Lo incluimos, sin embargo, porque cuando se introducen redes residuales, el flujo hacia la fuente se

vuelve significativo.



22

22

En el problema del flujo mximo, se nos da una red de flujo G con fuente s y destino t, y deseamos

encontrar un flujo de valor mximo.

La restriccin de capacidad dice simplemente que el flujo de un vrtice a otro debe ser no-negativo y que

no debe exceder la capacidad dada. La propiedad de conservacin del flujo dice que el flujo total entrando

un vrtice que no sea la fuente o el destino debe ser igual al flujo total saliendo de ese vrtice dicho

informalmente, el flujo de entrada es igual al flujo de salida.

3.2.2. Teorema del corte mnimo y flujo mximo

Teorema. En cualquier red, el flujo mximo que fluye de la fuente al destino, es igual a la

capacidad del corte mnimo que separa a la fuente del destino. Este corte mnimo de

separacin puede no ser nico.

En la figura siguiente se muestra una red de ejemplo que tiene varios cortes, cada uno con capacidad

diferente. El nmero que se muestra junto a cada arista representa su capacidad mxima.

La siguiente tabla contiene los cortes de separacin y sus capacidades.

Aristas en el corte de separacin Capacidad

{SA, SB} 17

{BE, BD, AD, CD, CT} 17

{CT, DT, ET} 16

{BE, CT, DT} Corte mnimo 14

El corte mnimo es el cuarto de la lista con una capacidad de 14 unidades; de acuerdo al teorema, tambin

es el flujo mximo que puede fluir de la fuente al destino. Como puedes ver, la esencia del teorema es

sencilla.

Un artculo de Lester Randolph Ford Jr. y de Delbert Ray Fulkerson (1962) discutiendo el problema del flujo

mximo estableci este famoso teorema. Para definirlo formalmente, necesitaremos de tres conceptos:

redes residuales, trayectorias de aumento, y cortes.



23

23

Redes Residuales

Dada una red de flujo G y un flujo f, la red residual Gf consiste de aristas con capacidades que representan

cmo se cambia el flujo en las aristas de G. Una arista de la red puede admitir una cantidad de flujo

adicional igual a la capacidad de la arista menos el flujo en esa arista. Si el valor es positivo, se pone esa

arista Gf con una capacidad residual de .

Las nicas aristas de G que estn en Gf son aquellas que pueden admitir ms flujo; las aristas cuyo flujo

iguala a su capacidad tienen , y no estn en Gf.

La red residual Gf tambin puede contener aristas que no estn en G, sin embargo. A medida que un

algoritmo manipula el flujo, con la meta de incrementar el flujo total, puede necesitar disminuir el flujo en

una arista particular. Para representar una posible disminucin de un flujo positivo en una arista en

G, se pone una arista en Gf con una capacidad residual ; esto es, una arista que

puede admitir un flujo en la direccin opuesta a , a lo ms cancelando el flujo en .

Estas aristas invertidas en la red residual permiten que un algoritmo devuelva flujo que ya ha enviado por

una arista. El devolver flujo por una arista es equivalente a disminuir su flujo, la cual es una operacin

necesaria en muchos algoritmos.

Ms formalmente, dada una red de flujo G = (V, A) con fuente s y destino t, un flujo f en G, y considerando

un par de vrtices , definimos la capacidad residual como

{

Trayectorias de Aumento

Dada una red de flujo G = (V, A) y un flujo f, una trayectoria de aumento p es una trayectoria simple de s a

t en la red residual Gf . Por la definicin de red residual, se puede incrementar el flujo en una arista (u, v) de

una trayectoria de aumento por hasta sin violar la restriccin de capacidad de (u, v) y (v, u) en la

red original G.

Llamaremos a la mxima cantidad por la cual se puede incrementar el flujo en cada arista en una

trayectoria de aumento p la capacidad residual de p, dada por

{ }.

Cortes de Redes de Flujo

Un corte (S, T) de una red de flujo G = (V, E) es una particin de V en S y T = V S tal que y . Si

f es un flujo, entonces el flujo neto f(S, T) a travs del corte (S, T) se define como



24

24

La capacidad del corte (S, T) es

Un corte mnimo de una red es un corte cuya capacidad es mnima sobre todos los cortes de la red.

La asimetra entre las definiciones de flujo y capacidad de un corte es intencional e importante. Para

capacidad, contamos solamente las capacidades de las aristas que van de S a T, ignorando las aristas en

la direccin opuesta. Para flujo, consideramos el flujo que va de S a T menos el flujo que va en la direccin

opuesta de T a S.

Versin Formal del Teorema del Corte Mnimo y Flujo Mximo

Si f es un flujo en una red de flujo G = (V, E) con fuente s y destino t, entonces las siguientes condiciones

son equivalentes:

1. f es un flujo mximo en G.

2. La red residual Gf no contiene trayectorias de aumento.

3. | | para algn corte de G.

Esto equivale a lo que enunciamos al principio de esta seccin: el valor del flujo mximo es igual a la

capacidad de un corte mnimo. Puedes encontrar todos los desarrollos y demostraciones matemticas de

este teorema en:

Cormen, T., Leiserson, C., Rivest, R., Stein, C. (2009) Introduction to Algorithms. 3rd Ed. The MIT Press.

Cambridge, Massachusetts USA.

3.2.3. Algoritmo de corte mnimo y flujo mximo

Ford y Fulkerson desarrollaron un mtodo para encontrar el flujo mximo alrededor del teorema.

Comenzando con un flujo cero, se aplica el mtodo repetidamente. Mientras que el mtodo pueda ser

aplicado, produce un aumento de flujo; si no puede ser aplicado, el flujo mximo ha sido encontrado.

Examinaremos el mtodo en trminos de la grfica de la siguiente figura.



25

25

Para simplificar, omitimos las flechas, dado que todas apuntan hacia abajo. El mtodo no est restringido,

por supuesto, a grficas que pueden ser trazadas con todas las aristas apuntando en una direccin.

Usamos estas grficas porque ayudan a entender el flujo de la red en trminos de lquidos fluyendo en

tubos.

Consideremos cualquier trayectoria dirigida (hacia abajo) a travs de la red (de la fuente al destino).

Claramente, el flujo puede ser incrementado por al menos la cantidad ms pequea de la capacidad no

utilizada en cualquier arista de la trayectoria, incrementando el flujo en todas las aristas de la trayectoria por

esa cantidad. En el diagrama izquierdo de la figura, esta regla se aplica a lo largo de la trayectoria ABDF;

luego en el diagrama central, es aplicada a lo largo de la trayectoria ACEF.

Como mencionamos anteriormente, podemos entonces aplicar la regla a lo largo de la trayectoria ACDF,

creando una situacin en la que todas las trayectorias dirigidas a travs de la red tienen al menos una

arista llena hasta su capacidad. Pero existe otra manera de incrementar el flujo: podemos considerar

trayectorias arbitrarias a travs de la red que pueden contener aristas que apuntan en la direccin

equivocada (del destino hacia la fuente a lo largo de la trayectoria). El flujo puede ser aumentado a lo largo

de tal trayectoria aumentando el flujo en aristas de la fuente al destino y disminuyendo el flujo en aristas del

destino a la fuente por la misma cantidad.

En el ejemplo, el flujo a travs de la red puede ser aumentado en 3 a lo largo de la trayectoria ACDBEF,

como se muestra en el tercer diagrama de la figura. Como describimos anteriormente, esto corresponde a

agregar 3 unidades de flujo a travs de AC y CD, luego desviando 3 unidades en la vlvula B de BD a BE y

EF. No perdemos ningn flujo en DF porque 3 de las unidades que venan de BD ahora vienen de CD.

Para simplificar la terminologa, llamaremos a las aristas que fluyen de la fuente al destino a lo largo de una

trayectoria particular aristas hacia adelante, y las aristas que fluyen del destino a la fuente aristas hacia

atrs. Nota que la cantidad por la cual el flujo puede ser aumentado est limitada por el mnimo de las

capacidades no usadas en las aristas hacia adelante y el mnimo de los flujos en las aristas hacia atrs.

Dicho de otra manera, en el nuevo flujo, al menos una de las aristas hacia adelante a lo largo de la

trayectoria se llena o al menos una de las aristas hacia atrs a lo largo de la trayectoria queda vaca.



26

26

Adems, el flujo no puede ser incrementado en cualquier trayectoria que contenga una arista hacia delante

llena o una arista hacia atrs vaca.

El prrafo anterior proporciona un mtodo para incrementar el flujo en cualquier red, a condicin de que

una trayectoria sin aristas hacia adelante llenas o aristas hacia atrs vacas pueda encontrarse. El punto

esencial del mtodo es la observacin de que si tal trayectoria no puede ser encontrada entonces el flujo es

mximo.

Propiedad. Si todas las trayectorias de la fuente al destino en una red tienen una arista hacia adelante

llena o una arista haca atrs vaca, entonces el flujo es mximo.

Para probar este hecho, examinamos la grfica e identifiquemos la primera arista hacia adelante llena o

hacia atrs vaca en cada trayectoria. Este conjunto de aristas corta la grfica en dos partes. En este

ejemplo, las aristas AB, CD, y CE conforman el corte. Para cualquier corte de la red en dos partes,

podemos medir el flujo a travs del corte: el total del flujo en las aristas que van de la fuente al destino.

En general, las aristas pueden ir en ambas direcciones a travs del corte: para obtener el flujo a travs del

corte, el total del flujo en las aristas yendo en la otra direccin deben ser restadas. Nuestro corte de

ejemplo tiene un valor de 12, el cual es igual al flujo total para la red. Resulta que cuando el flujo del corte

es igual al flujo total, sabemos no solamente que el flujo es mximo, sino tambin que el corte es mnimo

(esto es, cualquier otro corte tiene al menos un flujo tan alto que lo cruza). Esto corresponde al teorema de

corte mnimo flujo mximo: el flujo no puede ser mayor (de otra manera el corte tendra que ser mayor

tambin), y no existen cortes menores (de otra forma el flujo tendra que ser tambin menor).

El mtodo Ford y Fulkerson puede ser resumido como sigue: empieza con flujo cero por doquier e

incrementa el flujo a lo largo de cualquier trayectoria de la fuente al destino que no tenga aristas hacia

delante llenas o aristas hacia atrs vacas, continuando hasta que no existan tales trayectorias en la red.

Esto no es un algoritmo en el sentido usual, dado que el mtodo para encontrar trayectorias no est

especificado, y cualquier trayectoria puede ser usada.

Por ejemplo, uno puede basar el mtodo en la intuicin que entre ms larga la trayectoria, la red est ms

llena, de manera que las trayectorias largas deberan ser preferidas. Pero el ejemplo clsico que se

muestra en la siguiente figura demuestra que se debe tener cuidado con esto.



27

27

En esta red, si la primera trayectoria escogida es ABCD, entonces el flujo es aumentado en slo 1.

Entonces la segunda trayectoria escogida puede ser ACBD, de nuevo aumentando el flujo en 1, y dejando

una situacin idntica a la situacin inicial, excepto que los flujos en las aristas exteriores son aumentados

en uno. Cualquier algoritmo que escoja estas dos trayectorias (por ejemplo, uno que busque las

trayectorias largas) continuara con esta estrategia, requiriendo 1000 pares de iteraciones antes de que el

flujo mximo sea encontrado. Si los nmeros en los lados fueran un billn, entonces se usaran dos billones

de iteraciones. Obviamente, esta es una situacin indeseable, dado que las trayectorias ABC y ADC dan el

flujo mximo en slo dos pasos. Para que el algoritmo sea til, debemos evitar que el tiempo de ejecucin

sea tan dependiente de la magnitud de las capacidades. Afortunadamente, este problema puede ser

eliminado fcilmente:

Propiedad. Si la trayectoria ms corta disponible de la fuente al destino se utiliza en el mtodo Ford y

Fulkerson, entonces el nmero de trayectorias utilizadas antes de que se encuentre el flujo mximo en una

red de V vrtices y A aristas debe ser menor que VA.

Este hecho fue probado por Edmonds y Karp en 1972.

Para esto se puede utilizar una versin modificada apropiadamente del algoritmo de recorrido en anchura

que mencionamos en la seccin 3.1.2.

Los algoritmos bsicos que usan el mtodo de Ford y Fulkerson estn ampliamente desarrollados por

varios autores. Por ejemplo, en el libro de Heineman, G., Pollice, G., Selkow, S. Algorithms in a Nutshell.

(2009) OReilly Media, Inc. 1st Ed. USA puedes encontrar inclusive el cdigo en Java. Sera un buen

ejercicio que implementaras el algoritmo en tu computadora:

Tambin puedes experimentar interactivamente en estos dos sitios con el algoritmo de Ford y Fulkerson:

http://people.cs.pitt.edu/~kirk/cs1501/animations/Network.html

http://www.cse.yorku.ca/~aaw/Wang/MaxFlowStart.htm

Al principio slo se conocan algoritmos eficientes para el flujo mximo que trabajaban encontrando

trayectorias de aumento, ya sea una trayectoria a la vez (como en el algoritmo original de Ford and

Fulkerson) o todas las trayectorias de aumento de longitud ms corta a la vez (mtodo de Dinic). Ms tarde,

fue introducido un mtodo alternativo basado en el concepto de preflujo de Karzanov, el cual presentamos

desarrollado en la ltima seccin de la unidad.

En este mtodo, para un vrtice fuente s dado y un vrtice destino t, el algoritmo comienza con un preflujo

inicial en el que todas las aristas de s tienen capacidad residual cero, produciendo excesos en los vrtices

adyacentes de s. Los excesos son empujados hacia t, mientras que se satisface la restriccin que el flujo

de entrada debe ser igual al flujo de salida en cada vrtice. Los excesos que no pueden alcanzar el destino

debido a las restricciones de capacidad son regresados a s. El algoritmo termina cuando ya no hay ms

excesos.



28

28

El algoritmo y su anlisis son simples e intuitivos, aunque el algoritmo se ejecuta tan rpido para grficas

de cualquier densidad como cualquier otro mtodo conocido o ms cuando se incorporan estructuras

dinmicas de datos. Un punto extra a favor es que el algoritmo tambin admite implementaciones

distribuidas y paralelas eficientes, adecuadas para los nuevos entornos de cmputo.

En la seccin 3.4.1. Solucin de Problemas de Redes se presenta el desarrollo de este algoritmo

incluyendo el pseudocdigo y el cdigo en Java del programa, as como una corrida de ejemplo con sus

resultados. Te recomendamos que lo pruebes en tu IDE Eclipse con otros ejemplos que propongas.

El artculo original (en ruso) en el que se presenta este mtodo es el siguiente:

Karzanov, A. V. (1974) Determining a Maximal Flow in a Network by the Method of Preflows. Soviet Math.

Dokl., 15, No.2, 434-437.

Y puede descargarse de: http://alexander-karzanov.net/flows&multiflows.html

Un artculo en ingls que discute detalles del algoritmo y que puede encontrarse en internet es el siguiente:

Goldberg, A., Tarjan, R. (1988) A New Approach to the Maximum-Flow Problem. Journal of the Association

for Computing Machinery, Vol. 35, No. 4.

Actividad 2. Teoremas y algoritmos de flujo

A travs de lo aprendido en la seccin 3.2.3. Algoritmos de corte mnimo y flujo mximo, realiza el

siguiente reporte de investigacin tomando en cuenta el algoritmo de Ford y Fulkerson. Y las instrucciones

mencionadas a continuacin.

Instrucciones

1. Escribe un reporte que llevar por nombre Teoremas y algoritmo de flujo

2. Investiga sobre los siguientes temas:

a. Algoritmo de Ford-Fulkerson.

i. Descripcin.

ii. Pseudocdigo

3. Guarda tu documento con la siguiente nomenclatura MCOM1_U3_A2_XXYZ. Sustituye las XX por

las dos primeras letras de tu primer nombre, la Y por la inicial de tu apellido paterno y la Z por la

inicial de tu apellido materno.

4. Enva tu documento a tu Facilitador(a) y espera su retroalimentacin



29

29

3.3. Conexidad

En una grfica conexa hay al menos una trayectoria entre cada par de sus vrtices. Un vrtice o una arista

tienen la propiedad de destruir la conexidad de la grfica si cuando se elimina uno de los dos, o ambos, la

grfica se convierte en disconexa. Consideremos por ejemplo una red de comunicaciones representada por

la grfica que se muestra en la siguiente figura. Los vrtices corresponden a centros de comunicacin y las

aristas a canales de comunicacin.

Si se elimina el vrtice v, se rompe la comunicacin. Esto implica que en esta red el centro representado

por el vrtice v tiene la propiedad de destruir el sistema de comunicaciones, as que la red depende de la

conexidad.

Conexidad

En el siguiente diagrama, la grfica de la izquierda tiene dos piezas, mientras que la grfica de la derecha

slo tiene una.

Pongamos esta observacin en trminos rigurosos.

Una grfica es conexa si para cada par de vrtices u y v, la grfica contiene una trayectoria con

puntos extremos u y v como sub-grfica.

La grfica de la izquierda no es conexa porque no hay una trayectoria de cualquiera de los tres vrtices

superiores a cualquiera de los dos vrtices inferiores. Sin embargo, la grfica de la derecha es conexa

porque existe una trayectoria entre cada par de vrtices.



30

30

Una sub-grfica conexa mxima se denomina componente conexo. (Por mxima, queremos decir que el

incluir cualesquiera vrtices adicionales volver disconexa la sub-grfica.) La grfica de la izquierda tiene

dos componentes conexos, el tringulo y la arista independiente. La grfica de la derecha es conexa

completamente as que tiene un solo componente conexo.

Teorema de Conexidad

Cada grfica tiene al menos | | | | componentes conexos.

Corolario. Toda grfica conexa con n vrtices tiene al menos n-1 aristas.

Conceptos Bsicos

Vrtice de corte: Sea G una grfica con k(G) componentes. Un vrtice v de G es denominado vrtice de

corte de G si . Por ejemplo, en la grfica de la siguiente figura, los vrtices u y v son

vrtices de corte.

Arista de corte: Una arista a de una grfica G es denominada arista de corte si

. En la grfica de la siguiente figura, e y f son aristas de corte.

Las siguientes observaciones son las consecuencias inmediatas de las definiciones anteriores:

1. La remocin de un vrtice puede incrementar el nmero de componentes en una grfica por al

menos uno.

2. Cada vrtice no-colgante de un rbol es un vrtice de corte.

3. La remocin de una arista puede incrementar el nmero de componentes por a lo ms uno.

4. Los vrtices finales de una arista de corte son vrtices de corte si su grado es mayor que uno.



31

31

Lo siguiente caracteriza los vrtices de corte:

Si G(V, A) es una grfica conexa, entonces v es un vrtice de corte si existen vrtices { } tales

que cada trayectoria en G pasa a travs de v.

Lo siguiente caracteriza las aristas de corte:

Para una grfica conexa G, las siguientes declaraciones son equivalentes:

a. a es una arista de corte de G.

b. Si , existe una particin del subconjunto de aristas { } para con y

.

3.3.1. Conexidad puntual

La conexidad puntual (o de vrtices) k(G) de una grfica conexa G (que no sea una

grfica completa) es el nmero mnimo de vrtices cuya eliminacin desconecta G.

Recuerda que una grfica completa es una grfica no dirigida en la que se conecta cada par de vrtices

distintos por una arista nica.

Cuando , se dice que la grfica es k-conexa (o k-vrtices conexa). Cuando se elimina un vrtice,

tambin se deben eliminar las aristas que inciden en l.

Por ejemplo, consideremos las siguientes grficas:

La grfica G1 puede ser desconectada eliminando un solo vrtice (ya sea b o c). Esta grfica tiene una

conexidad puntual de 1.

La grfica G2 puede ser desconectada eliminando un solo vrtice (ya sea c o d). La grfica tiene una

conexidad puntual de 1.

La grfica G3 puede ser desconectada eliminando slo un vrtice: el c. La grfica tiene una conexidad

puntual de 1.



32

32

La grfica G4 no puede ser desconectada eliminando un solo vrtice, pero la eliminacin de dos vrtices no

adyacentes (tales como b y c) la desconectan. La grfica tiene una conexidad puntual de 2.

Conjunto de Vrtices de Corte

Un conjunto de vrtices de corte de una grfica conexa es un conjunto S de vrtices con las siguientes

propiedades:

La eliminacin de todos los vrtices en S desconecta G.

La eliminacin de algunos (pero no todos) de los vrtices en S no desconecta G.

Consideremos la siguiente grfica

Podemos desconectar la grfica eliminando los vrtices b y e, pero no podemos desconectarla eliminando

slo uno de ellos. El conjunto de vrtices de corte de G es {b, e}.

Nota que la conexidad puntual k(G) no excede la conexidad lineal (G) (la veremos en la siguiente seccin).

Esto se mantiene para todas las grficas conexas.

Existe una desigualdad entre descubierta por Whitney en 1932 que dio origen al

siguiente teorema:

Teorema. Para toda grfica G conexo, se cumple que

Donde es el grado mnimo de los vrtices en G.

Recuerda que el grado de un vrtice es el nmero de aristas incidentes en el vrtice, con los ciclos

contados dos veces.

Pero es ciertamente posible para ambas desigualdades en la expresin anterior que sean desigualdades

estrictas, esto es

Por ejemplo, en la siguiente grfica



33

33

Y la siguiente grfica tiene

3.3.2. Conexidad lineal

La conexidad lineal (o de aristas) (G) de una grfica conexa G es el nmero mnimo

de aristas que cuando son removidas desconectan G.

Cuando , se dice que la grfica G tiene una conexidad lineal k.

Si se tienen, por ejemplo, las siguientes grficas

Su conexidad lineal es como sigue:

G1 tiene una conexidad lineal de 1




G1 puede ser desconectado (dividido en dos componentes) removiendo una de las aristas: bc o bd. Estas

aristas son denominadas puente.



34

34

Puente. Un puente es una sola arista cuya remocin desconecta un grfica.

G2 puede ser desconectado eliminando una sola arista, cd. Por lo tanto, la arista cd es un puente.

G3 no puede ser desconectado eliminando una sola arista, pero la remocin de dos aristas (tales como ac y

bc) lo desconecta.

G4 puede ser desconectado eliminando dos aristas tales como ac y cd.

Conjunto de Aristas de Corte

El conjunto de aristas de corte de una grfica conexa G es un conjunto de aristas S con las siguientes

propiedades:

La eliminacin de todas las aristas en S desconecta G.

La eliminacin de algunas (pero no todas) de las aristas en S no desconecta G.

Consideremos, por ejemplo, la siguiente grfica:

Podemos desconectar G eliminando tres aristas: bd, be, y ce, pero no podemos desconectarlo eliminando

slo dos de ellas. Nota que un conjunto de corte es un conjunto de aristas en el cual ninguna arista es

redundante.

La conexidad lineal para una grfica no conexa es cero, (G) = 0, mientras que si la grfica es conexa y

posee un puente, entonces (G) = 1.

En la seccin 3.4.1. Solucin de Problemas de Redes encontrars el pseudocdigo, el cdigo en Java y

una corrida de ejemplo de un algoritmo que encuentra la conexidad lineal de una grfica conexa no-dirigido

de n vrtices resolviendo n problemas de flujo mximo de red. Te recomendamos que experimentes con l

en tu IDE Eclipse.

3.3.3. Teorema de Menger

Dado que un par determinado de vrtices en una grfica puede ser conectado por muchas trayectorias, es

natural preguntarse cmo puede medirse el grado de conexidad entre ellos.



35

35

Una manera de medir su conexidad es determinar el mximo nmero de esas trayectorias que son

"independientes" una de otra, esto es, que no comparten otros vrtices considerndolas por pares.

Otra manera de medir su conexidad es determinar el mnimo nmero de vrtices cuya eliminacin

de la grfica destruye todas las trayectorias entre el par de vrtices dado.

El teorema de Menger establece que para cada par de vrtices no adyacentes estas dos medidas son

iguales. Una formulacin equivalente del teorema establece que si V y W son conjuntos de vrtices no

vacos en una grfica, entonces el nmero mximo de trayectorias internamente disjuntas V-W es igual al

nmero mnimo de vrtices cuya eliminacin destruye todas esas trayectorias. Estamos hablando de la

conexidad puntual.

El teorema es un resultado del desarrollo de la conexidad en grficas no-dirigidas. Karl Menger lo demostr

en 1927 para la conexidad puntual, pero tambin para la conexidad lineal. La versin del teorema para la

conexidad lineal fue generalizada ms tarde por un teorema que ya estudiaste: el del corte mnimo flujo

mximo.

Teorema de Menger para la Conexidad Puntual

Sean v y w dos vrtices no adyacentes en una grfica G. Un conjunto S de vrtices es un conjunto de corte

v-w si v y w yacen en componentes diferentes de G S; esto es, si cada trayectoria v-w contiene un vrtice

en S. El orden mnimo de un conjunto de corte v-w es denominado conexidad v-w y es denotado por

Para dos vrtices cualesquiera v y w, una coleccin de trayectorias v-w es considerada internamente

disjunta si las trayectorias son disjuntas por pares, excepto para los vrtices v y w. El nmero mximo de

trayectorias internamente disjuntas v-w se denota por . Dado que cada trayectoria en ese conjunto

debe contener un vrtice diferente de todo conjunto de corte v-w, es claro que .

Dos trayectorias son internamente disjuntas (algunas personas las llaman puntualmente disjuntas o

independientes) si no tienen ningn vrtice en comn, excepto el primero y el ltimo.

Consideremos, por ejemplo, el grfico siguiente

Es fcil verificar que tanto como son 3. El que ambos parmetros sean iguales en este caso

no es coincidencia, y el hecho de que esto es cierto en general es el contenido de una versin del teorema

de Menger. Comprueba el resultado encontrando las tres trayectorias que no tienen vrtices en comn



36

36

excepto el inicial y el final, y un conjunto de corte puntual que contiene al menos tres vrtices y separa la

grfica al eliminarlos (no encontrars un conjunto que contenga menos de tres vrtices).

Teorema de Menger para la Conexidad Puntual. Si v y w son vrtices no adyacentes en una grfica G,

entonces el nmero mximo de trayectorias internamente disjuntas v-w es igual al nmero de vrtices de

un conjunto mnimo de corte v-w.

Teorema de Menger para la Conexidad Lineal

La versin puntual del teorema de Menger discutida en la seccin anterior tiene analogas para el caso de

la conexidad lineal. Sean v y w dos vrtices en una grfica G. Un conjunto S de aristas es un conjunto de

aristas de corte v-w si v y w estn en componentes diferentes de G S; esto es, si cada trayectoria v-w

contiene una arista de S. La mxima cardinalidad de un conjunto de corte lineal v-w es la conexidad lineal v-

w y es denotada por .

El mximo nmero de trayectorias lineales disjuntas v-w en G se denota por . Dado que cada una de

tales trayectorias debe contener una arista de cada conjunto de corte lineal v-w, .

Dos trayectorias son linealmente disjuntas si no tienen ninguna arista en comn.

Por ejemplo, consideremos de nuevo la siguiente grfica

Es fcil ver que tanto como son 5. El que los dos parmetros sean iguales en este caso no

es de nuevo, una mera coincidencia, y el hecho que esto es cierto en general es la versin local lineal del

teorema de Menger. Comprueba el resultado encontrando las cinco trayectorias que no tienen aristas en

comn, y un conjunto de corte lineal que contiene al menos cinco aristas y separa la grfica al eliminarlas

(no encontrars un conjunto que contenga menos de cinco aristas).

Teorema de Menger para la Conexidad Lineal. Para cualesquiera vrtices v y w en una grfica G,

.

3.4. Programacin

En esta seccin presentamos el desarrollo completo de dos algoritmos: uno que resuelve el problema del

flujo mximo en una red, y el otro que encuentra la conexidad lineal de una grfica. Encontrars tanto el

pseudocdigo como el cdigo en Java que puedes probar en tu entorno IDE Eclipse.



37

37

3.4.1. Solucin de problemas de redes

1. Teorema del Corte Mnimo y Flujo Mximo

Pseudocdigo:

Paso 1.

Flujo mximo y corte mnimo.

Paso 2.

Entradas: El nmero de vrtices vertice y el nmero de aristas aristas, vrtice de inicio o fuente fuente

y el vrtice final, sumidero o destino destino, valores de la red: vrtices de p[ ] a q[ ]; la capacidad de

cada arista cap[ ].

Salidas: cantidad de flujo de cada vrtice flujovertice[], cantidad de flujo por cada arista flujoarista[],

vrtices del corte mnimo cortemin[].

1. Inicio.

2. Inicializacin de variables

cortemin[vertice+1] 0

flujovertice[vertice+1] 0

flujoarista[aristas+aristas+1] 0

primarista[vertice+1] 0

mapeoi[vertice+1] 0

mapeoj[vertice+1] 0

flujo 0, aux 0, aristas2 0, NY 0, i 0, j 0

entrada 0, salida 0, parm 0, aristas1 0, cont1 0, cont2 0

fin 0, NP 0, NQ 0, NU 0, NV 0, NW 0, NX 0

termino false, A false, B false, C false, G false

D false, E false, F false.

3. Se empieza con un preflujo en donde las aristas de la fuente tienen una capacidad residual de cero,

produciendo excesos en los vrtices adyacentes a la fuente.

4. Mientras el flujo de entrada sea igual al flujo de salida del vrtice

Los excesos son conducidos hasta el destino

Si los excesos no alcanzan a llegar al destino, son regresados a la fuente.

5. Si ya no hay excesos.

Fin.

6. Fin.

Ejemplo:



38

38

Solucin (Programa en Java):

package maxflow;

public class Test extends Object{

public static void main(String args[]) {

int vertice = 11, aristas = 18;

int fuente = 1, destino = 11;

//para p,q y cap, la cantidad de datos esta dada por: 2*aristas+1

int p[] = {0, 1, 1, 1, 2, 3, 3, 3, 3, 4, 5, 5, 6, 6, 7, 8, 9, 10,

10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

int q[] = {0, 2, 3, 4, 5, 2, 5, 7, 6, 7, 9, 8, 9, 7, 10, 11, 8, 9,

11,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

int cap[] = {0, 6, 8, 4, 8, 3, 2, 14, 3, 10, 1, 10, 10, 12, 6, 8, 9, 10,

12,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

int cortemin[] = new int[vertice+1];

int flujovertice[] = new int[vertice+1];

int flujoarista[] = new int[aristas+aristas+1];

Maxflow.FlujoMaxCorteMin(vertice,aristas,p,q,cap,fuente,destino,cortemin,flujoarista,

flujovertice);

System.out.print("Vrtices del corte mnimo: ");

for (int i = 1; i



39

39

}

////////////////////////////////////////////////////////////////////////////////////////

package maxflow;

public class Maxflow {

//valores de retorno

public static void FlujoMaxCorteMin(int vertice, int aristas, int p[],

int q[], int cap[], int fuente, int destino,

int cortemin[], int flujoarista[], int flujovertice[]){

int primarista[] = new int[vertice+1];

int mapeoi[] = new int[vertice+1];

int mapeoj[] = new int[vertice+1];

int flujo, aux, aristas2, NY, i, j;

int entrada = 0, salida = 0, parm = 0, aristas1 = 0, cont1 = 0, cont2 = 0;

int fin = 0, NP = 0, NQ = 0, NU = 0, NV = 0, NW = 0, NX = 0;

boolean termino, A, B, C, G;

boolean D = false, E = false, F = false;

// Creacin de aristas sustitutas

j = aristas;

for (i = 1; i



40

40

while (true) {

if (!B) {

if ((aux < 0) && A) {

if (aux != -1) {

if (NY < 0) NP++;

NQ = cont2;

cont2 = NP;

aux = -1;

}

else {

if (NY 1) {

cont1--;

cont2 = cont1;

A = false;

continue etiqueta2;

}

if (aristas1 == 1)

aux = 0;

else {

NP = aristas1;

aristas1--;

NQ = 1;

aux = 1;

}

}

else

aux = 2;

}

}

else {

if (A)

if (aux > 0) {

if (aux 1) {

cont1--;



41

41

cont2 = cont1;

A = false;

continue etiqueta2;

}

if (aristas1 == 1)

aux = 0;

else {

NP = aristas1;

aristas1--;

NQ = 1;

aux = 1;

}

}

}

}

}

G = false;

C = false;

if ((aux < 0) && !B) {

NY = p[NP] - p[NQ];

if (NY == 0) NY = q[NP] - q[NQ];

continue etiqueta2;

}

else {

if ((aux > 0) || B) {

// intercambio de dos aristas

B = false;

NY = p[NP];

p[NP] = p[NQ];

p[NQ] = NY;

flujo = cap[NP];

cap[NP] = cap[NQ];

cap[NQ] = flujo;

NY = q[NP];

q[NP] = q[NQ];

q[NQ] = NY;

flujo = flujoarista[NP];

flujoarista[NP] = flujoarista[NQ];

flujoarista[NQ] = flujo;

if (aux > 0)

continue etiqueta2;

if (aux == 0) {

C = true;

}

else {

mapeoj[NV] = NQ;

G = true;

}

}

else

if (termino) {

//Obtencin del flujo mximo en cada arista

j = 0;

for (i = 1; i 0) {

j++;

p[j] = p[i];



42

42

q[j] = q[i];

flujoarista[j] = flujoarista[i];

}

flujoarista[0] = j;

return;

}

}

if (!G && !C) {

//Realiza el cruce de referencias entre aristas

for (i = 1; i aristas2)

break;

NV = q[fin];

flujo = cap[fin] - flujoarista[fin];

if ((cortemin[NV] != 0) || (flujo == 0))

continue;

if (NV != destino) {

salida++;

mapeoi[salida] = NV;

}

cortemin[NV] = -1;

}

}

if (cortemin[destino] == 0) {

// Salidas

for (i = 1; i



43

43

for (i=1; i



44

44

if (!G) {

if (!F) {

if (!D && !E)

NU = mapeoi[NX];

if ((flujovertice[NU] 0);

flujovertice[NU] = -1;

E = true;

continue etiqueta4;

}



45

45

fin = cortemin[NU] + 1;

F = true;

continue etiqueta4;

}

for (i = 1; i = 0) {

q[i] = NV;

j = p[i];

cap[i] -= flujoarista[j];

flujo = flujoarista[i] - flujoarista[j];

flujoarista[i] = flujo;

Documents

U3._Redes