Practica-Ford-Fulkerson PDF

Preview

Summary

Va muy bien este pdf para entender de forma rápida este algoritmo, también sale como hacerlo con el programa informático WinQSB, que te da la solución :)...

Description



Método MétodoFord Ford‐ ‐ ‐Fulkerson Fulkerson



Ejercicios Ejerciciosresueltos resueltoscon conWinqsb

 Portal Portal PortalEstadísticaAplicad Aplicada: a: a:Métod Métod Método oFord Ford‐ ‐ ‐Fulkerso Fulkerso Fulkerson n 1 1

FLUJO FLUJOMÁXI MÁXIMO MO MOEN ENREDES En Enteoría teoríade degrafos, grafos,un ungrafo grafodirigido dirigidocon conpesos pesoses estam también bién biénconocido conocidocom como ouna unared. Se Sedete determina rmina rminael elFlujo FlujoMáxi Máximo moporquehayinnumerablescuestiones cuestionesprá prácctic ticas as asdonde dondelo lomás másim importante portante es esconocer conocerla lacantidad cantidadde deflujo flujoquepasaatravésde deuna unared. El Elproblema problemadel delFlujo FlujoMáximo Máximoconsis consiste: te: te:Dado Dado Dadoun ungrafo grafodirigido dirigidocon conpesos, pesos,G G=(V, (V,A,W), A,W),qu qu que erepresenta otro odefinTen enV,se setr traatade deencontrar las lascapacidades capacidadesmáximas máximasdelos loscanales, canales,unnodo nodode deinicio inicioS yotr la lacantidad cantidadmáxima máximade deflujo flujoque quepuedecirculardesdeS hasta hastaT. Las Lasaris aristas tas tasreprese representan ntan ntancanales canalespor porlo lossque quepuede puedecircular circularcierta ciertacosa: cosa:tr transmisión ansmisión ansmisiónde dedatos, datos,rede redessde corriente corrienteeléctrica, eléctrica,líneas líneasde deoleoductos, oleoductos,agua agua agua,,auto automóviles, móviles, móviles,etc. Los Lospesos pesosde delas lasari arista sta stassrepresen representan tanlacapacidadmáximadeuncanal:velocida velocidad dde deuna unaconexión, cantidadmáxima máximade detráfico, tráfico,voltajede deuna unalínea líneaeléc eléctrica, trica, trica,volumen volumenmáximo máximode deagua, agua,etc. Los Losproblem problemas as asde deFlujo FlujoMáximo Máximose sepueden puedenresolver resolvermediante medianteprogra programas mas masinformáticos, informáticos,por porejemplo, ejemplo,el programa programaWinQSB WinQSBcon conun unconjunto conjuntode deherram herramientas ientas ientasútilesparala lainvestigaciónde deoperaciones. operaciones.Dentro Dentro de deWinQSB WinQSBse seencuentr encuentraael elmodulo moduloNet Networ wor workkModeling Modeling(Ma (Maxi xi xima ma mallFlow FlowProbl Proble em), m),que quepermiteresol resolver ver problemas problemasde deFlujo FlujoMáximo Máximocon confaci facilidad. lidad. CONCEPTOS CONCEPTOSBÁSICO BÁSICOS: S: 

Flujo: Flujo:Circulación Circulación Circulaciónde deunida unidades des deshomogéneas homogéneasdeunluga lugarraotro.



Capacidad Capacidadde deflujo flujo::Capacidad Capacidad Capacidaddeunidades unidadesquepueden puedenentrar entrarpor porel elnodo nodofuente fuenteysalir salirpor porel nodo nododestino.



Orig Origen en enofuente fuentede deflujo: flujo:Nodo Nodoporelqueingresaelflujo.



Destino DestinooSumidero Sumiderodeflujo: flujo:Nodo Nodo Nodopor porquesale saleel elflujo.



Capacidades Capacidadesresiduales: residuales:Capacidades Capacidades Capacidadesresta restantes ntes ntesuna unavez vezque queel elflujo flujopasa pasael elarco.

MÉTODO MÉTODODE DEFORD FORD‐‐FULKERSON: FULKERSON:FL FLUJ UJ UJO OMÁXIMO MÁXIMOEN ENREDES El Elmétodo métodopr propone opone oponebuscar buscarcaminos caminosen enlos losquese sepuedaaumentar aumentarel elflujo flujohasta hastaque quese sealcanceelflujo máximo, máximo,la laidea ideaes esencontr encontrar aruna unaruta rutadepenetración penetracióncon conun unflujopositivoneto netoqueunalos losnodos nodosde origen origenydestino. 

El Elflujo flujoes essiempre siemprepositivoyconunidadesenteras.



El Elflujo flujoatravés travésde deun unarco arcoes esmen menor or oroigual igualque quela laca capacidad. pacidad.



El Elflujo flujoqueentra entraen enunnodo nodoes esigual igualal alquesale salede deél.

 Portal Portal PortalEstadísticaAplicad Aplicada: a: a:Métod Métod Método oFord Ford‐ ‐ ‐Fulkerso Fulkerso Fulkerson n 2 2

PASOS PASOSPARA PARALA LARE RESOLUCIÓN SOLUCIÓN SOLUCIÓNDE DEUN UNPROBLEM PROBLEMA ADE DEFLUJO FLUJOMÁXI MÁXIMO MO 1. Identifica Identificarrel elnodo nodoorigen origenyde dedestino. 2. Partiendo Partiendodel delnodo nodode deorigen origense seelige eligeel elarco arcoque queposeamayor mayorflujo 3. Identifica Identificarrlos losnodos nodosde detransbordo. 4. Repetir Repetirel elproces proceso ocomosi sielno nodo do dointerm intermediario ediario ediariofu fuera era erael elnodo nodoorigen. 5. Calcular Calcular'k' 'k'ylas lasnuevas nuevascapacida capacidades. des. 6. Obten Obtenido ido idoel elresultado resultadose secambia cambian nlas lascapacida capacidades des desyse serepiteidéntico idénticopr proc oc ocedim edim edimiento iento ientodesde desdeel elinicio.

Ci jj,, j i

Capacidad   ⎧ C ≡ Capacidad ⎪ i j ≡ Índices Índicesde delos losnodos nodos   ⎪ = ((C Ci − k , C j + k ) ⎨ Míínimoflujoquepasapor porelnodo ⎪k ≡ M ⎪⎩ k = mín mín(( capac capacidades idades idadesdelaruta) ruta) 

El ElFlujo FlujoMáxi Máximo mo moque quepuede puedepasar pasardel delnodo nodoorigen origenhastaelnododestinoeslasuma sumade delas lascapacidades ∑ k delaruta.

Calcular Calcularel elflujo flujomáximo máximodel delgraf grafo: o:

MÉTODO MÉTODODE DEFORD FORD‐‐FULKERSON: FULKERSON:  Flujo Flujo Flujomáximo máximodesde desdes, s,rem remplazan plazan plazando do donuevas nuevascapacida capacidades des

k = mín mín((∞ , 30 , 20) = 20 C13 , 31 = (30 − 20 , 0 + 20) = (10 , 20) C35 , 53 = (20 − 20 , 0 + 20) = (0 , 20)

 Portal Portal PortalEstadísticaAplicad Aplicada: a: a:Métod Métod Método oFord Ford‐ ‐ ‐Fulkerso Fulkerso Fulkerson n 3 3

Ruta: Ruta:  1 1‐2‐ ‐3 3‐ ‐4 4‐ ‐5 5 //Rem Rem Remplazando plazando plazandonuevas nuevascapacidades

k = mín mín((∞ , 20 , 40 , 10 , 20) = 10 C12 , 21 = (20 − 10 , 0 + 10) = (10 , 10) C23 , 32 = ( 40 − 10 , 0 + 10) = (30 , 10) C34 , 43 = (10 − 10 , 5+ 10) = (0 , 15 15)) C45 , 54 = (20 − 10 , 0 + 10) = (10 , 10)

Ruta: Ruta:  1 1‐2‐ ‐5 5/Remplazand Remplazando onuevascapacidades

k = mín mín((∞ ,10 , 20) = 10 C12 , 21 = (10 − 10 , 10 + 10) = (0 , 20) C25 , 52 = (20 − 10 , 0 + 10) = (10 , 10)

 Portal Portal PortalEstadísticaAplicad Aplicada: a: a:Métod Métod Método oFord Ford‐ ‐ ‐Fulkerso Fulkerso Fulkerson n 4 4

Ruta: Ruta:  1 1‐3‐ ‐2 2‐ ‐5 5/Rem Remplazando plazando plazandonuevas nuevasca capacidades pacidades

k = mín mín((∞ , 10 , 10 , 10) = 10 C13 , 31 = (10 − 10 , 20 + 10) = (0 , 30) C32 , 23 = (10 − 10 , 30 + 10) = (0 , 40) C25 , 52 = (10 − 10 , 10 + 10) = (0 , 20)

Finalmente, Finalmente,Ruta Ruta Ruta:: 1 1‐4‐5/Remplaz Remplazando ando andonuevascapacidades

k = mín mín((∞ ,10 ,10) = 10 C14 , 41 = (10 − 10 , 0 + 10) = (0 , 10) C45 , 54 = (10 − 10 , 10 + 10) = (0 , 20) El ElFlujo Flujomáxi máximo mo mose seobtiene obtieneal alsumar sumartodas todaslasnuevascapacidades:

∑ k = 20 + 1100 + 1100 + 1100 + 1100 = 60

 Portal Portal PortalEstadísticaAplicad Aplicada: a: a:Métod Métod Método oFord Ford‐ ‐ ‐Fulkerso Fulkerso Fulkerson n 5 5

Network ng/Maximal Probl NetworkMod Model el eliing MaximalFlow FlowProbl blem em Muchos Muchosproblemas problemaspueden puedenser sermo mode de dela la lado do dossmedi mediante ante anteuna unared reden endonde ondelos losarcos arcoslimita limitan nla lacantidad de deun unproducto productoque quese sepuedeenviar enviar..Enestassituaciones,frecuentemente frecuentementesetran transporta sporta sportala lamáxima cantidad cantidadde deflujo flujodesdeun unpuntodepartida partidallamado llamadofuentehaciaunpuntofinalde denominado nominado nominadopozo.

 Portal Portal PortalEstadísticaAplicad Aplicada: a: a:Métod Métod Método oFord Ford‐ ‐ ‐Fulkerso Fulkerso Fulkerson n 6 6

 Portal Portal PortalEstadísticaAplicad Aplicada: a: a:Métod Métod Método oFord Ford‐ ‐ ‐Fulkerso Fulkerso Fulkerson n 7 7

RESOLUCIÓN RESOLUCIÓNALGORITMO ALGORITMODE DEFORD FORD‐ ‐ ‐FUL FULKE KE KERSO RSO RSON N

La Lared redesta estaform formada ada adapor por5no nodos, dos, dos,7 7aris aristas tas tasyuna unafunción funcióncapacidad. capacidad.Se Secomienza comienzaponiendo poniendotodos todoslos flujos flujosa0.

Caminode deaumento: aumento:Caminosin sinnodos nodosque queunescont Cuello Cuellode debotella: botella:Mín Mín Mínimo imo imodelas lascapacidades capacidadesresiduales residualesdeuncamino caminodeaument aumento. o. Se Sebusca buscauncamino caminodeaume aumento: nto: nto:ss‐2‐t

 Portal Portal PortalEstadísticaAplicad Aplicada: a: a:Métod Métod Método oFord Ford‐ ‐ ‐Fulkerso Fulkerso Fulkerson n 8 8

Seactualiza actualizalared redresidual

Se Sebusca buscaotro otrocamino caminode deaumento: aumento:ss‐4‐3‐t

 Portal Portal PortalEstadísticaAplicad Aplicada: a: a:Métod Métod Método oFord Ford‐ ‐ ‐Fulkerso Fulkerso Fulkerson n 9 9

Seactualiza actualizalared redresidual.

Se Sebusca buscaotro otrocamino caminode deaumento: aumento:ss‐4‐t

Seactualiza actualizalared redresidual.

El Elalgoritmo algoritmode deFord Ford‐ ‐ ‐Fulkerson Fulkerson Fulkersonfinaliza finalizaporque porqueya yano nose sepueden puedenencont encontrar rarmá másscaminosen aumento. aumento.El Elflujo flujomáximo máximoes es ∑ f( f(aarista) = 9 + 9 = 18

 Portal Portal PortalEstadísticaAplicad Aplicada: a: a:Métod Métod Método oFord Ford‐ ‐ ‐Fulkerso Fulkerso Fulkerson n 10 10

Network NetworkMod Model el eliing ng/Maximal MaximalFlow FlowPro Probl bl blem em

 Portal Portal PortalEstadísticaAplicad Aplicada: a: a:Métod Métod Método oFord Ford‐ ‐ ‐Fulkerso Fulkerso Fulkerson n 11 11

ElFlujomáxi deshas es18. El máximo mo mode hasta tates

Network NetworkMod Model el eliing ng/Maximal MaximalFlow FlowPro Probl bl blem em

Obtener Obtenerel elmáximo máximoflujoque quesepuede llevar llevardelnodo nodo0alno nodo do doT

 Portal Portal PortalEstadísticaAplicad Aplicada: a: a:Métod Métod Método oFord Ford‐ ‐ ‐Fulkerso Fulkerso Fulkerson n 12 12

El ElFlujo Flujomáxi máximo mo mode de0hasta hastaTes es14.

 Portal Portal PortalEstadísticaAplicad Aplicada: a: a:Métod Métod Método oFord Ford‐ ‐ ‐Fulkerso Fulkerso Fulkerson n 13 13

 Portal Portal PortalEstadísticaAplicad Aplicada: a: a:Métod Métod Método oFord Ford‐ ‐ ‐Fulkerso Fulkerso Fulkerson n 14 14...