Aplicación del algoritmo ford fulkerson en maple

Universidad de Guanajuato
División de Ingenierías Campus Irapuato-Salamanca

Algoritmo de Ford-Fulkerson

CONTENIDO
INTRODUCCIÓN OBJETIVO MARCO TEÓRICO GRAFO DIRIGIDO GRAFO ETIQUETADO Y PONDERADO RED DE TRANSPORTE FLUJO CORTE ALGORITMO DE FORD-FULKERSON TEOREMA DE FLUJO MÁXIMO-CORTE MÍNIMO PROBLEMA DESARROLLO MANUAL DESARROLLO EN MAPLE™ CONCLUSIONES BIBLIOGRAFÍA APÉNDICE: CÓDIGOSPSEUDOCÓDIGO IMPLEMENTACIÓN EN PHYTON CÓDIGO DE MATLAB® 2 2 3 3 3 3 4 5 6 7 7 8 11 12 12 13 13 13 15

DIVISIÓN DE INGENERÍAS, CAMPUS IRAPUATO- SALAMANCA

2 U N I V E R S I D A D D E G U A N A J U A T O

INTRODUCCIÓN
En muchas áreas de aplicación de la ingeniería existen problemas denominados “de flujo”. Se puede definir el flujo como el movimiento de partículas cualesquiera que se traslada de unpunto a otro. Dichas partículas pueden ser:  Líquidos que fluyen a través de tubos  Partes de líneas de ensamble  Corrientes sobre redes eléctricas  Información a través de redes de comunicación  Luz en la fibra óptica, etc. En estos sistemas de flujo existen limitantes conocidas como capacidad máxima de flujo, y que determinan la cantidad máxima de partículas que puede pasar a través de lasconexiones en estas redes de flujo, por ejemplo, 200 litros de líquido por hora en un tubo, 20 amperes de corriente eléctrica, la cantidad de automóviles que pueden transitar en una autopsita, etc. Algunas ocasiones es necesario conocer la tasa más grande a la cual se puede trasladar el material de una fuente a un destino, dentro de las restricciones de capacidad dadas por el sistema. Existe unalgoritmo llamado de Ford-Fulkerson, desarrollado para resolver este tipo de problemas.

OBJETIVO
Al finalizar este trabajo el alumno deberá ser capaz de resolver problemas de flujo máximo utilizando el algoritmo de Ford-Fulkerson, comparando sus resultados con el algoritmo implementado por el software Maple™ para verificar su congruencia.

DIVISIÓN DE INGENERÍAS, CAMPUS IRAPUATO- SALAMANCA

3 UN I V E R S I D A D D E G U A N A J U A T O

MARCO TEÓRICO
Grafo dirigido Sea G un grafo. Si cada arista en G tiene una dirección, las aristas en este tipo de gafo se transforman en flechas, entonces G se llama grafo dirigido o dígrafo y sus aristas se llaman arcos. Estos arcos tienen una dirección unívoca. El vértice donde empieza un arco se llama punto inicial y el vértice donde termina sellama punto Terminal. Cuando no se consideran las direcciones de las aristas en G, el grafo que se obtiene se llama grafo subyacente de G. Grafo etiquetado y ponderado Un grafo G es un grafo etiquetado si sus aristas y/o vértices tienen asignado alguna identificación. En particular, G es un grafo ponderado si a cada arista e de G se le asigna un número no negativo w(e) denominado peso o longitud dee. El peso (o longitud de un camino en un grafo ponderado G se define como la suma de los pesos de las aristas del camino. Un importante problema en teoría de grafos es encontrar el camino más corto (liviano), esto es, el camino con el peso (longitud) mínimo entre dos vértices dados.

Figura1: Ejemplo de un grafo ponderado

Los pesos de las aristas se guardan en una matriz, de manera que elpeso de (i,j) está en A[i,j]. La siguiente matriz muestra los pesos de las matrices del grafo de la figura 1.

Red de transporte Una red de transporte = (, , , ) es un grafo dirigido = (, ) con dos vértices distinguidos s y t, la fuente y el destino, respectivamente; y una función c llamada

DIVISIÓN DE INGENERÍAS, CAMPUS IRAPUATO- SALAMANCA

4 U N I V E R S I D A D D E G U A N A J U A T Ocapacidad que asigna a cada arco = , ∈ (), un valor entero no negativo = (, ) llamado la capacidad del arco .

Figura 2: Dos ejemplos de redes de flujo

Flujo Sea G = (V,E) uan 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 valores reales : → que satisface las siguientes tres propiedades:   ...