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:
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.
aqui un video para entenderlo mejor:
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(PX – PY) = |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(PX – PY) 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(PX – PY) para todos los puntos (vértices) en cuestión se forman los grafos similares por medio del siguiente criterio: si S(PX – PY) ≤ C, se traza una arista de los vértices PX y PY y se dice que PX y PY 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:
No hay comentarios:
Publicar un comentario