Matemáticas - Teoría de grafos

Algoritmos de grafos

red de flujo es un grafo dirigido donde existen dos vértices especiales, uno llamado fuente, al que se le asocia un flujo positivo y otro llamadosumidero que tiene un flujo negativo y a cada arista se le asocia cierta capacidad positiva. En cada vértice diferente a los dos especiales se mantiene la ley de corrientes de Kirchoff, en donde la suma de flujos entrantes a un vértice debe ser igual a la suma de flujos que salen de él. Puede ser utilizada para modelar el tráfico en un sistema de autopistas, fluidos viajando en tuberías, corrientes eléctricas en circuitos eléctricos o sistemas similares por lo que viaje algo entre nodos.

Descripción matemática

Una red de flujo es un grafo dirigido ${\displaystyle G=(V,E)}$ en donde cada arco ${\displaystyle (u,v)\in E}$ tiene una capacidad no negativa ${\displaystyle c(u,v)\geq 0}$.

Se distinguen dos vértices: la fuente s y el destino t.

Se supone que cada vértice se encuentra en alguna ruta de s a t.

Un flujo en G es una función ${\displaystyle f:V\times V\mapsto R}$ tal que

• Restricción de capacidad: ${\displaystyle \forall \quad u,v\in V,\quad f(u,v)\leq c(u,v)}$
• Simetría: ${\displaystyle f(u,v)=-f(v,u)\,}$
• Conservación: ${\displaystyle \forall u\in V-\left\{s,t\right\}\quad \sum _{v\in V}f(u,v)=0}$

El valor del flujo es ${\displaystyle |f|=\sum _{v\in V}f(s,v)}$

El problema del flujo máximo trata de maximizar este flujo.

Algoritmo de flujo máximo

Tenemos el conocido problema de flujo máximo o maximal: ¿cuál es la tasa mayor a la cual el material puede ser transportado de la fuente al sumidero sin violar ninguna restricción de capacidad?

En otras palabras, el problema consiste en determinar la máxima capacidad de flujo que puede ingresar a través de la fuente y salir por el nodo de destino.

El procedimiento para obtener el flujo máximo de una red, consiste en seleccionar repetidas veces cualquier trayectoria de la fuente al destino y asignar el flujo máximo posible en esa trayectoria.

Capacidad residual: es la capacidad adicional de flujo que un arco puede llevar:

${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)\,}$

• Dada una red de flujo máximo, plantee la red residual asociada.

• Encuentre la trayectoria de la fuente al destino con capacidad de flujo estrictamente positivo (si no existe alguno, es por que se ha encontrado el óptimo).

• Examine estas trayectorias para encontrar la rama o arco con la menor capacidad de flujo restante e incremente en éste valor, la capacidad del flujo en sentido contrario.

• Determine todas las trayectorias estrictamente positivas, hasta que no se permita flujo del nodo a un nodo destino.

REDES DE FLUJO

La red de flujo es una representación gráfica de la solución de la ecuación de Laplace para  f y y con las condiciones de frontera existentes en el flujo.

Esta constituida por líneas equipotenciales separadas igualmente en f y por líneas de corriente igualmente separadas en y. Esta separación se conoce como canal de flujo o canal de corriente. Todas las intersecciones de la red son ortogonales.

Propiedades de las redes de flujo:

·        El caudal que fluye entre dos líneas consecutivas es el mismo por unidad de ancho.

·        Ni las líneas equipotenciales pueden cortarse entre sí, dentro del medio fluido, ni las líneas de corriente pueden cortarse entre sí dentro del medio fluido.

Se trata entonces de definir en cada caso las condiciones de frontera específicas del problema y trazar, cumpliendo con estas, las dos familias de curvas ortogonales, obteniendo así una verdadera imagen gráfica del problema, que si a sido realizada con cuidado podrá ser lo suficientemente buena para los fines ingenieriles.

Para el trazo de una red de flujo se tienen los siguientes pasos:

·        Dibujar los limites del dominio

·        Fijar tentativamente 3 ó 4 líneas de corriente.

·        Trazar tentativamente equipotenciales, ortogonales a las líneas de corriente

·        Ajustar

·        Comprobar la bondad del ajuste si al trazar las líneas diagonales de los cuadros se obtienen también curvas suaves, formando una nueva red

CALCULO DEL CAUDAL

Al trazar cualquier red de flujo se dibujan las equipotenciales de tal manera que la Dh sea la misma y que el Dq entre dos líneas de corriente sea el mismo.

Se tendrá entonces que:

Dq = KaDh/b

Si n_f es el número total de canales de la red y n_c el número de caídas de potencial que hay en toda la zona de flujo, entonces podrá escribirse:

Dq = q/n_f     y    Dh = h/n_c

Donde q y h son el caudal unitario total y la carga total.

A partir de lo anterior se puede llegar a que:

q/n_f = Ka h/n_c

q = (n_f/n_c) (a/b) kh

Puesto que q, k, h, n_f y n_c son constantes para una red de flujo dada, la relación a/b debe serlo también. Esta condición implica que se estén cumpliendo las dos condiciones iniciales (que la Dh sea la misma y que el Dq entre dos líneas de corriente sea el mismo).

El término n_f/n_c depende únicamente de la forma de la región de flujo, se le conoce como factor de forma y se representa:

F_f = n_f/n_c

El calculo de las presiones hidrodinámicas en el agua que se infiltra a través de la región de flujo, es una de las aplicaciones más útiles de una red de flujo.

FUERZAS DE INFILTRACIÓN

El agua circulando en un medio poroso, imparte energía a los granos sólidos por fricción. Considérese un  volumen de arena confinado, en el cual se tiene un nivel de agua h1 antes y un nivel h2 después de la arena.

La fuerza resultante en el volumen de arena es:

F = P1 – P2

Donde:

P1 = gh1A        P2 = gh2A

A es el área transversal de la muestra.

Sustituyendo:

F = (h1 – h2) gA

La dirección de F es paralela al flujo y puede localizarse dependiendo de la posición del centro de gravedad del elemento analizado.

Para suelos anisotrópicos, debe utilizarse el concepto de sección transformada.

EJEMPLOS DE REDES DE FLUJO

algoritmo de Dinic es un algoritmo de Tiempo polinómico para la computación de un Flujo maximal en una red de flujo, concebida en 1970 por el científico de la computación Yefim Dinitz, israelí de origen soviético.¹ El algoritmo es ejecutado en un tiempo de ${\displaystyle O(V^{2}E)}$ y está basado en el Algoritmo de Edmonds-Karp, el cual a su vez se ejecuta en un tiempo ${\displaystyle O(VE^{2})}$, y utiliza trayectorias de aumento más cortas. La introducción de los conceptos nivel de grafo y bloqueo de flujo es lo que define el rendimiento del algoritmo de Dinic.

Definición

Se tiene el grafo ${\displaystyle G=((V,E),c,s,t)}$ que será una red de flujo con ${\displaystyle c(u,v)}$ donde ${\displaystyle f(u,v)}$ es la capacidad y el flujo de el arco ${\displaystyle (u,v)}$ respectivamente.

Lacapacidad residual es un mapeo ${\displaystyle c_{f}:V\times V\to R^{+}}$ definido como,

1. Si ${\displaystyle (u,v)\in E}$,

   ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$

   ${\displaystyle c_{f}(v,u)=f(u,v)}$

2. ${\displaystyle c_{f}(u,v)=0}$ de otra manera.

Elgrafo residual es el grafo ${\displaystyle G_{f}=((V,E_{f}),c_{f}|_{E_{f}},s,t)}$, donde

${\displaystyle E_{f}=\{(u,v)\in V\times V:c_{f}(u,v)>0\}}$.

Latrayectoria de aumento es una ruta ${\displaystyle s-t}$ en el grafo residual ${\displaystyle G_{f}}$.

Se define ${\displaystyle \operatorname {dist} (v)}$ como la longitud del camino más corto desde ${\displaystyle s}$ hasta ${\displaystyle v}$ en ${\displaystyle G_{f}}$.Entonces el nivel del grafo de ${\displaystyle G_{f}}$ es el grafo ${\displaystyle G_{L}=(V,E_{L},c_{f}|_{E_{L}},s,t)}$, donde

${\displaystyle E_{L}=\{(u,v)\in E_{f}:\operatorname {dist} (v)=\operatorname {dist} (u)+1\}}$.

El bloqueo del flujo es un ${\displaystyle s-t}$ flujo ${\displaystyle f}$ de manera tal que el grafo ${\displaystyle G'=(V,E_{L}',s,t)}$ con ${\displaystyle E_{L}'=\{(u,v):f(u,v)$ no tiene ninguna ruta ${\displaystyle s-t}$.

Algoritmo

Algoritmo de Dinic

Entrada: Una red ${\displaystyle G=((V,E),c,s,t)}$.

Salida: Un flujo ${\displaystyle s-t}$ ${\displaystyle f}$ de valor maximizado.

1. Se tiene ${\displaystyle f(e)=0}$ para cada ${\displaystyle e\in E}$.
2. Construir${\displaystyle G_{L}}$ desde ${\displaystyle G_{f}}$ de ${\displaystyle G}$. Si ${\displaystyle \operatorname {dist} (t)=\infty }$, detener y retornar el resultado ${\displaystyle f}$.
3. Encontrar un bloqueo de flujo ${\displaystyle f\;'}$ en ${\displaystyle G_{L}}$.
4. Aumentar el flujo ${\displaystyle \ f}$ by ${\displaystyle f\;'}$ y volver al paso 2.

Análisis

Se puede demostrar que el número de arcos en cada bloqueo de flujo, es incrementado en al menos 1 unidad cada vez, y por lo tanto hay al menos ${\displaystyle n-1}$ bloqueos de flujo en el algoritmo, donde ${\displaystyle n}$ es el número de vértices en la red. El nivel del grafo ${\displaystyle G_{L}}$ puede ser construido por Breadth-first search en un tiempo de ${\displaystyle O(E)}$ y un bloqueo de flujo en cada nivel del grafo puede ser encontrado en un tiempo de ${\displaystyle O(VE)}$. Por lo tanto, el tiempo del algoritmo de Dinic es de ${\displaystyle O(V^{2}E)}$.

Usando una estructura de datos llamada árboles dinámicos, el tiempo de ejecución para encontrar un bloqueo de flujo en cada fase puede ser reducido a ${\displaystyle O(E\log V)}$ y por lo tanto el tiempo de ejecución del algoritmo de Dinic puede ser reducido a ${\displaystyle O(VE\log V)}$.

Casos Especiales

En redes con capacidades de unidad, el tiempo de ejecución es mucho mayor. Cada bloqueo de flujo puede ser encontrado en un tiempo de ${\displaystyle O(E)}$, y es demostrable que el número de fases no excedan ${\displaystyle O({\sqrt {E}})}$ y ${\displaystyle O(V^{2/3})}$. En estos casos el algoritmo se ejecuta en un tiempo de ${\displaystyle O(\min(V^{2/3},E^{1/2})E)}$.

En las redes surgidas durante la solución del problema de apareamiento, el número de fases está limitado por ${\displaystyle O({\sqrt {V}})}$,lo cual resulta en un limitado tiempo de ${\displaystyle O({\sqrt {V}}E)}$. El algoritmo resultante a raíz de esto es conocido como algoritmo Hopcroft–Karp. De manera más general, este límite se mantiene para cualquier red unitaria — un tipo de red en la que cada vértice, excepto para los vértices fuente y sumidero, o bien tienen un único arco de capacidad, o un único arco con salida, y todas las demás capacidades son valores enteros arbitrarios.²

Ejemplo

Esta es una simulación del algoritmo de Dinic. En el nivel del grafo ${\displaystyle G_{L}}$, los vértices marcados en rojo son los valores ${\displaystyle \operatorname {dist} (v)}$. Las rutas en azul forman el bloqueo de flujo.

	${\displaystyle G}$	${\displaystyle G_{f}}$	${\displaystyle G_{L}}$
1.
	El bloqueo de flujo está constituido por ${\displaystyle \{s,1,3,t\}}$ con 4 unidades de flujo, ${\displaystyle \{s,1,4,t\}}$ con 6 unidades de flujo, and ${\displaystyle \{s,2,4,t\}}$ con 4 unidades de flujo. Por lo tanto el bloqueo del flujo es de 14 unidades y el valor del flujo ${\displaystyle |f|}$ es 14. Note que cada ruta de aumento en el flujo de bloqueo tiene 3arcos.
2.
	El bloqueo de flujo está constituido por ${\displaystyle \{s,2,4,3,t\}}$ con 5 unidades de flujo. Por lo tanto el bloqueo del flujo es de 5 unidades y el valor del flujo ${\displaystyle |f|}$ es 14 + 5 = 19. Note que cada ruta de aumento en el flujo de bloqueo tiene 4 arcos.
3.
	Desde ${\displaystyle t}$ no puede ser alcanzado en ${\displaystyle G_{f}}$. El algoritmo termina y retorna un valor m'aximo de flujo de 19. Note que en cada bloqueo de flujo, el n'umero de arcos en la ruta de aumento se incrementa en al menos 1 valor.

Historia

El algoritmo de Dinic fue publicado en 1970 por el ex ruso científico de la computación Yefim (Chaim) A. Dinitz , quien hoy es miembro del departamento de Ciencias de la Computación en [Ben-Gurion University of the Negev]] (Israel). Dicha publicación se realizó antes que la del algoritmo Edmonds–Karp, el cual fue publicado en 1972, pero fue descubierta antes. Ambos demostraron cada uno por su cuenta, que en el algoritmo de Ford–Fulkerson, si cada ruta de aumento es la m'as corta, el largo de la ruta de aumento es no decreciente.