MODELOS DE REDES

En este capitulo se estudian los modelos de redes, que usan gráficas dirigidas, en esta sección aprenderemos a maximizar el flujo a través de una red. La red podría ser una red de transporte por la que fluyen bienes, una red de tuberías a través de la cual fluye el petróleo, una red de computadoras a través de la cual fluyen los datos, etc. En cada caso el problema consiste en determinar el flujo máximo. La maximización del flujo en una red es un problema que pertenece a la teoría de gráficas como a la investigación de operaciones. Las redes de Petri modelan sistemas en los que el procesamiento puede ocurrir de manera concurrente. El modelo proporciona un marco de referencia para tratar cuestiones como la posible operación de estancamiento en un sistema o el hecho de exceder la capacidad de los componentes de un sistema. 

RED DE TRANSPORTE

Considerando la siguiente gráfica dirigida (red de transporte), que representa una tubería de petróleo. El petróleo se descarga en el muelle a y se bombea por toda la red de la refinería z. Los vértices b,c,d y e representan estaciones de bombeo intermedias. Las aristas dirigidas representan subtuberías del sistema y muestran la dirección en que puede fluir el petróleo. Las etiquetas de las aristas indican las capacidades de las subtuberías. El problema es encontrar la manera de maximizar el flujo del muelle a la refinería y calcular el valor de este flujo máximo.

3e

Una red de transporte es una grafica dirigida, simple con pesos que satisface:

a) Un vértice fijo, designado como el origen o fuente, no tiene aristas de entrada.

b) Un vértice, designado como destino o sumidero, no tiene aristas salientes.

c) El peso Cij de la arista dirigida (i, j) llamada capacidad de (i, j) es un numero no negativo.

Si observamos la gráfica, el origen es el vértice a y el destino es el vértices z. La capacidad de la arista (a, b), C_{a, b} es 3 y la capacidad de la arista (b, c), C_{b, c} es 2. Un flujo en una red asigna un flujo a cada arista dirigida que no excede la capacidad de esa arista. Más aun, si se supone que el flujo que entra a un vértice v, que no es el origen y el destino, es igual al flujo que sale de v.

Ejemplo de red de transporte

Tomado con referencia la gráfica:

Sea G una red de transporte. Sea C_{ij} la capacidad de la arista dirigida (i, j) . Un flujo F en G asigna a cada arista dirigida (i, j) un numero no negativo F_{ij} tal que:

a. F_{ij} ≤ C_{ij}

b. Para cada vértice j, que no es la fuente ni el destino. 

Conservación de flujo

  

F_{ij} recibe el nombre de flujo en la arista (i, j). Para cualquier vértice j, 

Se llama flujo que entra a j y 

Se llama flujo que sale de j. 

Conservación de flujo significa para el ejemplo, que el petróleo no se usa ni se suministra en las estaciones de bombeo b, c, d y e.

Ahora, vamos a definir un flujo para la red del ejemplo asignando los valores:

F_{ab} = 2, F_{bc} = 2, F_{cz} = 3; F_{ad} = 3, F_{dc} = 1, F_{de} = 2, F_{ez} = 2

La gráfica quedaría,

Analizando, El flujo que entra al vértice d F_{ad} = 3 y es el mismo que sale del vértice d,

F_{dc} + F_{de} = 1 + 2 = 3

Se debe considerar que una arista e se etiqueta “x, y” si la capacidad de e es x y el flujo en e es y.

Observemos que el flujo que sale del origen (a) Fab + Fad, es igual al flujo que entra al destino (z) Fcz + Fez

F_{ab} + F_{ad} = 2 + 3 = 5

F_{cz} + F_{ez} = 3 + 2 = 5

Ambos valores son iguales a 5; a este valor lo denominamos valor del flujo F.

Sea F un flujo en una red G. el valor 

Se llama el valor del flujo F.

Tomando como base la teoría antes mencionada, ahora vamos a realizar los siguientes ejercicios.

Ejercicio 1

 

El ejemplo propuesto en la gráfica, nos permite explicar la “conservación del flujo” en una red de transporte.

En cada arista de la red, se encuentra un par o dupla de valores en unos casos completa y en otros incompleta faltando el segundo número de la dupla. El primer número de la dupla nos señala la “capacidad” que tiene la arista de la red denotada por C_{ij} que nos indica la capacidad de la arista dirigida (i, j), mientras el segundo número nos representa el “flujo” que esta transportando la arista de la red denotada por Fij que designa el flujo que transporta la arista dirigida (i, j), todo esto dentro de la red de transporte. Para resolver el problema propuesto, el flujo F en G asigna a cada arista dirigida (i, j) un número no negativo Fij, que cumple las siguientes condiciones:

1) Fij ≤ Cij, que quiere decir que el flujo que circula por cada arista debe ser menor o máximo igual a la capacidad que soporta dicha arista dentro de una red de transporte.

2) Para cada vértice j, que no sea la fuente ni el sumidero, se debe cumplir el siguiente principio: ,

que expresa que el flujo que llega a un vértice debe ser igual al flujo que sale de dicho vértice.

Para determinar los flujos faltantes de algunas de las aristas de aplicaremos las dos condiciones anteriormente expuestas.

Desarrollo:

a) Si analizamos la arista dirigida (a, d), se conoce la capacidad de la misma pero nos falta el flujo Fad, pero se puede observar que del vértice d sale la arista dirigida (d, e) cuyo flujo es conocido y es igual a 2 o sea Fde = 2 y aplicando la segunda condición se tiene que:

donde

F_{ad} = F_{de}, pero F_{de} = 2 por tanto F_{ad} = 2 que es el flujo faltante

b) Como es conocido el flujo de la arista dirigida (a, b) y que es Fab = 3, se puede determinar el flujo faltante Fbc, aplicando la segunda condición, que para este caso sería:

donde

F_{ab} = F_{bc}, pero F_{ab} = 3 por tanto F_{bc} = 3 que es el flujo faltante

c) Para conocer los otros flujos faltantes, para el presente caso se deberá considerar al mismo tiempo los flujos que llegan a los vértices y como los flujos que salen de los dos vértices antes mencionados, por la condición dos se tendrá:

Para el vértice c       Para el vértice e

F_{bc} = F_{ce} + F_{cz}       F_{ce} + F_{de} = F_{ez}

los flujos conocidos son:       los flujos conocidos son:

F_{bc} = 3       F_{de} = 2 y F_{ez} = 3

la ecuación que se forma es:       la ecuación que se forma es:

3 = F_{ce} + F_{cz}       F_{ce} + 2 = 3 existe una incógnita

despejamos F_{cz} = 3 - F_{ce} = 3 - 1 = 2       F_{ce} = 3 - 2 = 1 dato buscado

d) Para comprobar que los flujos obtenidos son los correctos, se tiene que revisar que la sumatoria de los flujos que salen del vértice “fuente”, deben ser igual a la suma de los flujos que llegan al vértice “destino o sumidero”, o sea:

F_{ab} + F_{ad} = F_{cz} + F_{ez}

3 + 2 = 2 + 3

5 = 5

Por tanto la red de transporte con los flujos completos que están en negrillas sería: 

• Ejercicio 2

Encuentre los flujos en las aristas que faltan de manera que el resultado sea un flujo en la red dada. Determine los valores de los flujos. 

ALGORITMO DE FLUJO MÁXIMO

Si G es una red de transporte, un flujo máximo en G es un flujo con valor máximo.

• Diseñar un algoritmo para determinar un valor máximo, consiste en iniciar con cierto flujo inicial e incrementar de manera interactiva el valor del flujo hasta que no pueda mejorarse mas.

• Podemos considerar un flujo inicial aquel en el que el flujo en cada arista es igual a cero.

• Para incrementar el valor de un flujo dado, debemos determinar un camino del origen al destino e incrementar el flujo a lo largo de este camino.

Notación

G denota una red con origen a, destino z y capacidad C

En principio denotaremos aristas no dirigidas

(Camino) P = (V0, V1,……………., Vn) Vo = a, V = z

Si una arista e en P esta dirigida de Vi-1 a Vi decimos que esta orientada en forma propia. 

 

Si podemos determinar un camino P de la forma del origen al destino en donde cada arista P esta orientada en forma propia y el flujo en cada arista es menor que la capacidad de la arista es posible aumentar el valor del flujo. 

Dada la siguiente red de transporte: 

 
Determinar un flujo máximo en la red, mediante el algoritmo 8.2.4

Desarrollo:

Las líneas 1 y 2 del algoritmo, nos permite inicializar el flujo con 0 para cada una de las aristas de la red. 

Las líneas 5 al 9 del algoritmo, permiten etiquetar los vértices como NULOS.

Las líneas 10 y 11 del algoritmo permite etiquetar el vértice a como (-,α) que es un par o dupla de valores, donde el primer elemento identifica el vértice “predecesor o anterior” y el segundo valor es el mínimo entre el incremento (∆) y la diferencia dada por Cvw - Fvw, donde la red resultante es:

En la línea 12 al conjunto U le añadimos el vértice a en este caso (vértice fuente o inicial).

A continuación la línea 13, da inicio al ciclo WHILE, que permite etiquetar los vértices que conectan las aristas que salen de a y al mismo tiempo elimina el vértice a de U, para nuestro caso las aristas (a, b) y (a, d) controlando que los vértices b y d no estén etiquetados. Luego de etiquetar los vértices anteriores, regresamos a la línea 13 y repetimos el ciclo WHILE, pero esta vez tomamos el vértice b y nos dirigimos a etiquetar el vértice c que se conecta con la arista (b, c) y c no esta etiquetado, se elimina el vértice b y se añade el vértice c a U. Regresamos a la línea 13 y repetimos el ciclo WHILE, como el vértice z no está etiquetado, tomamos cualquiera de los vértices que se encuentran en U pero observando que con los vértices que se conecta no se encuentren etiquetados, para nuestro caso tomamos el vértice c y cumplimos los requisitos que nos pide el algoritmo en las líneas que hagamos referencia, para nuestro caso c se conecta con z y z no está etiquetado, dando como resultado lo siguiente: 

Regresamos a la línea 13, ciclo WHILE, pero como z está etiquetado, saltamos a la línea 35, donde las líneas que le siguen nos permite determinar el conjunto P con el camino de los vértices comenzando desde z hacia atrás hasta llegar a a, donde el camino está dado por:

P = (a, b, c, z)

En la línea 43 del algoritmo hacemos ∆ = val(z) y asignamos el flujo a todas las aristas del camino identificado, conforme lo señalan las líneas del algoritmo que están a continuación de la línea 43.

La red con estos nuevos datos es la siguiente: 

Luego de obtener este primer camino, regresamos al inicio del algoritmo o sea a la línea 3 y volvemos a ejecutar las instrucciones como se lo hizo al inicio, con esto se determina otro camino y los flujos respectivos; pero hay que considerar que ahora algunas de las aristas ya tienen un flujo asignado por el anterior proceso. Este procedimiento continua hasta cuando el conjunto U este vacío, que se controla en la línea 15 y se puede dar por terminado el algoritmo. 

APLICACIÓN DE LOS GRAFOS

Actualmente nada funciona de manera individual, por el contrario existe una relación entre los distintos elementos que integran un sistema, trabajo o equipo.

Puesto que los grafos permiten modelar todo aquello que esta relacionado, es evidente que su aplicación es muy amplia y variada.

Reconocimiento de patrones mediante grafos de similaridad.

Los grafos permiten agrupar información con características semejantes. Esto implica formar subgrafos en donde los vértices de un subgrafo están relacionados entre si, pero no tienen relación con los subvertices del otro subgrafo,ya que no son similares. Una aplicación de este tipo de subgrafos se encuentra en el reconocimiento de patrones,  en donde agrupa información con propiedades muy parecidas de tal manera que se puedan detectar enfermedades como el cáncer, al agrupar conjunto de células que comparten características similares. Otra aplicación se encuentra en la cartografía, en donde grupos de pixeles se agrupan porque son muy parecidos y por tanto se consideran similares.

En este tipo de grafo se debe definir una función que permita determinar la similaridad que existe entre los vértices, principalmente la distancia entre sus características. Una función muy usada para determinar la distancia es:

S(P_X – P_Y) = |P _x,i – P _{y, i}| = | P _x,i – P _{y, i}| +

+| P _x,2 – P _{y, 2}| + ……… + | P _x,n – P _{y, m}|

En donde P _{x, n} es la propiedad n del punto P _x y P _{y, m} es la propiedad m del punto P _y. con la función anterior es posible determinar la distancia que existe en las propiedades de los vértices x, y. un valor grande S(P_X – P_Y) indica que no existe similaridad entre los vértices x, y mientras que un valor pequeño significa que son muy parecidos o similares.

Pero además de la función anterior, es necesario un valor referencial para discriminar la información que en este caso se llamara coeficiente de inferencia C. el valor de C se puede seleccionar de acuerdo con las experiencias que se tenga en el campo, o bien por medio de una prueba piloto. Si C es grande, la similaridad es poco exacta, sin embargo para un valor de C pequeño la similaridad es muy fuerte.

Una vez que se tiene S(P_X – P_Y) para todos los puntos (vértices) en cuestión se forman los grafos similares por medio del siguiente criterio: si S(P_X – P_Y)  ≤ C, se traza una arista de los vértices P_X  y  P_Y y se dice que P_X  y  P_Y son similares. Los grafos similares forman un subgrafo y los no similares otro distinto.

Determinación de la ruta más corta mediante grafos ponderados.

En un grafo ponderado a las aristas se le asigna un valor que se les llama ponderación  y que podría representar la distancia que hay de un nodo a otro, o bien el costo de transportarse de una ciudad a otra.

Determinar la ruta mas corta es un típico de la teoría de grafos, y consiste en determinar el camino mas corto para ir de una ciudad origen w a una ciudad de destino x. pueden existir varias rutas para ir de un nodo a otro,  pero el objetivo es encontrar la mas corta o bien la mas económica, si es que la ponderación representa un costo.

El método mas utilizado para encontrar la ruta mas corta de un nodo cualquiera W a cualquier nodo de la red es por medio del algoritmo Dijkstra el cual consta de los siguientes pasos:

1.      Seleccionar la ciudad la ciudad origen a.

2.      Usar una matris que tenga como columnas el numero de iteración, una columna para cada nodo(a, b,c,d),la columna actual que se utilizara para indicar el vértice que se seleccione en cada iteración y columna seleccionados para registrar los vértices que se van seleccionando en el proceso

iteracion	a	b	c	d	…	actual	seleccionados

3.       

Colocar en la matriz la distancia que existe en la ciudad origen a ella misma (cuando se trara de encontrar la distancia de una ciudad a ella misma considerar que es cero). A todas de mas se le coloca infinito como distancia.

iteracion	a	b	c	d	…	actual	seleccionados
0	0	∞	∞	∞

4.       

Colocar en la columna actual el vértice que tenga la distancia mas corta de entre todos los nodos (es obvio que en esta primera iteración en el nodo origen). En la columna seleccionados registrar dicho nodo escogido para ya no volver a elegir. (en nuestro caso registramos esta distancio de tipo bold, negro y subrrayado).

iteracion	a	b	c	d	…	actual	Seleccionados
0	0	∞	∞	∞	…	a	a

5.    

  Registrar en la columna de cada uno de los nodos la distancia mas corta que resulta de sumar la distancia registrada en el nodo actual + distancia de los vértices adyacentes a el,y seleccionar la distancia mas corta cuyo nodo aun no este seleccionado de esa fila de la matriz (suponer que d1>d2), Por la tanto la matriz será.

iteracion	a	b	c	d	…	actual	Seleccionado
0	0	∞	∞	∞	…	a	a
1	0	D1	D2	∞	…

 Si el nodo seleccionado tiene una distancia diferente de infinito, que es menor o igual a la que se obtiene de sumar la dstancia registrada en la columna actual + la distancia de ese nodo actual a los nodos abyacente a el, dejarla tal como esta, en caso contrario cambiarlo por la nueva suma. Seleccionados dicho nodo para ya no volver a elegir.

6.      Registrar en la columna actual el vértice que tenga la distancia mas corta de entre todos los nodos y que no haya sido seleccionada hasta ahora. Además de anotar en la columna.

iteracion	a	b	c	d	…	actual	Seleccionado
0	0	∞	∞	∞	…	a	a
1	0	D1	D2	∞	…		a,c

7.       

Si ya están todos los vértices seleccionados, finalizar . En caso contrario regresar al paso 5.

Muchas de las aplicaciones de grafos se pueden representar por medio de grafos ponderados, por lo general siempre se desean optimizar los recursos reduciendo las distancias de tal manera que al encontrar la ruta mas corta se disminuye el costo, tiempo y por supuesto distancia.

APLICACIÓN DE LOS ARBOLES

La estructura de árbol, independientemente si se trata de arboles binarios, AVL o B se usa principalmente para guardar la información organizada de tal manera que sea posible tener un rápido acceso a ella. La diferencia principal que permite decidir qué tipo de árbol usar depende de la forma en que está estructurada la información,  pero sobre todo el volumen de la misma (si la información es poca, entonces hay que utilizar arboles binarios o AVL dependiendo de la forma en que está organizada: si el volumen de información es grande entonces hay que usar arboles B).

Ya que cuando es posible manipular la información en memoria principal, los arboles binarios AVL son recomendables. Sin embargo, cuando no se puede transferir la información completamente de memoria secundaria a memoria principal después de procesarla se regresa al dispositivo de almacenamiento secundario, entonces es recomendable la utilización de arboles B y B++.

aqui un video para entenderlo mejor: