Flujos y cortes

Flujos Y Cortes en Redes.

Elena Jaramillo

Teoría de Grafos.

Edisson Camilo Martínez Giraldo
Fundación Universitaria María Cano.
Ingeniería de Sistemas
2011-04-26
Tesis
La tesispropuesta por el autor es:
Comprender la aplicación de los grafos dirigidos en la cotidianidad, así mismo su definición, ya que por medio de estos tipos de grafos se calcula el flujo en un elemento aanalizar.
Desarrollo argumentativo
Para dar inicio a esta relatoría cabe resaltar los siguientes conceptos anteriormente revisados en las sesiones, ya que serán muy utilizados en el desarrollo de estarelatoría:
* Grafo dirigido: Un grafo es un conjunto de puntos (vértices) en el espacio, que están conectados por un conjunto de líneas (aristas). En donde este conjunto de aristas tienen unadirección, es decir, para llegar desde un vértice x a un vértice y, se debe tener en cuenta que el camino o arista que comunica estos vértices sea el correcto, un claro ejemplo de este son las calles,carreteras las cuales tienen dirección si es de izquierda a derecha o en sentido contrario.
* Grafo ponderado: este tipo de grafos es similar al anterior, su diferencia radica en que cada arista estaetiquetada y en esa etiqueta tiene un valor, la cual representa el peso que tiene esta.
* Camino: es el conjunto de aristas que llevan desde un vértice inicial a un vértice final.
Es necesarioaclarar que el texto reemplaza la palabra grafo por redes de flujo.
Así de esta manera ya teniendo en claro los anteriores conceptos podemos entrar a analizar el flujo, corte, caminos aumentantes,capacidad y grafos residuales en las redes de flujo:
Como primera instancia para definir estos anteriores conceptos, el grafo debe tener un vértice inicial (fuente) que no tiene ninguna incidencia, es decir,este no tiene ninguna arista que apunte a él, pero de este se desprende una serie de aristas y un vértice final (sumidero), en donde en este inciden una cantidad determinada de aristas, pero de...