Grafuri

Cap.I Retele de transport

I.1. Flux într-o retea de transport, definitii

Definitie

Se numeste „ retea de transport ” un graf finit fara bucla, în care fiearui arc u îi este asociat un numar c(u) 0 numit „ capacitatea arcului ” si în care :

1) exista un vârf X0 si numai unul, astfel încât “-1X0 = ¦ ; acest vârf se numeste „ intrarea în retea ” ;

2) exista un vârf Xn si numai unul, astfel încât “ X0 = ¦ ; acest vârf se numeste „ iesirea din retea ”.

Flux într-o retea de transport

Fie multimea arcelor incidente interior în Xi si aceea a arcelor incidente exterior în Xi ; se spune ca o functie în valori întregi ¦(u) definita pe este un „ flux ” pentru o retea de transport daca sunt satisfacute relatiile:

1) ¦(u) e 0, u

2) ( Xi X0 , Xi Xn )

3) ¦(u) d c(u), u

¦(u) poate fi asimilat cu o cantitate de materie care trece prin arcul u si deci care nu trebuie sa depaseasca capacitatea c(u) a acestui arc.

Se deduce astfel ca:

= ¦0

Numarul ¦0 reprezinta cantitatea de materie care iese din X0 spre retea si ajunge prin retea în Xn

I.2. Taieturi minime si flux maxim într-o retea de transport

Taietura

Fie A o multime de vârfuri ale retelei continând iesirea Xn si necontinând pe X0. Multimea a arcelor incidente spre interior în A este o taietura a retelei.

Exemplu

Fie: A = { Xn , X2 , X3 , X6 , X9 }

= { ( X8 , Xn ), ( X10 , Xn ), ( X0 , X2 ), ( X1 , X2 ), ( X5 , X2 ), ( X0 , X3 ),

( X5 , X9 ), ( X10 , X9 ) }

este taietura corespunzatoare lui A ; ea a fost materializata printr-o linie punctata în desenul de mai sus, care reprezinta graful. Traseul unei taieturi în desenul grafului este destinat numai pentru materializarea arcelor incidente spre interior întâlnite si poate forma linii deschise sau închise neconexe ; totul depinde de alegerea lui A.

Întrucât A contine iesirea, orice unitate de materie care merge de la X0 la Xn parcurge cel putin odata un arc facând parte din ; deci, oricare ar fi fluxul ¦ si taietura este satisfacuta inegalitatea:

¦(Xn) d c( )

Daca exista un flux ¦0(Xn) si o taietura V astfel încât :

¦0(Xn) d c(V),

fluxul ¦0(Xn) are deci o valoare maxima, iar taietura V o capacitate minima ; de unde teorema de mai jos.

Teorema Ford – Fulkenson ( taietura minima, flux maxim )

Într-o retea de transport data, valoarea maxima a unui flux este egala cu capacitatea minima a unei taieturi.

MAX ¦0 = c( ).

Algoritmul Ford – Fulkenson

Acest algoritm permite obtinerea maximului unui flux printr-o retea ; enuntarea lui va fi ilustrata pe masura ce se dau explicatiile, prin exemplul din figura de mai jos, în care cantitatiile indicatelânga sagetile arcelor reprezinta capacitatile. În acest exemplu, intrarea va fi vârful 0, iar iesirea 11.