• Author / Uploaded
• Rodrigo Jesus Ramirez Tomasini

Citation preview

Programa desarrollado Unidad 3. Redes

Universidad Abierta y a Distancia de México

Licenciatura en Matemáticas Computación I

6° Cuatrimestre

Unidad 3. Redes

Clave: 050920621/060920621

Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 1

1

Programa desarrollado Unidad 3. Redes

Í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

Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 2

2

Programa desarrollado Unidad 3. Redes 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.

Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 3

3

Programa desarrollado Unidad 3. Redes 

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.

Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 4

4

Programa desarrollado Unidad 3. Redes 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 nodirigida; 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/).

Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 5

5

Programa desarrollado Unidad 3. Redes

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 Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 6

6

Programa desarrollado Unidad 3. Redes 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. Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 7

7

Programa desarrollado Unidad 3. Redes 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:

Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 8

8

Programa desarrollado Unidad 3. Redes

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á

Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 9

9

Programa desarrollado Unidad 3. Redes 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.

Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 10

10

Programa desarrollado Unidad 3. Redes 

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. Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 11

11

Programa desarrollado Unidad 3. Redes 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

B

C

D

E

F

G

H

I

J

K

L

M

1 1 1 0 0 1 1 0 0 0 0 0 0

1 1 0 0 0 0 0 0 0 0 0 0 0

1 0 1 0 0 0 0 0 0 0 0 0 0

0 0 0 1 1 1 0 0 0 0 0 0 0

0 0 0 1 1 1 1 0 0 0 0 0 0

1 0 0 1 1 1 0 0 0 0 0 0 0

1 0 0 0 1 0 1 0 0 0 0 0 0

0 0 0 0 0 0 0 1 1 0 0 0 0

0 0 0 0 0 0 0 1 1 0 0 0 0

0 0 0 0 0 0 0 0 0 1 1 1 1

0 0 0 0 0 0 0 0 0 1 1 0 0

0 0 0 0 0 0 0 0 0 1 0 1 1

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; Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 12

12

Programa desarrollado Unidad 3. Redes int a[maxV][maxV]; void matrizady(){ int j, x, y; // Instrucciones para leer V y A for (x = 1; x v); }

Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 16

16

Programa desarrollado Unidad 3. Redes 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). Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 17

17

Programa desarrollado Unidad 3. Redes 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

Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 18

18

Programa desarrollado Unidad 3. Redes 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, Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 19

19

Programa desarrollado Unidad 3. Redes 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.

Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 20

20

Programa desarrollado Unidad 3. Redes Redes de Flujo y Flujos Una red de flujo no-negativa

es una gráfica dirigida en la cual cada arista .

Requerimos además que si A contiene una arista inversa. Si

tiene una capacidad

, entonces no existe una arista

, entonces por conveniencia definimos

en la dirección

, 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 {

Conservación del flujo: Para todo ∑

.

}, se requiere

∑

Cuando

, no puede haber flujo desde u a v, y el flujo del vértice u al vértice v. El valor | | de un flujo f se

Llamamos a la cantidad no-negativa define como | |

, se requiere

∑

∑

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. Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 21

21

Programa desarrollado Unidad 3. Redes 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. Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 22

22

Programa desarrollado Unidad 3. Redes 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 f es un flujo, entonces el flujo neto f(S, T) a través del corte (S, T) se define como

y

. Si

Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 23

23

Programa desarrollado Unidad 3. Redes ∑∑

∑∑

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.

Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 24

24

Programa desarrollado Unidad 3. Redes

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.

Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 25

25

Programa desarrollado Unidad 3. Redes 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.

Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 26

26

Programa desarrollado Unidad 3. Redes 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.

Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 27

27

Programa desarrollado Unidad 3. Redes 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

Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 28

28

Programa desarrollado Unidad 3. Redes 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.

Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 29

29

Programa desarrollado Unidad 3. Redes 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. Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 30

30

Programa desarrollado Unidad 3. Redes Lo siguiente caracteriza los vértices de corte: { } tales

Si G(V, A) es una gráfica conexa, entonces v es un vértice de corte si existen vértices 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. Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 31

31

Programa desarrollado Unidad 3. Redes 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 siguiente teorema:

descubierta por Whitney en 1932 que dio origen al

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 Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 32

32

Programa desarrollado Unidad 3. Redes

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. Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 33

33

Programa desarrollado Unidad 3. Redes 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. Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 34

34

Programa desarrollado Unidad 3. Redes 

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 Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 35

35

Programa desarrollado Unidad 3. Redes 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 vw y es denotada por . El máximo número de trayectorias lineales disjuntas v-w en G se denota por tales trayectorias debe contener una arista de cada conjunto de corte lineal v-w,

. Dado que cada una de .

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. Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 36

36

Programa desarrollado Unidad 3. Redes 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:

Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías 37

37

Programa desarrollado Unidad 3. Redes

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