Ret de fluix

Archiu:Simpe flow network.svg

Ret de fluix

En teoria de grafos, una ret de fluix és un grafo dirigit a on existixen dos vèrtiços especials, un de cridat font, al que se li associa un fluix positiu i un atre cridat sumidero que té un fluix negatiu i a cada aresta se li associa certa capacitat positiva. En cada vèrtiç diferent als dos especials es manté la llei de corrents de Kirchoff, en a on la suma de fluix entrantes a un vèrtiç deu ser igual a la suma de fluix que ixen d'ell (propietat de conservació del fluix $\sum f_i=\sum f_o$). Pot ser utilisada per a modelar el tràfic en un sistema d'autopistes, decorreguts viajant en canonades, corrents elèctriques en circuits elèctrics o sistemes similars per lo que viage alguna cosa entre nodos. Un dels usos principals dels cridats algoritmes de fluix és trobar el fluix màxim de la font al sumidero, sempre complint unes determinades restriccions.

Descripció matemàtica

Una ret de fluix és un grafo dirigit $G=(V,E)$ en a on cada arc $(u,v)\in E$ té una capacitat no negativa $c(u,v)\ge 0$.

Es distinguixen dos vèrtiços: la font s i el destí t.

Se supon que cada vèrtiç es troba en alguna ruta de s a t.

Un fluix en G és una funció

$f:V\times V\mapsto R$

tal que

Archiu:Red de flujo.jpg

Eixemple de Ret de fluix

• Restricció de capacitat: $\mathrm{\forall }u,v\in V,f(u,v)\le c(u,v)$
• Simetria: $f(u,v)=-f(v,u)$
• Conservació: $\mathrm{\forall }u\in V-\{s,t\}\sum _{v\in V}f(u,v)=0$

El valor del fluix és $|f|=\sum _{v\in V}f(s,v)$

El problema del fluix màxim tracta d'maximizar este fluix.

Algoritme de fluix màxim

Tenim el conegut problema de fluix màxim o maximal: ¿quin és la taxa major a la qual el material pot ser transportat de la font al sumidero sense violar cap restricció de capacitat?

En atres paraules, el problema consistix en determinar la màxima capacitat de fluix que pot ingressar a través de la font i eixir pel nodo de destí.

El procediment per a obtindre el fluix màxim d'una ret, consistix en seleccionar repetides voltes qualsevol trayectòria de la font al destí i assignar el fluix màxim possible en eixa trayectòria.

Capacitat residual: és la capacitat adicional de fluix que un arc pot dur:

$c_f(u,v)=c(u,v)-f(u,v)$

• Donada una ret de fluix màxim, plantege la ret residual associada.

• Trobe la trayectòria de la font al destí en capacitat de fluix estrictament positiu (si no existix algun, és perque s'ha trobat l'òptim).

• Examine estes trayectòrias per a trobar la branca o arc en la menor capacitat de fluix restant i incremente en este valor, la capacitat del fluix en sentit contrari.

• Determine totes les trayectòries estrictament positives, fins que no es permeta fluix del nodo a un nodo destine.

Podem, per mig del Algoritme de Ford-Fulkerson, trobar el fluix màxim d'una ret.

Este algoritme és un método iterativo, el qual, escomença en un fluix nul i en cada iteración es va obtenint un valor del fluix que va aumentant el camí, fins que no es puga aumentar més. Depén de tres punts vitals:

• Ret residual: camí de la font al sumidero, a on cada una de les arestes té un fluix residual major que zero. Sent el fluix residual, el fluix que es pot obtindre en una aresta una volta que haja passat un fluix per ella.
• Aument de camí: es basa en anar aumentant el camí, fins a alcançar el màxim (capacitat residual, definit anteriorment).
• Cort en rets de fluix: consistix simplement en realisar una partició del conjunt de vèrtiços en dos subconjunts.

Restriccions

Les restriccions de capacitat mencionades són les següents: Els valors de fluix existents en cada aresta no poden sobrepassar els valors màxims. La suma de les entrades de cada nodo interior té que ser igual a la suma de les seues eixides.

Característiques principals

El fluix va a ser sempre positiu i en unitats sanceres. El fluix que entra en un nodo és igual al que ix.

El fluix que travessa un arc mai serà major que la capacitat, solament pot ser menor o igual que ella.

Bibliografia

• Algoritme de Ford-Fulkerson
• Rets de Fluix