u3._redes.pdf
DESCRIPTION
RedesTRANSCRIPT
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
1
1
Universidad Abierta y a Distancia de México
Licenciatura en Matemáticas
Computación I
6° Cuatrimestre
Unidad 3. Redes
Clave:
050920621/060920621
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
2
2
Índice
Presentación de la unidad .......................................................................................................................... 3
Propósitos ................................................................................................................................................... 3
3.1. Fundamentos ........................................................................................................................................ 3
3.1.1. Conceptos Básicos .......................................................................................................................... 4
3.1.2. Características ................................................................................................................................. 9
Actividad 1. Fundamentos de redes......................................................................................................... 17
3.2. Flujo ..................................................................................................................................................... 18
3.2.1. Flujo Máximo .................................................................................................................................. 19
3.2.2. Teorema del Corte Mínimo y Flujo Máximo .................................................................................... 22
3.2.3. Algoritmo de Corte Mínimo y Flujo Máximo .................................................................................... 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. Programación ..................................................................................................................................... 36
3.4.1. Solución de Problemas de Redes .................................................................................................. 37
Actividad 3. Análisis de conexidad .......................................................................................................... 49
Autoevaluación .......................................................................................................................................... 50
Evidencia de Aprendizaje. Programación de algoritmos para resolver problemas de redes .............. 51
Cierre de la Unidad .................................................................................................................................... 51
Para saber más .......................................................................................................................................... 51
Fuentes de consulta .................................................................................................................................. 52
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
3
3
Presentación de la unidad
Las redes aparecen en casi cualquier área del quehacer humano, desde los circuitos eléctricos hasta las
redes sociales, y requieren soluciones para sus problemas. En esta unidad tendrás la oportunidad de
aprender los fundamentos de las redes para que seas capaz de analizarlas y proponer soluciones a sus
problemas de flujo.
La Teoría de gráficas aporta una plataforma para representar las redes en el ámbito matemático.
Aprenderás conceptos, teoremas y algoritmos para computadora alrededor de esta teoría que te ayudarán
a resolver problemas de las representaciones de las redes.
También estudiarás conceptos, métodos y algoritmos que te permitirán analizar la conexidad de las
gráficas. Finalmente conocerás el código ejecutable en una computadora de algoritmos relacionados con
gráficas y flujo en redes.
Propósitos
Al finalizar esta unidad serás capaz de:
Identificar los fundamentos de las redes.
Identificar teoremas y algoritmos de flujo en las redes.
Analizar la conexidad de gráficas.
Programar algoritmos para resolver problemas de redes.
Competencia específica
Utilizar algoritmos sobre gráficas dirigidas para determinar flujos y rutas mediante herramientas
informáticas.
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 específica 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.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
4
4
Dado un conjunto de solicitantes que han sido entrevistados para un conjunto de puestos
disponibles, encontrar un esquema que maximiza el número de solicitantes seleccionados para los
trabajos para los cuales están calificados.
Determinar la forma más efectiva en costo para embarcar bienes desde un conjunto de fábricas
proveedoras hacia un conjunto de tiendas minoristas que venden esos bienes.
Determinar la forma más efectiva en costo para embarcar bienes desde un conjunto de fábricas
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 máximo soportado por la red.”
Como un ejemplo más, podemos estar examinando un mapa de rutas de una línea aérea y formulando
preguntas como ¿Cuál es la forma más rápida de llegar de esta ciudad a esta otra? O quizás estamos
interesados en la manera más barata de llegar, no en el tiempo. Para responder a estas preguntas
necesitamos información acerca de las interconexiones entre los objetos.
Los circuitos eléctricos son otro ejemplo de la importancia de las conexiones entre objetos. Los dispositivos
eléctricos pueden ser representados y procesados dentro de una computadora para responder preguntas
simples como “¿Ya todo está conectado? O preguntas más complejas como ¿Funcionará este circuito si se
construye?
La estructura o patrón de interconexión de una red puede ser representada por una gráfica. Las
propiedades de la gráfica de una red se relacionan a menudo con las características específicas de esa
red; por ejemplo, siendo el ruteo una funcionalidad esencial en muchas redes, la complejidad
computacional del ruteo de la trayectoria más corta depende de la cuenta de saltos en la gráfica
subyacente. La Teoría de Gráficas es una rama de las matemáticas iniciada por Euler en 1736 y ha
encontrado muchas aplicaciones en la ingeniería y en la ciencia para resolver problemas de redes.
3.1.1. Conceptos básicos
En Matemáticas discretas tuviste la oportunidad de trabajar con la teoría de gráficas, así que sólo
revisaremos a continuación algunos conceptos que seguramente ya conoces y que conectaremos con
representaciones en computadora; utilizaremos más adelante esas representaciones para desarrollar
algoritmos capaces de resolver problemas de redes.
Una gráfica consiste de un conjunto de objetos llamados vértices, con ciertos pares de estos objetos
conectados por enlaces llamados aristas (edges, en inglés). Por ejemplo, la gráfica de la figura siguiente
contiene cuatro vértices (A, B, C, D), con B conectado a cada uno de los otros tres vértices, y C y D
conectados también. Decimos que dos vértices son vecinos si están conectados por una arista.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
5
5
Nota. La expresión “vértice” es propia de la Teoría de Gráficas; en la Teoría de Redes se utiliza el término
“nodo”. Como estaremos utilizando gráficas y programando algoritmos alrededor de ellas para resolver
problemas de redes, mantendremos el uso de "vértice" para evitar confusiones.
En la figura anterior se considera que la relación entre los dos extremos de una arista es simétrica; la arista
simplemente los conecta. En otras situaciones, sin embargo, queremos expresar relaciones asimétricas –
por ejemplo, que A apunta a B pero no viceversa. Para esto, definimos una gráfica dirigida como un
conjunto de vértices y aristas dirigidas; cada arista dirigida es un enlace de un vértice al otro en el que la
dirección es importante. Las gráficas dirigidas se trazan generalmente como muestra la figura siguiente,
con las aristas representadas por flechas.
Cuando queramos enfatizar que una gráfica no es dirigida, la podemos llamar precisamente gráfica no-
dirigida; pero en general las gráficas que discutamos serán no-dirigidas a menos que se especifique otra
cosa.
Las Gráficas como Modelos de Redes
Las gráficas son útiles porque sirven como modelos matemáticos 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 tenía 13 sitios (trazamos las localidades sólo de forma aproximada). Si estás
interesado, puedes encontrar diagramas acerca de este proyecto en
(http://som.csudh.edu/cis/lpress/history/arpaMaps/).
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
6
6
Los vértices representan computadoras y aparece una arista uniendo dos vértices si existe un enlace de
comunicación entre ellos. El diagrama puede reducirse a una gráfica de 13 vértices similar a las gráficas
simples de las figuras anteriores.
Notarás que el patrón de conexiones no depende de la posición de los vértices; lo que importa es cuáles
vértices están conectados a cuáles otros. Obtenemos la gráfica siguiente:
Las gráficas aparecen en muchos dominios, siempre que es útil representar cómo las cosas están física o
lógicamente enlazadas unas con otras en una estructura de red. El caso de los 13 vértices de Arpanet es
un ejemplo de una red de comunicaciones, en la cual los vértices son computadoras u otros dispositivos
que pueden trasmitir mensajes, y las aristas representan los enlaces a través de los cuales los mensajes
son transmitidos.
Existen otros tipos de redes como las redes sociales, en las cuales los vértices son personas o grupos de
personas y las aristas representan alguna clase de interacción social; y las redes de información, en las
cuales los vértices son recursos de información tales como páginas web o documentos, y las aristas
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
7
7
representan conexiones lógicas tales como hipervínculos, citas o referencias cruzadas. La lista de áreas en
las que las gráficas tienen una presencia es muy larga; te presentamos a continuación dos imágenes que
se encuentran a menudo y que contienen gráficas.
a) Red del Metro (Cd. de México) b) Rutas aéreas de Aeroméxico
Trayectorias y Conectividad
Repasemos ahora algunos de los conceptos y definiciones fundamentales que rodean a las gráficas.
Trayectorias
Hemos estado exponiendo algunos ejemplos de gráficas en diferentes áreas, y seguramente habrás notado
que surgen naturalmente algunos temas con el uso de gráficas en estas áreas. Uno de los más notorios es
la idea de que las cosas viajan a través de las aristas de una gráfica, moviéndose de vértice a vértice en
secuencia podría ser un pasajero siguiendo una secuencia de vuelos de una aerolínea, una pieza de
información siendo pasada de persona a persona en una red social, o un usuario de computadora o pieza
de software visitando una secuencia de páginas web a través de hipervínculos.
Esta idea motiva la definición de camino en una gráfica: un camino es simplemente una secuencia de
vértices con la propiedad de que cada par consecutivo en la secuencia está conectado por una arista.
Algunas veces también es útil pensar que el camino contiene no sólo los vértices sino también la secuencia
de aristas que conectan esos vértices.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
8
8
En el ejemplo anterior de Arpanet, la secuencia de vértices MIT, BBN, RAND, UCLA es un camino, como
lo es también la secuencia CASE, LINCOLN, MIT, UTAH, SRI, UCSB. En esta definición, un camino puede
repetir vértices, por ejemplo: SRI, STAN, UCLA, SRI, UTAH, MIT. Pero la mayoría de caminos que
consideraremos no hacen esto; si queremos enfatizar que el camino que estamos discutiendo no repite
vértices 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 vértices LINC, CASE, CARN, HARV, BBN, MIT, LINC.
Más precisamente, un ciclo es un camino con al menos tres aristas, en la cual el primer vértice y el último
son el mismo; el resto de los vértices son distintos. En la gráfica 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 diseño:
significa que si alguna arista falla todavía habría una forma de llegar de un vértice a cualquier otro.
De forma más general, los ciclos en las redes de comunicaciones y transporte están presentes a menudo
para permitir la redundancia –para proporcionar rutas alternativas.
También 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,
estás hablando de un ciclo que te contiene a ti, a tu esposa, a su primo, a su amigo de la secundaria, a su
compañero de trabajo (tu hermano), y finalmente a ti de nuevo.
Conectividad o Conexidad
Dado una gráfica, es natural preguntar si cada vértice puede alcanzar a todos los demás vértices a través
de una trayectoria. De acuerdo a esto, podemos decir que una gráfica es conexa cuando todos sus
vértices están conectados. Dos vértices están conectados si existe un camino que los une.
Por ejemplo, la gráfica de Arpanet es conexa. De forma general, se espera que la mayoría de redes de
comunicaciones y de transporte estén conectadas dado que su meta es mover tráfico de un vértice a otro.
Por otro lado, no existe una razón a priori para esperar que las gráficas en otros casos estén 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 gráfica
disconexa:
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
9
9
Componentes
La figura anterior hace visualmente aparente un hecho básico acerca de las gráficas disconexas: si una
gráfica es disconexa, se divide naturalmente en un conjunto de “piezas” conexas, grupos de vértices que
están conectados cuando se les considera como gráficas aisladas, de modo que no se traslapan. En la
misma figura anterior, puedes ver que la gráfica consiste de tres de tales piezas: una que contiene los
vértices A y B, otra que contiene los vértices C, D, y E, y otra más que contiene el resto de los vértices.
Con el fin de precisar esta noción, decimos que una componente conexa de una gráfica (a menudo llamada
simplemente “componente”) es una subgráfica conexa maximal tal que:
a. Cada vértice en el subconjunto tiene una trayectoria hacia cada uno de los otros
b. El subconjunto no es parte de un conjunto más grande con la propiedad de que cada vértice puede
llegar a cualquier otro.
Nota que tanto (a) como (b) son necesarios para formalizar la definición intuitiva: (a) indica que el
componente está conectado internamente, y (b) indica que realmente es una “pieza” independiente de la
gráfica, no una parte conexa de una pieza más grande. Por ejemplo, al conjunto de vértices F, G, H y J de
la figura anterior no lo podemos considerar como un componente, porque viola la parte (b) de la definición:
aunque existen trayectorias entre todos los pares de vértices, el conjunto pertenece a un conjunto más
grande (vértices F a M), en el cual también existen trayectorias para todos los pares.
El dividir una gráfica en sus componentes es solamente una primera forma de describir su estructura.
Dentro de un componente dado, puede existir una estructura interna más rica que sea importante para la
interpretación de la red.
3.1.2. Características
Una gráfica está formada por dos conjuntos, V el conjunto de vértices que debe ser a lo más
numerable (y en este caso podemos pedir que sea finito), y A el conjunto de aristas que está
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
10
10
formado por parejas de elementos de V. La gráfica se define independientemente de la
representación. Por ejemplo, las dos figuras siguientes representan la misma gráfica.
Un camino del vértice “x” al “y” en una gráfica, es una lista de vértices en la cual vértices sucesivos
se conectan a través de aristas. Por ejemplo BAFEG es una trayectoria de B a G en la gráfica
anterior.
Una gráfica es conexa si existe una trayectoria desde cada uno de los vértices hacia todos los otros
vértices.
Una gráfica disconexa está formado de componentes conexos, por ejemplo la gráfica de la figura
anterior tiene tres componentes conexos.
Una trayectoria es un camino en el cual ningún vértice 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 vértice son el mismo.
Por ejemplo, la trayectoria AFEGA es un ciclo.
Una gráfica conexa sin ciclos se denomina árbol.
Un grupo de árboles disconexos entre sí se denomina bosque.
Un árbol generador (spanning tree) es una subgráfica generadora a toda subgráfica que contiene a
todos los vértices. Por ejemplo, las aristas AB AC AF FD DE EG forman un árbol generador para el
componente grande de la gráfica anterior.
Si se agrega una arista a un árbol, se forma un único ciclo.
Un árbol con v vértices tiene exactamente v-1 aristas.
Si una gráfica con v vértices tiene menos de v-1 aristas, no es conexa. Si tiene más de v-1 aristas,
debe tener un ciclo.
Estamos utilizando v para denotar el número de vértices en una gráfica y utilizaremos a para denotar el
número de aristas (“edges” en inglés). a puede variar desde 0 hasta
. También se suele utilizar la
letra p para referirse a la cardinalidad del conjunto V.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
11
11
Las gráficas con relativamente pocas aristas son llamadas escasas.
Las gráficas con una falta relativamente baja de las aristas posibles son llamadas densas.
Las gráficas que hemos mostrado hasta el momento son llamados gráficas no-dirigidas, el tipo más
simple de gráfica. Existen otros tipos de gráficas más complejos que tienen más información asociada con
los vértices y las aristas:
En las gráficas ponderadas, se asignan cantidades (pesos o valores) a cada arista para
representar, por ejemplo, distancias o costos.
En las gráficas dirigidas, las aristas son de “un solo sentido”: una arista puede ir de x a y pero no
de y a x.
Las gráficas ponderadas dirigidas son llamadas a veces redes.
La información extra que contienen las gráficas ponderadas y las dirigidas las hace obviamente un poco
más difíciles de manipular que las gráficas simples no-dirigidas.
Representaciones en Computadora
Para poder procesar gráficas con un programa de computadora, es necesario decidir cómo representarlos
dentro de la computadora. Discutiremos dos de las representaciones más comunes; la selección de cuál
usar depende principalmente de si la gráfica 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 gráfica es mapear los nombres de los vértices a números enteros
entre 1 y v. La razón principal del mapeo es hacer posible el acceso rápido a la información
correspondiente a cada vértice, a través de un indexado de arreglos.
Se puede utilizar cualquier esquema estándar de búsqueda; por ejemplo, podemos trasladar los nombres
de los vértices 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 vértice.
¿Recuerdas que estudiamos estas clases de algoritmos en la unidad anterior? Asumimos entonces que
una función indice está disponible para convertir nombres de vértice a enteros entre 1 y v, y una función
nombre para convertir enteros a nombres de vértice.
Para hacer los algoritmos fáciles de seguir, utilizamos aquí nombres de vértice 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 extensión de los algoritmos para manipular gráficas con nombres reales de
vértice por medio de las técnicas de búsqueda que aprendiste.
La representación más directa de las gráficas 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 vértice x al vértice y, y
establecido en 0 en otro caso.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
12
12
La matriz de adyacencia para la gráfica que hemos estado usando se muestra a continuación.
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
Notarás 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 simétrica, pero los algoritmos resultan un poco más
simples cuando se utiliza la matriz completa. Asimismo, es usualmente conveniente asumir que existe una
“arista” en cada vértice con sí mismo, así a[x][x] está establecido en 1 para x desde 1 a v.
Introduciendo una Gráfica a la Computadora
Para introducir una gráfica 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
gráficas escasas. Usaremos entonces un formato más directo: primero leemos los nombres de los vértices,
y luego pares de nombres de vértices (lo cual define las aristas).
Una manera sencilla de proceder es leer los nombres de los vértices y guardarlos en una tabla hash o en
un árbol de búsqueda binaria y asignar a cada nombre de vértice un entero que se usará para acceder a
los arreglos de vértices indexados, como la matriz de adyacencia. A la lectura del i-ésimo vértice se le
puede asignar el entero i.
Por simplicidad, primero leemos v y a, luego los vértices y las aristas. Como alternativa, la entrada podría
ser organizada con un delimitador que separe los vértices de las aristas, y entonces el programa podría
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 gráfica 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 sólo las
partes más relevantes de los programas y usaremos algo de pseudocódigo para facilitar las explicaciones;
en la última sección de la unidad encontrarás programas completamente funcionales).
int V, A;
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
13
13
int a[maxV][maxV];
void matrizady(){
int j, x, y;
// Instrucciones para leer V y A
for (x = 1; x <= V; x++)
for (y = 1; y <= V; y++) a[x][y] = 0;
for (x = 1; x <= V; x++) a[x][x] = 1;
for (j = 1; j <= A; j++) {
// Instrucciones para leer v1 y v2
x = indice(v1); y = indice(v2);
a[x][y] = 1; a[y][x] = 1;
}
}
Los tipos de v1 y v2 y el código para indice no se han incluído en el programa, pero pueden agregarse
fácilmente, dependiendo de la representación deseada. Por ejemplo, v1 y v2 pueden ser del tipo carácter
e indice puede ser una simple función que devuelva c – ‘A’ + 1 o algo parecido.
La representación con la matriz adyacente es satisfactoria solamente si las gráficas que van a ser
procesadas son densas: la matriz requiere v2 bits de almacenamiento y v2 pasos sólo para inicializarla. Si el
número de aristas (número de bits 1 en la matriz) es proporcional a v2, esto puede ser aceptable porque
alrededor de v2 pasos se requieren para leer las aristas en cualquier caso. Sin embargo, si la gráfica es
escasa, simplemente la inicialización de la matriz puede ser el factor dominante en el tiempo de ejecución
de un algoritmo.
Analicemos ahora una representación que es más adecuada para gráficas que no son densas. En la
representación de la estructura de adyacencia todos los vértices conectados a cada vértice están listados
en una lista de adyacencia para ese vértice. Esto puede ser realizado fácilmente con listas enlazadas. El
programa que sigue construye la estructura de adyacencia para la gráfica que estamos tomando como
ejemplo. Las listas enlazadas se construyen de la forma usual, con un vértice artificial z al final (el cual
apunta a sí mismo). Los vértices artificiales para el inicio de las listas se mantienen en un arreglo ady
indexado por el vértice. Para agregar a esta representación de la gráfica una arista conectando x a y,
agregamos la lista de adyacencia de x a y, y la lista de adyacencia de y a x.
struct vertice {
int v;
struct vertice *sig; };
int V, A;
struct vertice *ady[maxV], *z;
void listaady() {
int j, x, y;
struct vertice *t;
// Instrucciones para leer V y A
z = new vertice;
z->next = z;
for (j = 1; j <= V; j++)
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
14
14
ady[j] = z;
for (j = 1; j <= A; j++) {
// Instrucciones para leer v1 y v2;
x = indice(v1); y = indice(v2);
t = new vertice;
t->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 representación con estructura de adyacencia construida por el programa
anterior.
La representación de lista de adyacencia es mejor para gráficas escasas porque el espacio requerido es
menor comparado con el espacio requerido por la representación 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 “¿Cuáles vértices están conectados directamente al vértice x?” no
pueden ser respondidas eficientemente.
Para esta representación, el orden en el que las aristas aparecen en la entrada es muy importante:
determina el orden (junto con el método de inserción de lista utilizado) en el cual los vértices aparecen en
las listas de adyacencia. Debido a esto, la misma gráfica 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 cómo están ordenadas las aristas en las listas de adyacencia, puede llegar a la respuesta a
través de secuencias muy diferentes de cálculos. Si hay más de una “respuesta correcta”, los diferentes
órdenes de entrada pueden producir diferentes resultados de salida.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
15
15
Algunas operaciones simples no son soportadas por esta representación. Por ejemplo, si se desea eliminar
un vértice x, y todas las aristas conectadas a él, no es suficiente eliminar vértices de la lista de adyacencia:
cada vértice en esta lista especifica otro vértice cuya lista de adyacencia debe ser examinada para eliminar
un vértice correspondiente a x. Este problema puede ser corregido enlazando los dos vértices 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 vértices correspondientes a esa arista pueden ser eliminados
rápidamente. Por supuesto, estos enlaces extra son incómodos de procesar, y no deberían ser incluidos a
menos que se requieran operaciones como la eliminación.
Tales consideraciones también aclaran por qué no utilizamos una representación “directa” para las gráficas:
una estructura de datos que modele la gráfica exactamente, con vértices representados por registros
asignados y listas de aristas conteniendo enlaces a los vértices en lugar de nombres de vértice. Sin un
acceso directo a los vértices, las operaciones simples se vuelven desafiantes. Por ejemplo, para agregar
una arista a una gráfica representado de esta manera, se tendría que buscar de alguna manera a través de
la gráfica para encontrar los vértices.
Las gráficas dirigidas y ponderadas se representan con estructuras similares. Para las gráficas dirigidas,
todo es lo mismo, excepto que cada arista está representada sólo 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 aparición de y en la lista de
adyacencia de x dentro de la estructura de adyacencia.
Para las gráficas ponderadas, de nuevo todo es lo mismo excepto que se llena la matriz de adyacencia con
pesos en lugar de valores booleanos (utilizando algún 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 información con los vértices de una gráfica para permitirle modelar
objetos más complicados o para ahorrar información de control en algoritmos complicados. La información
extra asociada con cada vértice puede ser acomodada utilizando arreglos auxiliares indexados por el
número de vértice o haciendo ady un arreglo de registros en la representación de estructura de
adyacencia.
La información extra asociada con cada arista puede ser colocada en los vértices de la lista de adyacencia
(o en un arreglo a de registros en la representación de matriz de adyacencia), o en arreglos auxiliares
indexados por el número de arista (esto requiere la numeración de las aristas).
Recorrido en Profundidad
Cuando hablamos de redes y gráficas, empezamos inmediatamente a hacernos preguntas: ¿Es la gráfica
conexa? Si no, ¿Cuáles son sus componentes conexos? ¿La gráfica tiene un ciclo? Estos y otros
problemas pueden ser resueltos con diversos algoritmos. Discutiremos a continuación un método llamado
búsqueda en profundidad (depth-first search en inglés), el cual “visita” cada vértice y revisa cada arista de
la gráfica sistemáticamente.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
16
16
Comencemos por concentrarnos en la forma de examinar cada pieza de la gráfica de una manera
organizada:
Utilizamos un arreglo vid[V] para registrar el orden en el que los vértices son visitados.
Cada entrada o “celda” en el arreglo se inicializa con el valor de “novisitado” para indicar que ningún
vértice ha sido visitado todavía.
La meta es visitar sistemáticamente todos los vértices de la gráfica, estableciendo en la entrada vid
correspondiente el id del vértice i visitado, en el que id = 1, 2,…, v. El siguiente programa utiliza una
función visitar que visita todos los vértices del mismo componente conexo con el vértice dado como
argumento.
void recorrer()
{
int k;
for (k = 1; k <= V; k++)
vid[k] = novisitado;
for (k = 1; k <= V; k++)
if (vid[k] == novisitado) visitar(k);
}
El primer ciclo for inicializa el arreglo vid. Luego visitar es llamada para el primer vértice, lo cual tiene
como resultado que los valores vid de todos los vértices conectados a ese vértice son modificados a
valores diferentes de “novisitado”. Luego recorrer explora el arreglo vid para encontrar un vértice que
todavía no ha sido visitado y llama visitar para ese vértice, continuando de esta manera hasta que todos
los vértices han sido visitados. Nota que este método no depende de cómo la gráfica está representada o
de cómo visitar es implementada.
Una posible implementación recursiva de visitar para la representación de lista de adyacencia sería:
Visitar un vértice.
Revisar todas sus aristas para ver si llevan a vértices que todavía no han sido visitados.
Si esto es así, se les hace la visita.
void visitar(int k)
{
struct vertice *t;
vid[k] = ++id;
for (t = ady[k]; t != z; t = t->siguiente)
if (vid[t->v] == novisitado)
visitar(t->v);
}
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
17
17
En la figura siguiente se puede seguir la operación del algoritmo. Están trazadas las llamadas recursivas
durante la función visitar. Cada componente conexo lleva a un árbol, denominado árbol de búsqueda
en profundidad del componente.
Es importante notar que este bosque de árboles de recorrido en profundidad es sólo otra manera de trazar
la gráfica: el algoritmo examina todos los vértices y aristas de la gráfica. Las líneas sólidas indican que el
vértice inferior fue encontrado por el algoritmo en la lista de aristas del vértice superior y que no había sido
visitado en ese momento, así que una llamada recursiva fue hecha. Las líneas punteadas corresponden a
aristas de vértices que ya habían 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 también evita que se siga la arista la segunda vez que es
encontrada.
Existen algoritmos similares que pueden utilizarse alternativamente como el de búsqueda en profundidad
no recursivo o el de búsqueda en amplitud.
Actividad 1. Fundamentos de redes
A través de esta actividad podrás identificar dos tipos de búsqueda que se mencionan en el contenido,
pero no se definen (Búsqueda en Profundidad No Recursivo (Nonrecursive Depth-First Search) y
Búsqueda en Amplitud (Breadth-First Search).
Instrucciones:
1. Formen equipos de 4 o 5 integrantes.
2. Colabora con tu equipo en el diseño de una wiki que responderá al título: Algoritmos de Recorrido
3. Investiga sobre los siguientes temas:
a. Recorrido en Profundidad No Recursivo (Nonrecursive Depth-First Search).
i. Descripción.
ii. Diferencia con el algoritmo Recorrido en Profundidad (Depth-First Search).
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
18
18
iii. Código en C o en Java de la función básica.
b. Recorrido en Anchura (Breadth-First Search).
i. Descripción.
ii. Diferencia con el algoritmo Recorrido en Profundidad No Recursivo (Nonrecursive
Depth-First Search).
iii. Código en C o en Java de la función básica.
4. La wiki que ayudes a construir debe contener al menos, los siguientes elementos: introducción,
desarrollo (información generada por ti), explicación del funcionamiento de los algoritmos,
diferencia con el otro algoritmo que se menciona, el código en C o en Java de la función básica
(suele ser expresable en 15-20 líneas de código), dos links para conocer más algunos de los
temas, conclusiones, las fuentes de información 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 información ingresada por ti y por tus
compañeros, es importante que respetes las aportaciones de tus compañeros y cualquier
modificación sea con fundamentos.
.
3.2. Flujo
Ya que repasamos un poco la teoría de gráficas, que discutimos la forma en que las gráficas pueden
representarse dentro de una computadora y que nos introdujimos a algoritmos que son capaces de
proporcionar respuestas a preguntas básicas acerca de las gráficas, 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 típicos es el del flujo
de materias primas u otros elementos a través de ellas. Podemos considerar, por ejemplo, una red
petrolera con tubería de diversos tamaños interconectada de formas complejas con válvulas controlando la
dirección del flujo en las uniones. Para simplificar el trabajo que iniciaremos acerca de esto podemos
suponer también que la red tiene una sola fuente (digamos, un campo petrolero) y un solo destino
(digamos, una refinería) a los cuales se conectan la tubería. Los entornos reales, por supuesto, pueden
tener varias fuentes y varios destinos, así que los algoritmos deben ajustarse a la situación.
¿Cuáles son las configuraciones de válvulas que maximizan la cantidad de petróleo 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 solución.
Este escenario general también puede ser usado para describir el flujo de tráfico en las autopistas, de
materiales moviéndose dentro de las fábricas, etc. Se han estudiado muchas diferentes versiones del
problema, dependiendo de las situaciones prácticas en las que se presenta. Puedes ver que existe una
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
19
19
motivación muy fuerte para encontrar un algoritmo eficiente que ofrezca una solución adecuada. El flujo en
las redes es un ejemplo típico de problemas del área de investigación de operaciones.
Existen métodos matemáticos complejos para tratar los problemas de investigación de operaciones, pero la
solución de problemas específicos como el del flujo en una red, está estrechamente relacionada a los
algoritmos de gráficas, así que es posible desarrollar un programa que resuelva el problema utilizando las
herramientas algorítmicas que ya hemos empezado a examinar. El problema continúa siendo estudiado
activamente; la “mejor” solución todavía no ha sido encontrada y nuevos algoritmos siguen siendo
descubiertos.
3.2.1. Flujo máximo
Considera el diagrama idealizado de una pequeña red de tuberías de petróleo que se muestra a
continuación:
Las tuberías son de capacidad fija proporcional a su tamaño y el petróleo puede fluir solamente de arriba
hacia abajo. Además, válvulas en cada unión controlan cuánto petróleo pasa en cada dirección. Sin
importar el estado de las válvulas el sistema alcanza un punto de equilibrio cuando la cantidad de petróleo
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 petróleo fluyendo hacia cada unión es igual a
la cantidad saliendo de ella. Medimos tanto el flujo como la capacidad de la tubería en términos de
unidades enteras (por ejemplo, litros por segundo).
No es obvio inmediatamente que la configuración de las válvulas pueda afectar realmente el flujo máximo
total. La figura siguiente ilustra que sí afecta.
Primero, supongamos que se abre la válvula 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 continuación supongamos que el
tubo AC se abre y la válvula C se mueve para cerrar el tubo CD y abrir el tubo CE (quizás el operador de la
válvula D ha informado al operador de la válvula C que ya no puede aceptar más debido a la carga desde
B). El flujo resultante se muestra en el diagrama central de la figura: los tubos BD y CE están llenos. Ahora,
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
20
20
el flujo podría ser incrementado en alguna medida enviando lo suficiente a través de la trayectoria ACDF
para llenar el tubo DF, pero hay una mejor solución, como se muestra en el tercer diagrama. Cambiando la
válvula B para redirigir suficiente flujo para llenar BE, proporcionamos suficiente capacidad en el tubo DF
para permitir a la válvula C abrir completamente el tubo CD. El flujo total entrando y saliendo de la red se
incrementa encontrando la configuración adecuada de válvulas.
Nuestro desafío es desarrollar un algoritmo que pueda encontrar la configuración “apropiada” de válvulas
para cualquier red. Además, queremos estar seguros que ninguna otra configuración de válvulas permitirá
un flujo mayor. Esta situación puede ser modelada por una gráfica dirigida.
Definimos una red como una gráfica ponderada dirigida con dos vértices 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 vértice. 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 vértice es igual al flujo saliendo de ese vértice. El valor del
flujo es el flujo de la fuente. El problema del flujo de red es encontrar un flujo con valor máximo 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 gráficas anteriormente. En lugar de un solo peso, dos pesos están asociados con cada
arista, el tamaño y el flujo. Estos pueden ser representados por dos campos en un vértice de la lista de
adyacencia, como dos matrices en la matriz de adyacencia, o por dos campos dentro de un solo registro en
cualquier representación. Aunque las redes son gráficas dirigidas, los algoritmos necesitan atravesar las
aristas en la dirección “equivocada”, así que utilizamos una representación de gráfica no-dirigida: si existe
una arista de x a y con tamaño s y flujo f, también mantenemos una arista de y a x con tamaño –s y flujo –f.
En una representación de lista de adyacencia, es necesario mantener enlaces conectando los dos vértices
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 máximo de una forma más precisa como sigue.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
21
21
Redes de Flujo y Flujos
Una red de flujo es una gráfica dirigida en la cual cada arista tiene una capacidad
no-negativa .
Requerimos además que si A contiene una arista , entonces no existe una arista en la dirección
inversa.
Si , entonces por conveniencia definimos , y no aceptamos auto-ciclos.
Distinguimos dos vértices en una red de flujo: una fuente s y un destino t. Por conveniencia, asumimos
que cada vértice se encuentra en alguna trayectoria de la fuente al destino. Esto es, para cada vértice
, la red de flujo contiene una trayectoria . La gráfica es por lo tanto conexa y, dado que cada
vértice diferente de s tiene al menos una arista entrante, entonces | | | | .
Estamos listos ahora para definir los flujos más formalmente.
Sea una red de flujo con una función de capacidad c. Sea s la fuente de la red, y sea t el destino.
Un flujo en G es una función con valor real que satisface las siguientes dos propiedades:
Restricción de la capacidad: Para todo , se requiere .
Conservación 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 vértice u al vértice 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 notación | f | denota
el valor del flujo, no valor absoluto o cardinalidad.) Típicamente, 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.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
22
22
En el problema del flujo máximo, se nos da una red de flujo G con fuente s y destino t, y deseamos
encontrar un flujo de valor máximo.
La restricción de capacidad dice simplemente que el flujo de un vértice a otro debe ser no-negativo y que
no debe exceder la capacidad dada. La propiedad de conservación del flujo dice que el flujo total entrando
un vértice que no sea la fuente o el destino debe ser igual al flujo total saliendo de ese vértice –dicho
informalmente, “el flujo de entrada es igual al flujo de salida.”
3.2.2. Teorema del corte mínimo y flujo máximo
Teorema. En cualquier red, el flujo máximo que fluye de la fuente al destino, es igual a la
capacidad del corte mínimo que separa a la fuente del destino. Este corte mínimo de
separación puede no ser único.
En la figura siguiente se muestra una red de ejemplo que tiene varios cortes, cada uno con capacidad
diferente. El número que se muestra junto a cada arista representa su capacidad máxima.
La siguiente tabla contiene los cortes de separación y sus capacidades.
Aristas en el corte de separación Capacidad
{SA, SB} 17
{BE, BD, AD, CD, CT} 17
{CT, DT, ET} 16
{BE, CT, DT} Corte mínimo 14
El corte mínimo es el cuarto de la lista con una capacidad de 14 unidades; de acuerdo al teorema, también
es el flujo máximo que puede fluir de la fuente al destino. Como puedes ver, la esencia del teorema es
sencilla.
Un artículo de Lester Randolph Ford Jr. y de Delbert Ray Fulkerson (1962) discutiendo el problema del flujo
máximo estableció este famoso teorema. Para definirlo formalmente, necesitaremos de tres conceptos:
redes residuales, trayectorias de aumento, y cortes.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
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
cómo 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 están en Gf son aquellas que pueden admitir más flujo; las aristas cuyo flujo
iguala a su capacidad tienen , y no están en Gf.
La red residual Gf también puede contener aristas que no están 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 disminución 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 dirección opuesta a , a lo más 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 operación
necesaria en muchos algoritmos.
Más 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 vértices , 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 definición de red residual, se puede incrementar el flujo en una arista (u, v) de
una trayectoria de aumento por hasta sin violar la restricción de capacidad de (u, v) y (v, u) en la
red original G.
Llamaremos a la máxima 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 partición de V en S y T = V – S tal que y . Si
f es un flujo, entonces el flujo neto f(S, T) a través del corte (S, T) se define como
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
24
24
∑∑
∑∑
La capacidad del corte (S, T) es
∑∑
Un corte mínimo de una red es un corte cuya capacidad es mínima sobre todos los cortes de la red.
La asimetría 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 dirección opuesta. Para flujo, consideramos el flujo que va de S a T menos el flujo que va en la dirección
opuesta de T a S.
Versión Formal del Teorema del Corte Mínimo y Flujo Máximo
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 máximo en G.
2. La red residual Gf no contiene trayectorias de aumento.
3. | | para algún corte de G.
Esto equivale a lo que enunciamos al principio de esta sección: el valor del flujo máximo es igual a la
capacidad de un corte mínimo. Puedes encontrar todos los desarrollos y demostraciones matemáticas 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 mínimo y flujo máximo
Ford y Fulkerson desarrollaron un método para encontrar el flujo máximo alrededor del teorema.
Comenzando con un flujo cero, se aplica el método repetidamente. Mientras que el método pueda ser
aplicado, produce un aumento de flujo; si no puede ser aplicado, el flujo máximo ha sido encontrado.
Examinaremos el método en términos de la gráfica de la siguiente figura.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
25
25
Para simplificar, omitimos las flechas, dado que todas apuntan hacia abajo. El método no está restringido,
por supuesto, a gráficas que pueden ser trazadas con todas las aristas apuntando en una dirección.
Usamos estas gráficas porque ayudan a entender el flujo de la red en términos de líquidos fluyendo en
tubos.
Consideremos cualquier trayectoria dirigida (hacia abajo) a través de la red (de la fuente al destino).
Claramente, el flujo puede ser incrementado por al menos la cantidad más pequeña 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 situación en la que todas las trayectorias dirigidas a través 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 través de la red que pueden contener aristas que apuntan en la “dirección
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 través 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 través de AC y CD, luego desviando 3 unidades en la válvula B de BD a BE y
EF. No perdemos ningún flujo en DF porque 3 de las unidades que venían de BD ahora vienen de CD.
Para simplificar la terminología, 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
atrás. Nota que la cantidad por la cual el flujo puede ser aumentado está limitada por el mínimo de las
capacidades no usadas en las aristas hacia adelante y el mínimo de los flujos en las aristas hacia atrás.
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 atrás a lo largo de la trayectoria queda vacía.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
26
26
Además, el flujo no puede ser incrementado en cualquier trayectoria que contenga una arista hacia delante
llena o una arista hacia atrás vacía.
El párrafo anterior proporciona un método para incrementar el flujo en cualquier red, a condición de que
una trayectoria sin aristas hacia adelante llenas o aristas hacia atrás vacías pueda encontrarse. El punto
esencial del método es la observación de que si tal trayectoria no puede ser encontrada entonces el flujo es
máximo.
Propiedad. Si todas las trayectorias de la fuente al destino en una red tienen una arista hacia adelante
llena o una arista hacía atrás vacía, entonces el flujo es máximo.
Para probar este hecho, examinamos la gráfica e identifiquemos la primera arista hacia adelante llena o
hacia atrás vacía en cada trayectoria. Este conjunto de aristas corta la gráfica 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 través” 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 través del corte: para obtener el flujo a través del
corte, el total del flujo en las aristas yendo en la otra dirección 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 máximo, sino también que el corte es mínimo
(esto es, cualquier otro corte tiene al menos un flujo tan alto que lo cruza). Esto corresponde al teorema de
corte mínimo – flujo máximo: el flujo no puede ser mayor (de otra manera el corte tendría que ser mayor
también), y no existen cortes menores (de otra forma el flujo tendría que ser también menor).
El método 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 atrás vacías, continuando hasta que no existan tales trayectorias en la red.”
Esto no es un algoritmo en el sentido usual, dado que el método para encontrar trayectorias no está
especificado, y cualquier trayectoria puede ser usada.
Por ejemplo, uno puede basar el método en la intuición que entre más larga la trayectoria, la red está más
llena, de manera que las trayectorias largas deberían ser preferidas. Pero el ejemplo clásico que se
muestra en la siguiente figura demuestra que se debe tener cuidado con esto.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
27
27
En esta red, si la primera trayectoria escogida es ABCD, entonces el flujo es aumentado en sólo 1.
Entonces la segunda trayectoria escogida puede ser ACBD, de nuevo aumentando el flujo en 1, y dejando
una situación idéntica a la situación 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) continuaría con esta estrategia, requiriendo 1000 pares de iteraciones antes de que el
flujo máximo sea encontrado. Si los números en los lados fueran un billón, entonces se usarían dos billones
de iteraciones. Obviamente, esta es una situación indeseable, dado que las trayectorias ABC y ADC dan el
flujo máximo en sólo dos pasos. Para que el algoritmo sea útil, debemos evitar que el tiempo de ejecución
sea tan dependiente de la magnitud de las capacidades. Afortunadamente, este problema puede ser
eliminado fácilmente:
Propiedad. Si la trayectoria más corta disponible de la fuente al destino se utiliza en el método Ford y
Fulkerson, entonces el número de trayectorias utilizadas antes de que se encuentre el flujo máximo en una
red de V vértices y A aristas debe ser menor que VA.
Este hecho fue probado por Edmonds y Karp en 1972.
Para esto se puede utilizar una versión modificada apropiadamente del algoritmo de recorrido en anchura
que mencionamos en la sección 3.1.2.
Los algoritmos básicos que usan el método de Ford y Fulkerson están ampliamente desarrollados por
varios autores. Por ejemplo, en el libro de “Heineman, G., Pollice, G., Selkow, S. Algorithms in a Nutshell.
(2009) O’Reilly Media, Inc. 1st Ed. USA” puedes encontrar inclusive el código en Java. Sería un buen
ejercicio que implementaras el algoritmo en tu computadora:
También 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 sólo se conocían algoritmos eficientes para el flujo máximo 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 más corta a la vez (método de Dinic). Más tarde,
fue introducido un método alternativo basado en el concepto de preflujo de Karzanov, el cual presentamos
desarrollado en la última sección de la unidad.
En este método, para un vértice fuente s dado y un vértice 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 vértices
adyacentes de s. Los excesos son empujados hacia t, mientras que se satisface la restricción que el flujo
de entrada debe ser igual al flujo de salida en cada vértice. 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 más
excesos.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
28
28
El algoritmo y su análisis son simples e intuitivos, aunque el algoritmo se ejecuta tan rápido para gráficas
de cualquier densidad como cualquier otro método conocido o más cuando se incorporan estructuras
dinámicas de datos. Un punto extra a favor es que el algoritmo también admite implementaciones
distribuidas y paralelas eficientes, adecuadas para los nuevos entornos de cómputo.
En la sección 3.4.1. Solución de Problemas de Redes se presenta el desarrollo de este algoritmo
incluyendo el pseudocódigo y el código 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 artículo original (en ruso) en el que se presenta este método 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 artículo en inglés 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 través de lo aprendido en la sección 3.2.3. Algoritmos de corte mínimo y flujo máximo, realiza el
siguiente reporte de investigación tomando en cuenta el algoritmo de Ford y Fulkerson. Y las instrucciones
mencionadas a continuación.
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. Descripción.
ii. Pseudocódigo
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. Envía tu documento a tu Facilitador(a) y espera su retroalimentación
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
29
29
3.3. Conexidad
En una gráfica conexa hay al menos una trayectoria entre cada par de sus vértices. Un vértice o una arista
tienen la propiedad de destruir la conexidad de la gráfica si cuando se elimina uno de los dos, o ambos, la
gráfica se convierte en disconexa. Consideremos por ejemplo una red de comunicaciones representada por
la gráfica que se muestra en la siguiente figura. Los vértices corresponden a centros de comunicación y las
aristas a canales de comunicación.
Si se elimina el vértice v, se rompe la comunicación. Esto implica que en esta red el centro representado
por el vértice v tiene la propiedad de destruir el sistema de comunicaciones, así que la red depende de la
conexidad.
Conexidad
En el siguiente diagrama, la gráfica de la izquierda tiene dos piezas, mientras que la gráfica de la derecha
sólo tiene una.
Pongamos esta observación en términos rigurosos.
Una gráfica es conexa si para cada par de vértices u y v, la gráfica contiene una trayectoria con
puntos extremos u y v como sub-gráfica.
La gráfica de la izquierda no es conexa porque no hay una trayectoria de cualquiera de los tres vértices
superiores a cualquiera de los dos vértices inferiores. Sin embargo, la gráfica de la derecha es conexa
porque existe una trayectoria entre cada par de vértices.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
30
30
Una sub-gráfica conexa máxima se denomina componente conexo. (Por máxima, queremos decir que el
incluir cualesquiera vértices adicionales volverá disconexa la sub-gráfica.) La gráfica de la izquierda tiene
dos componentes conexos, el triángulo y la arista independiente. La gráfica de la derecha es conexa
completamente así que tiene un solo componente conexo.
Teorema de Conexidad
Cada gráfica tiene al menos | | | | componentes conexos.
Corolario. Toda gráfica conexa con n vértices tiene al menos n-1 aristas.
Conceptos Básicos
Vértice de corte: Sea G una gráfica con k(G) componentes. Un vértice v de G es denominado vértice de
corte de G si . Por ejemplo, en la gráfica de la siguiente figura, los vértices u y v son
vértices de corte.
Arista de corte: Una arista a de una gráfica G es denominada arista de corte si
. En la gráfica de la siguiente figura, e y f son aristas de corte.
Las siguientes observaciones son las consecuencias inmediatas de las definiciones anteriores:
1. La remoción de un vértice puede incrementar el número de componentes en una gráfica por al
menos uno.
2. Cada vértice no-colgante de un árbol es un vértice de corte.
3. La remoción de una arista puede incrementar el número de componentes por a lo más uno.
4. Los vértices finales de una arista de corte son vértices de corte si su grado es mayor que uno.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
31
31
Lo siguiente caracteriza los vértices de corte:
Si G(V, A) es una gráfica conexa, entonces v es un vértice de corte si existen vértices { } tales
que cada trayectoria en G pasa a través de v.
Lo siguiente caracteriza las aristas de corte:
Para una gráfica conexa G, las siguientes declaraciones son equivalentes:
a. a es una arista de corte de G.
b. Si , existe una partición del subconjunto de aristas { } para con y
.
3.3.1. Conexidad puntual
La conexidad puntual (o de vértices) k(G) de una gráfica conexa G (que no sea una
gráfica completa) es el número mínimo de vértices cuya eliminación desconecta G.
Recuerda que una gráfica completa es una gráfica no dirigida en la que se conecta cada par de vértices
distintos por una arista única.
Cuando , se dice que la gráfica es k-conexa (o k-vértices conexa). Cuando se elimina un vértice,
también se deben eliminar las aristas que inciden en él.
Por ejemplo, consideremos las siguientes gráficas:
La gráfica G1 puede ser desconectada eliminando un solo vértice (ya sea b o c). Esta gráfica tiene una
conexidad puntual de 1.
La gráfica G2 puede ser desconectada eliminando un solo vértice (ya sea c o d). La gráfica tiene una
conexidad puntual de 1.
La gráfica G3 puede ser desconectada eliminando sólo un vértice: el c. La gráfica tiene una conexidad
puntual de 1.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
32
32
La gráfica G4 no puede ser desconectada eliminando un solo vértice, pero la eliminación de dos vértices no
adyacentes (tales como b y c) la desconectan. La gráfica tiene una conexidad puntual de 2.
Conjunto de Vértices de Corte
Un conjunto de vértices de corte de una gráfica conexa es un conjunto S de vértices con las siguientes
propiedades:
La eliminación de todos los vértices en S desconecta G.
La eliminación de algunos (pero no todos) de los vértices en S no desconecta G.
Consideremos la siguiente gráfica
Podemos desconectar la gráfica eliminando los vértices b y e, pero no podemos desconectarla eliminando
sólo uno de ellos. El conjunto de vértices 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 sección).
Esto se mantiene para todas las gráficas conexas.
Existe una desigualdad entre descubierta por Whitney en 1932 que dio origen al
siguiente teorema:
Teorema. Para toda gráfica G conexo, se cumple que
Donde es el grado mínimo de los vértices en G.
Recuerda que el grado de un vértice es el número de aristas incidentes en el vértice, con los ciclos
contados dos veces.
Pero es ciertamente posible para ambas desigualdades en la expresión anterior que sean desigualdades
estrictas, esto es
Por ejemplo, en la siguiente gráfica
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
33
33
Y la siguiente gráfica tiene
3.3.2. Conexidad lineal
La conexidad lineal (o de aristas) λ(G) de una gráfica conexa G es el número mínimo
de aristas que cuando son removidas desconectan G.
Cuando , se dice que la gráfica G tiene una conexidad lineal k.
Si se tienen, por ejemplo, las siguientes gráficas
Su conexidad lineal es como sigue:
G1 tiene una conexidad lineal de 1
G2 tiene una conexidad lineal de 1
G3 tiene una conexidad lineal de 2
G4 tiene una conexidad lineal de 2
G1 puede ser desconectado (dividido en dos componentes) removiendo una de las aristas: bc o bd. Estas
aristas son denominadas puente.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
34
34
Puente. Un puente es una sola arista cuya remoción desconecta un gráfica.
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 remoción 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 gráfica conexa G es un conjunto de aristas S con las siguientes
propiedades:
La eliminación de todas las aristas en S desconecta G.
La eliminación de algunas (pero no todas) de las aristas en S no desconecta G.
Consideremos, por ejemplo, la siguiente gráfica:
Podemos desconectar G eliminando tres aristas: bd, be, y ce, pero no podemos desconectarlo eliminando
sólo 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 gráfica no conexa es cero, λ(G) = 0, mientras que si la gráfica es conexa y
posee un puente, entonces λ(G) = 1.
En la sección 3.4.1. Solución de Problemas de Redes encontrarás el pseudocódigo, el código en Java y
una corrida de ejemplo de un algoritmo que encuentra la conexidad lineal de una gráfica conexa no-dirigido
de n vértices resolviendo n problemas de flujo máximo de red. Te recomendamos que experimentes con él
en tu IDE Eclipse.
3.3.3. Teorema de Menger
Dado que un par determinado de vértices en una gráfica puede ser conectado por muchas trayectorias, es
natural preguntarse cómo puede medirse el grado de conexidad entre ellos.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
35
35
Una manera de medir su conexidad es determinar el máximo número de esas trayectorias que son
"independientes" una de otra, esto es, que no comparten otros vértices considerándolas por pares.
Otra manera de medir su conexidad es determinar el mínimo número de vértices cuya eliminación
de la gráfica destruye todas las trayectorias entre el par de vértices dado.
El teorema de Menger establece que para cada par de vértices no adyacentes estas dos medidas son
iguales. Una formulación equivalente del teorema establece que si V y W son conjuntos de vértices no
vacíos en una gráfica, entonces el número máximo de trayectorias internamente disjuntas V-W es igual al
número mínimo de vértices cuya eliminación destruye todas esas trayectorias. Estamos hablando de la
conexidad puntual.
El teorema es un resultado del desarrollo de la conexidad en gráficas no-dirigidas. Karl Menger lo demostró
en 1927 para la conexidad puntual, pero también para la conexidad lineal. La versión del teorema para la
conexidad lineal fue generalizada más tarde por un teorema que ya estudiaste: el del corte mínimo – flujo
máximo.
Teorema de Menger para la Conexidad Puntual
Sean v y w dos vértices no adyacentes en una gráfica G. Un conjunto S de vértices 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 vértice
en S. El orden mínimo de un conjunto de corte v-w es denominado conexidad v-w y es denotado por
Para dos vértices cualesquiera v y w, una colección de trayectorias v-w es considerada internamente
disjunta si las trayectorias son disjuntas por pares, excepto para los vértices v y w. El número máximo de
trayectorias internamente disjuntas v-w se denota por . Dado que cada trayectoria en ese conjunto
debe contener un vértice 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 ningún vértice en común, excepto el primero y el último.
Consideremos, por ejemplo, el gráfico siguiente
Es fácil verificar que tanto como son 3. El que ambos parámetros sean iguales en este caso
no es coincidencia, y el hecho de que esto es cierto en general es el contenido de una versión del teorema
de Menger. Comprueba el resultado encontrando las tres trayectorias que no tienen vértices en común
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
36
36
excepto el inicial y el final, y un conjunto de corte puntual que contiene al menos tres vértices y separa la
gráfica al eliminarlos (no encontrarás un conjunto que contenga menos de tres vértices).
Teorema de Menger para la Conexidad Puntual. Si v y w son vértices no adyacentes en una gráfica G,
entonces el número máximo de trayectorias internamente disjuntas v-w es igual al número de vértices de
un conjunto mínimo de corte v-w.
Teorema de Menger para la Conexidad Lineal
La versión puntual del teorema de Menger discutida en la sección anterior tiene analogías para el caso de
la conexidad lineal. Sean v y w dos vértices en una gráfica G. Un conjunto S de aristas es un conjunto de
aristas de corte v-w si v y w están en componentes diferentes de G – S; esto es, si cada trayectoria v-w
contiene una arista de S. La máxima cardinalidad de un conjunto de corte lineal v-w es la conexidad lineal v-
w y es denotada por .
El máximo número 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 común.
Por ejemplo, consideremos de nuevo la siguiente gráfica
Es fácil ver que tanto como son 5. El que los dos parámetros sean iguales en este caso no
es de nuevo, una mera coincidencia, y el hecho que esto es cierto en general es la versión local lineal del
teorema de Menger. Comprueba el resultado encontrando las cinco trayectorias que no tienen aristas en
común, y un conjunto de corte lineal que contiene al menos cinco aristas y separa la gráfica al eliminarlas
(no encontrarás un conjunto que contenga menos de cinco aristas).
Teorema de Menger para la Conexidad Lineal. Para cualesquiera vértices v y w en una gráfica G,
.
3.4. Programación
En esta sección presentamos el desarrollo completo de dos algoritmos: uno que resuelve el problema del
flujo máximo en una red, y el otro que encuentra la conexidad lineal de una gráfica. Encontrarás tanto el
pseudocódigo como el código en Java que puedes probar en tu entorno IDE Eclipse.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
37
37
3.4.1. Solución de problemas de redes
1. Teorema del Corte Mínimo y Flujo Máximo
Pseudocódigo:
Paso 1.
Flujo máximo y corte mínimo.
Paso 2.
Entradas: El número de vértices “vertice” y el número de aristas “aristas”, vértice de inicio o fuente “fuente”
y el vértice final, sumidero o destino “destino”, valores de la red: vértices de “p[ ]” a “q[ ]”; la capacidad de
cada arista “cap[ ]”.
Salidas: cantidad de flujo de cada vértice “flujovertice[]”, cantidad de flujo por cada arista “flujoarista[]”,
vértices del corte mínimo “cortemin[]”.
1. Inicio.
2. Inicialización 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 vértices adyacentes a la fuente.
4. Mientras el flujo de entrada sea igual al flujo de salida del vértice
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:
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
38
38
Solución (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("Vértices del corte mínimo: ");
for (int i = 1; i <= vertice; i++)
if (cortemin[i] == 1)
System.out.print(" " + i);
System.out.println("\n\nCantidad de flujo por cada uno de los vértices:" +
"\n\n Vertice flujo");
for (int i = 1; i <= vertice; i++)
System.out.printf("%4d%7d\n",i,flujovertice[i]);
System.out.println("\nCantidad de flujo por cada una de las aristas:\n\n de hasta flujo");
for (int i = 1; i <= flujoarista[0]; i++)
System.out.printf("%2d%6d%7d\n",p[i],q[i],flujoarista[i]);
System.out.print("\nNOTA: En aquellas aristas que no aparecen, el flujo es cero (0)");
}
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
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;
// Creación de aristas sustitutas
j = aristas;
for (i = 1; i <= aristas; i++) {
j++;
p[aristas+i] = q[i];
q[aristas+i] = p[i];
cap[aristas+i] = 0;
}
aristas = aristas + aristas;
// Inicialización
for (i = 1; i <= vertice; i++)
primarista[i] = 0;
flujo = 0;
for (i = 1; i <= aristas; i++) {
flujoarista[i] = 0;
j = p[i];
if (j == fuente)
flujo += cap[i];
primarista[j]++;
}
flujovertice[fuente] = flujo;
NY = 1;
for (i = 1; i <= vertice; i++) {
j = primarista[i];
primarista[i] = NY;
mapeoi[i] = NY;
NY += j;
}
termino = false;
A = true;
// Ordenamiento de aristas en orden lexicográfico
etiqueta1:
while (true) {
aux = 0;
B = false;
etiqueta2:
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
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 <= 0) {
if (cont1 > 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) cont2 = cont1;
A = false;
}
if (A) {
aristas1 = aristas;
cont1 = 1 + aristas / 2;
cont1--;
cont2 = cont1;
}
A = true;
NP = cont2 + cont2;
if (NP < aristas1) {
NQ = NP + 1;
aux = -2;
}
else {
if (NP == aristas1) {
NQ = cont2;
cont2 = NP;
aux = -1;
}
else {
if (cont1 > 1) {
cont1--;
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
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) {
//Obtención del flujo máximo en cada arista
j = 0;
for (i = 1; i <= aristas; i++)
if (flujoarista[i] > 0) {
j++;
p[j] = p[i];
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
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 <= aristas; i++) {
NV = q[i];
p[i] = mapeoi[NV];
mapeoi[NV]++;
}
}
etiqueta3:
while (true) {
if (!G) {
if (!C) {
aux = 0;
for (i = 1; i <= vertice; i++) {
if (i != fuente)
flujovertice[i] = 0;
mapeoj[i] = aristas + 1;
if (i < vertice) mapeoj[i] = primarista[i + 1];
cortemin[i] = 0;
}
entrada = 0;
salida = 1;
mapeoi[1] = fuente;
cortemin[fuente] = -1;
while (true) {
entrada++;
if (entrada > salida)
break;
NU = mapeoi[entrada];
aristas2 = mapeoj[NU] - 1;
fin = primarista[NU] - 1;
while (true) {
fin++;
if (fin > 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 <= vertice; i++)
cortemin[i] = -cortemin[i];
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
43
43
for (i=1; i<=aristas; i++) {
NU = q[p[i]];
if (flujoarista[i] < 0)
flujovertice[NU] -= flujoarista[i];
p[i] = NU;
}
flujovertice[fuente] = flujovertice[destino];
termino = true;
continue etiqueta1;
}
cortemin[destino] = 1;
}
while (true) {
if (!C) {
entrada--;
if (entrada == 0)
break;
NU = mapeoi[entrada];
NP = primarista[NU] - 1;
NQ = mapeoj[NU] - 1;
}
C = false;
while (NP != NQ) {
NV = q[NQ];
if ((cortemin[NV] <= 0) ||(cap[NQ] == flujoarista[NQ])) {
NQ--;
continue;
}
else {
q[NQ] = -NV;
cap[NQ] -= flujoarista[NQ];
flujoarista[NQ] = 0;
NP++;
if (NP < NQ) {
p[p[NP]] = NQ;
p[p[NQ]] = NP;
B = true;
continue etiqueta2;
}
break;
}
}
if (NP >= primarista[NU])
cortemin[NU] = NP;
}
NW = 0;
for (i=1; i<=salida; i++)
if (cortemin[mapeoi[i]] > 0) {
NW++;
mapeoi[NW] = mapeoi[i];
}
// Encuentra el flujo más factible
aux = -1;
NX = 1;
}
etiqueta4:
while (true) {
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
44
44
if (!G) {
if (!F) {
if (!D && !E)
NU = mapeoi[NX];
if ((flujovertice[NU] <= 0) || D || E) {
if (!E) {
D = false;
NX++;
if (NX <= NW) continue etiqueta4;
parm = 0;
}
E = false;
NX--;
if (NX != 1) {
NU = mapeoi[NX];
if (flujovertice[NU] < 0) {
E = true;
continue etiqueta4;
}
if (flujovertice[NU] == 0) {
//Flujos acumulados
aristas2 = aristas + 1;
if (NU < vertice)
aristas2 = primarista[NU + 1];
fin = mapeoj[NU];
mapeoj[NU] = aristas2;
while (true) {
if (fin == aristas2) {
E = true;
continue etiqueta4;
}
j = p[fin];
flujo = flujoarista[j];
flujoarista[j] = 0;
cap[j] -= flujo;
flujoarista[fin] -= flujo;
fin++;
}
}
if (primarista[NU] > cortemin[NU]) {
fin = mapeoj[NU];
do {
j = p[fin];
flujo = flujoarista[j];
if (flujovertice[NU] < flujo)
flujo = flujovertice[NU];
flujoarista[j] -= flujo;
flujovertice[NU] -= flujo;
NV = q[fin];
flujovertice[NV] += flujo;
fin++;
}
while (flujovertice[NU] > 0);
flujovertice[NU] = -1;
E = true;
continue etiqueta4;
}
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
45
45
fin = cortemin[NU] + 1;
F = true;
continue etiqueta4;
}
for (i = 1; i <= aristas; i++) {
NV = -q[i];
if (NV >= 0) {
q[i] = NV;
j = p[i];
cap[i] -= flujoarista[j];
flujo = flujoarista[i] - flujoarista[j];
flujoarista[i] = flujo;
flujoarista[j] = -flujo;
}
}
continue etiqueta3;
}
// Se da el flujo máximo a la arista saliente del vertice
fin = cortemin[NU] + 1;
}
}
while (true) {
if (!G) {
F = false;
fin--;
if (fin < primarista[NU])
break;
NV = -q[fin];
if (flujovertice[NV] < 0)
continue;
flujo = cap[fin] - flujoarista[fin];
if (flujovertice[NU] < flujo)
flujo = flujovertice[NU];
flujoarista[fin] += flujo;
flujovertice[NU] -= flujo;
flujovertice[NV] += flujo;
parm = 1;
NP = p[fin];
NQ = mapeoj[NV] - 1;
if (NP < NQ) {
p[p[NP]] = NQ;
p[p[NQ]] = NP;
B = true;
continue etiqueta2;
}
if (NP == NQ)
mapeoj[NV] = NQ;
}
G = false;
if (flujovertice[NU] > 0)
continue;
if (cap[fin] == flujoarista[fin]) fin--;
break;
}
cortemin[NU] = fin;
if (parm != 0) {
D = true;
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
46
46
continue etiqueta4;
}
//Se eliminan los excesos de flujo entrantes de los vertices
fin = mapeoj[NU];
do {
j = p[fin];
flujo = flujoarista[j];
if (flujovertice[NU] < flujo) flujo = flujovertice[NU];
flujoarista[j] -= flujo;
flujovertice[NU] -= flujo;
NV = q[fin];
flujovertice[NV] += flujo;
fin++;
} while (flujovertice[NU] > 0);
flujovertice[NU] = -1;
E = true;
continue etiqueta4;
} } } } } }
Resultado:
Vértices del corte mínimo: 1 2 3 4 5 6 7 8 9
Cantidad de flujo por cada uno de los vértices:
Vertice flujo
1 14
2 6
3 5
4 3
5 8
6 0
7 6
8 8
9 0
Consola
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
47
47
10 6
11 14
Cantidad de flujo por cada una de las aristas:
de hasta flujo
1 2 6
1 3 5
1 4 3
2 5 6
3 5 2
3 7 3
4 7 3
5 8 8
7 10 6
8 11 8
10 11 6
NOTA: En aquellas aristas que no aparecen, el flujo es cero (0)
2. Conexidad Lineal
Pseudocódigo:
Paso 1.
Conexidad lineal de una gráfica.
Paso 2.
Entradas: El número de vértices “vertice” y el número de aristas “aristas”, valores de la red: vértices de “p[ ]”
a “q[ ]”.
Salidas: La conexidad lineal “conex” de la gráfica.
1. Inicio.
2. Inicialización de variables
i ← 0, j ← 0, destino ← 0
cortemin[vertice+1] ← 0
aristai[4*aristas+1] ← 0
aristaj[4*aristas+1] ← 0
cap[4*aristas+1] ← 0
flujoaristas[4*aristas+1] ← 0
flujovertice[4*aristas+1] ← 0
conex ← vertice
fuente ← 1 // Toma el vértice 1 como la fuente
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
48
48
aristas2 ← aristas + aristas.
3. for j=2… vertice
Toma el vertice j como el destino
Asigna una capacidad unitaria a todas las aristas para ambas direcciones
Encuentra el valor del flujo máximo f(j) resultante en la gráfica
end-for.
4. La conexidad lineal es igual al número mínimo de f(j) para j=2…vertice.
5. Fin.
Ejemplo:
Solución (Programa en Java):
package maxflow;
public class Prueba_ConexidadLineal extends Object{
public static void main(String args[]) {
int conex;
int vertice = 7;
int aristas = 12;
int p[] = {0,4,6,4,3,6,3,2,6,2,1,3,2};
int q[] = {0,7,4,5,7,3,5,7,2,5,4,1,1};
conex = Conexidad.ConexidadLineal(vertice,aristas,p,q);
System.out.println("La conexidad lineal de la gráfica G es = " + conex);
}
}
////////////////////////////////////////////////////////////////////////////////
package maxflow;
public class Conexidad {
public static int ConexidadLineal(int vertice, int aristas, int p[], int q[]){
int i,j,conex,aristas2,fuente,destino;
int cortemin[] = new int[vertice+1];
int aristai[] = new int[4*aristas+1];
int aristaj[] = new int[4*aristas+1];
int cap[] = new int[4*aristas+1];
int flujoaristas[] = new int[4*aristas+1];
int flujovertice[] = new int[4*aristas+1];
conex = vertice;
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
49
49
fuente = 1;
aristas2 = aristas + aristas;
for (destino = 2; destino <= vertice; destino++) {
// Construir la red
for (i = 1; i <= 4*aristas; i++) {
aristai[i] = 0;
aristaj[i] = 0;
cap[i] = 0;
}
// Ducplicado de aristas
j = 0;
for (i = 1; i <= aristas; i++) {
j++;
aristai[j] = p[i];
aristaj[j] = q[i];
cap[j] = 1;
j++;
aristai[j] = q[i];
aristaj[j] = p[i];
cap[j] = 1;
}
// Manda llamar el algoritmo de flujo máximo
Maxflow.FlujoMaxCorteMin(vertice,aristas2,aristai,aristaj,cap,fuente,destino,cortemin,fluj
oaristas,flujovertice);
if (flujovertice[fuente] < conex) conex = flujovertice[fuente];
}
return conex;
}
}
La conexidad lineal de la gráfica G es = 3 Consola
Actividad 3. Análisis de conexidad
Al finalizar esta actividad serás capaz de analizar gráficas para determinar su conexidad.
Instrucciones: resuelve cada uno de los problemas planteados de acuerdo a los lineamientos que se
solicitan en cada uno de ellos.
1. Descarga el documento llamado “Act. 3. Análisis de conexidad”
2. Resuelve cada uno de los problemas que ahí se presentan.
3. Guarda tu documento con la siguiente nomenclatura MCOM1_U3_A3_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. Envía tu documento a tu Facilitador(a) y espera su retroalimentación
5.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
50
50
Autoevaluación
Es momento que realices la autoevaluación, donde podrás medir el nivel de conocimiento adquirido
durante la unidad.
Instrucciones: elige la respuesta correcta que corresponda a la pregunta planteada.
1. ¿Cuál es la secuencia de vértices en la que cada par consecutivo está conectado?
a) Arista b) Trayectoria c) Gráfica d) Red
2. Si para cada par de vértices existe una trayectoria entre ellos, se dice que la gráfica es
a) Completa b) Cíclica c) Conexa d) Ciclo
3. El problema del flujo de una red consiste en
a) Encontrar el flujo máximo para la red
b) Encontrar el flujo mínimo para la red
c) Encontrar la trayectoria de flujo más corta
d) Encontrar la gráfica que representa a la red
4. Un conjunto de componentes conexos forma una gráfica
a) Conexa b) Cíclica c) No dirigida d) Disconexa
5. El método Ford y Fulkerson empieza considerando
a) Un flujo máximo
b) Un flujo cero c) Todas las
aristas llenas d) Cortes
máximos
Para comparar tus respuestas, revisa el documento “Respuestas_autoevaluación_U3, ubicada en la
pestaña material de apoyo.
RETROALIMENTACION
1-3 aciertos. Los conocimientos obtenidos no fueron suficientes, debes revisar nuevamente el contenido
de la unidad.
4-5 aciertos. Tienes un conocimiento claro de los conceptos manejados en la Unidad. ¡Sigue adelante!.
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
51
51
Evidencia de Aprendizaje. programación de algoritmos para resolver problemas de
redes
Al finalizar esta actividad serás capaz de aplicar el teorema del corte mínimo – flujo máximo para encontrar
el flujo máximo que puede fluir por una red y obtendrás una herramienta para determinar si dos matrices
de adyacencia representan una misma gráfica.
1. Descarga el documento llamado “EA_Presentación de resultados”
2. Resuelve los problemas que se plantean en el documento descargable
3. Guarda tu documento con la nomenclatura MCOM1_U3_EA_XXYZ. Y envía tu archivo al Portafolio
de Evidencias. Recuerda sustituir las XX por las dos primeras de tu primer nombre, la Y por la
inicial de tu apellido paterno y la por la inicial de tu apellido materno.
4. Espera la retroalimentación de tu Facilitador(a), atiende sus comentarios y reenvía la nueva
versión de tu evidencia, en caso de que sea requerido.
5. Consulta la Escala de Evaluación para conocer los criterios con que será evaluado tu trabajo.
Cierre de la Unidad
Pudiste comprobar que las redes aparecen en casi cualquier área del quehacer humano, desde los
circuitos eléctricos hasta las redes sociales, y requieren soluciones para sus problemas. En esta unidad
tuviste la oportunidad de aprender los fundamentos de las redes que te permiten analizarlas y proponer
soluciones a sus problemas de flujo.
Comprobaste también que la teoría de gráficas aporta una plataforma para representar las redes en el
ámbito matemático. Aprendiste conceptos, teoremas y algoritmos para computadora alrededor de esta
teoría que te ayudan a resolver problemas de las representaciones de las redes.
Aprendiste conceptos, métodos y algoritmos que te permiten analizar la conexidad de las gráficas.
Finalmente conociste el código ejecutable en una computadora de algoritmos relacionados con gráficas y
flujo en redes.
Para saber más
Consulta los siguientes links:
Acerca de algoritmos de corte mínimo – flujo máximo:
http://people.cs.pitt.edu/~kirk/cs1501/animations/Network.html
Programa desarrollado Unidad 3. Redes
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
52
52
http://www.cse.yorku.ca/~aaw/Wang/MaxFlowStart.htm
Acerca de flujo en redes de transporte: cb.mty.itesm.mx/tc1003/lecturas/tc1003-117.pdf
Acerca de representaciones, redes y flujos:
http://polimedia.upv.es/catalogo/mobile/curso.asp?curso=615b1ab8-bf46-294f-a53a-457977bfea87
Fuentes de consulta
Cormen, T., Leiserson, C., Rivest, R., Stein, C. (2009) Introduction to Algorithms. 3rd Ed. The MIT
Press. Cambridge, Massachusetts USA.
Heineman, G., Pollice, G., Selkow, S. Algorithms in a Nutshell. (2009) O’Reilly Media, Inc. 1st Ed.
USA.
Karzanov, A. V. (1974) Determining a Maximal Flow in a Network by the Method of Preflows. Soviet
Math. Dokl., 15, No.2, 434-437. (http://alexander-karzanov.net/flows&multiflows.html)
Goldberg, A., Tarjan, R. (1988) A New Approach to the Maximum-Flow Problem. Journal of the
Association for Computing Machinery, Vol. 35, No. 4.
Gross, J., Yellen, J. (2006). Graph Theory and Its Applications. Chapman & Hall/CRC Press. 2nd Ed.
USA.