Edición de «Práctica 11: Matching - Flujo Máximo (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 24: | Línea 24: | ||
***In(v)={e en EN, e=w->v con w otro vertice de N} | ***In(v)={e en EN, e=w->v con w otro vertice de N} | ||
***Out(v)={e en EN, e=v->w con w otro vertice de N} | ***Out(v)={e en EN, e=v->w con w otro vertice de N} | ||
*(DEF) Un '''corte''' en la red N es un subconjunto S(V | *(DEF) Un '''corte''' en la red N es un subconjunto S(V tq s en S y t no en S | ||
*(DEF) SS'={ejes que tienen la cola en S y la cabeza en S'} y S'S={ejes que tienen la cola en S' y la cabeza en S} donde S'=V\S | *(DEF) SS'={ejes que tienen la cola en S y la cabeza en S'} y S'S={ejes que tienen la cola en S' y la cabeza en S} donde S'=V\S | ||
* (TEO) Sea f un flujo definido en una red N y sea S un corte -> F= Σ{e en SS'} f(e)-Σ{e en S'S} f(e) | * (TEO) Sea f un flujo definido en una red N y sea S un corte -> F= Σ{e en SS'} f(e)-Σ{e en S'S} f(e) |