redes






Ing. En Sistemas Computacionales













Semestre: 1° “G”







 Definición: Una Red de Transporte es una gráfica dirigida, simple, con pesos y que debe cumplir las siguientes:

· Poseer una fuente o vértice fijo que no tiene aristas de entrada.
· Poseer un sumidero o vértice fijo que no tiene arista de salida
· El peso Cij de la arista dirigida de i aj llamado capacidad de “ij” es un número no negativo.

Una red de transporte es una gráfica 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 número nonegativo.




          En una red G, el flujo máximo es un flujo máximo. Generalmente existen varios flujos con el mismo valor máximo. Para encontrar el flujo máximo consideraremos un flujo inicial en cada arista igual a cero, después se determina un camino específico de la fuente al sumidero y se incrementa el flujo.

Si una arista está dirigida hacia la fuente decimos que esta arista estádirigida en forma impropia, en caso contrario está dirigida en forma propia.

Si se determina un camino P de la fuente al sumidero en donde cada arista de P está orientada en forma propia y el flujo en cada arista es menor que la capacidad de la arista, es posible aumentar el valor de flujo.

Es posible incrementar el flujo en ciertos caminos de la fuente al sumidero que tenga aristas orientadasen forma impropia y propia. Sea P un camino de “a” a “z” y sea “x” un vértice en P que no sea “a” ni ”z”.
Ambas aristas están orientadas en forma propia, en este caso, si incrementamos el flujo en ", el flujo en la entrada en x seguirá siendo igual al flujo de salida de x.
Si incrementamos el flujo en e2 en ", debemos disminuir el flujo en e1 en " de modo que el flujo de entrada en x siga siendoigual al flujo de salida en x.
Es análogo en el caso b
Disminuimos el flujo en ambas aristas en”. En cada caso las asignaciones resultantes de las aristas dan como resultado un flujo.
Para realizar estas alteraciones debemos tener un flujo menor que la capacidad en una arista orientada en forma propia y un flujo distinto de cero en una arista orientada en forma impropia. Matching (Pareo)
Dado un grafo, un pareo es un subconjunto de aristas los cuales no tiene vértices en común.








G = {V, E}
Ej. de pareo: AB DF EG HI LM
Pareo maximal
Un pareo maximal es un pareo que contiene el máximo número de aristas posibles, minimizando así el número de vértices sin unir. En el mejor de los casos, el pareo maximal contendrá a lo sumo V/2 aristas.

En elej. anterior, el pareo maximal podría ser: AB DF EG HI LM JK
Grafo bipartido
Se dice que G = {V, E} es un grafo bipartido si se cumple que:
1) V = V1  V2 y V1 V2 = ;
2)  e  E, e = (v1, v2) donde v1  V1 y v2  V2







Pareo maximal: A J2 B J5 C J3
Pareos en Grafos Bipartidos
Sea un grafo dirigido, bipartido con conjuntos disjuntos de vértices V y W, en el cual los ladosestán dirigidos desde los vértices de V a los vértices de W. (Cualquier vértice de G está en V o en W, pero no en ambos.) Un pareo para G es un conjunto de lados E los cuales no tienen vértices comunes. Un pareo maximal para G es un pareo E que contiene el máximo número de lados. Un pareo completo para G es un pareo E que tiene la siguiente propiedad: si v  V, entonces (v, w)  E, para algún w  W.El problema de pareos en un grafo bipartido puede modelarse como un problema de redes de la sig. forma:

1) Se asigna capacidad 1 a todas las aristas.
2) Se agrega una fuente (F) y aristas con capacidad 1 que van entre la fuente F y todos los vértices de un mismo grupo.
3) Se agrega también un sumidero (S) y aristas con capacidad 1 que van entre S y todas los vértices del otro grupo....