Redes de flujo Flashcards
1
Q
¿Cómo puede representarse una red de flujo?
A
Como un grafo dirigido donde:
* Los ejes transportan algún tipo de flujo
* Los vértices actúan como conmutador de tráfico entre los diferentes ejes
2
Q
Definición de Capacidad
A
Cantidad máxima que un eje puede transportar
3
Q
Definición de Fuente
A
Vértice que genera tráfico saliente
4
Q
Definición de Sumidero
A
Vértice que absorbe tráfico entrante
5
Q
Definición de Flujo
A
Cantidad transportada por un eje
6
Q
¿Qué es el corte del grafo?
A
Dividir los nodos del grafp en dos sets (A y B), donde A incluye a la fuente y B al sumidero.
Condiciones:
* Cualquier flujo s-t debe cruzar en algún punto de A a B
* Ese corde define un límite al caudal máximo del flujo
7
Q
A
