| Autor |
Mensaje |
mvc
Nivel 3
Registrado: 01 Feb 2008
Mensajes: 24
|
|
Tengo dos dudas:
1. siempre para hallar el corte minimal tengo q poner en un grupo los vertices que fueron etiquetados en el ultimo paso y en el otro grupo los otros?
2. Se puede en un mismo paso dividir un floju en dos partes...es decir si a A le llega (6)...puedo pasarle a B (2) y a C (4)..o si o si lo tengo que hacer en dos pasos distintos??
|
|
|
|
|
|
| |
    |
|
RiaNo
Nivel 8
Edad: 40
Registrado: 19 Mar 2008
Mensajes: 586
Carrera: Electrónica
|
|
1) Si; y además ya que estás si llamás P al conjunto en el que te quedó la fuente, y llamás Q al conjunto en el que te quedó el sumidero, entonces ya que estás podés verificar que todo lo que sale de P y llega a Q está saturado, y si hay flechas que van de elementos de Q a elementos de P, tienen flujo cero.
2) No estoy seguro, pero para no pifiar te conviene agarrar y pegarle derecho por un solo camino desde la fuente hasta el sumidero, aumentando los flujos que puedas, pero siempre de uno en uno. O sea, en tu ejemplo: Si de A (siendo A la fuente) sale una flecha a B y otra a C, y además suponé que de C y de B salen flechas hacia sumidero S, entonces te conviene hacer A->B->S y terminás. Te fijás que podés aumentar, lo aumentás y volvés a arrancar. Si podés volver a hacer A->B->S-> lo volvés a hacer, todas las veces hasta que te quede imposible de llegar al sumidero por haber algo saturado en el medio. Entonces ahí recién agarrás por otro camino. No sé si se entiende, cualquier cosa chiflá y lo intento explicar de nuevo.
Espero te sirva, salud!
|
|
|
|
|
|
   |
|
|
renzoe
Nivel 4
Edad: 37
Registrado: 09 Sep 2005
Mensajes: 109
Ubicación: Saavedra
Carrera: Informática y Sistemas
|
|
Hola!
Yo los corte minimo lo encuentro siempre a hojo, pero por supuesto hay que cortar siempre por aristas que estan saturadas (respecto a lo que dijo riano, no se si es necesario que de Q a P el flujo sea 0, me parece que no).
2) segun el algortimo de flord-fluckreson, eso se hace en dos pasos distintos, en una iteracion, por lo que aprendi solo marcas UN camino desde la fuente hacia el sumidero.
saludos
|
|
|
|
|
|
  |
|
|
mvc
Nivel 3
Registrado: 01 Feb 2008
Mensajes: 24
|
|
| Muchas gracias por las rtas!! me han servido bastante. Otra consulta alguien me podria explicar cuando se usa y para que me sirve el etiquetado negativo, porque no lo uso nunca por no saber para q sirve..gracias!
|
|
|
|
|
|
| |
|
|
RiaNo
Nivel 8
Edad: 40
Registrado: 19 Mar 2008
Mensajes: 586
Carrera: Electrónica
|
|
| mvc escribió:
|
|
Muchas gracias por las rtas!! me han servido bastante. Otra consulta alguien me podria explicar cuando se usa y para que me sirve el etiquetado negativo, porque no lo uso nunca por no saber para q sirve..gracias!
|
No me acuerdo excatamente cómo era el algoritmo en ese caso, pero más tarde cuando llegue a mi casa miro los apuntes y te digo si querés. La onda es que el etiquetado negativo se usa cuando se da un caso como tenés vértices A, B,C,D acomodados de la siguiente forma:
A->B
B->C
D->B
Entonces, si querés usar Ford Fulckerson al llegar a B tenés dos opciones: Ir para C ó or para D. Si vas para C, no pasa nada, haces lo mismo de siempre. El tema está si vas para D, ya que por el sentido de la arista estarías yendo como "a contra mano" ( ), y ahí se arma quilombo y se usa el etiquetado negativo. Cuando refresque mi memoria vuelvo a postear. Si no, tratá de conseguirte el apunte de Lorusso en el que está explicado todo el tema de redes de transporte, los teoremas que toman en el coloquio y al final está bien explicado Ford-Fulckerson.
| renzoe escribió:
|
|
Yo los corte minimo lo encuentro siempre a hojo, pero por supuesto hay que cortar siempre por aristas que estan saturadas (respecto a lo que dijo riano, no se si es necesario que de Q a P el flujo sea 0, me parece que no).
|
En realidad los algoritmos están hechos para cuando los cortes mínimos no pueden ser buscados "a ojo"; por ejemplo en redes de transportes de diez mil vértices. Si bien en todos los ejemplos que se ven en clase pueden sacarse muy fácilmente a ojo, la idea es usar los algoritmos. Y, sí, siempre ocurre que todo las aristas que van de P a Q están saturadas, y las que van de Q a P tienen flujo cero (figura en el apunte de Lorusso que nombré más arriba).
Salutes!
|
|
|
|
|
|
| |
|
|
|
|
|
Ver tema siguiente
Ver tema anterior
Podés publicar nuevos temas en este foro
No podés responder a temas en este foro
No podés editar tus mensajes en este foro
No podés borrar tus mensajes en este foro
No podés votar en encuestas en este foro
No Podéspostear archivos en este foro
No Podés bajar archivos de este foro
|
Todas las horas son ART, ARST (GMT - 3, GMT - 2 Horas)
Protected by CBACK CrackerTracker365 Attacks blocked.
|
