click below
click below
Normal Size Small Size show me how
DEFINICION
Redes
| Term | Definition |
|---|---|
| Red | Una red N con una fuente simple y un sumidero simple es un digrafo conexo con dos vertices distinguidos, uno llamado fuente tal que su grado de salida sea distinto de 0 y otro llamado sumidero tal que su grado de entrada sea distinto de 0. |
| Red con capacidad | Es una red tal que cada arco tiene asignado una capacidad no negativa cap(e) llamada capacidad de arco. |
| Flujo | Sea N una red f-s con capacidad, un posible flujo en N es una funcion que va desde las aristas de N hastalos reales positivos, asigna un numero real positivo f(e) a cada arco tal que: - Restri de capacidad: f(e) < cap(e) - Restri de conservacion |
| Capacidad de un corte | La capacidad de un corte < V f, V s > denotada cap < V f, V s > es la suma de las capacidades de los arcos en el corte < V f, V s >. |