Probleme de drum in (di)grafuri

Parcurgeri sistematice ale (di)grafurilor.

Dat G = (V, E) un (di)graf cu multimea varfurilor V = si s I V, se cere sa se genereze "eficient" multimea S a varfurilor accesibile din s pe drumuri in G.

Solutia pe care o vom da va impune un proces de "vizitare" succesiva a vecinilor lui s in G, apoi a vecinilor (inca nevizitati) ai acestora, s.a.m.d., pana se va construi multimea S.

Algoritmul va implementa o metoda sistematica de "vizitare", utila in probleme de optimizare pe grafuri, dar mai ales in problemele in care grafurile sunt folosite ca structuri (explicite sau implicite) de date.

Vom presupune ca (di)graful G este dat prin intermediul listelor de adiacenta (in cazul grafurilor se poate considera ca fiecare muchie genereaza o pereche de arce simetrice si reprezentarea folosita la sortarea topologica ramane valabila). In algoritm vom folosi doua multimi:

S = multimea varfurilor (deja) vizitate;

S astfel incat v I S - vw I E Þ w I S (complementara in S a lui contine varfuri ai caror vecini au fost deja vizitati).

Algoritmul se va termina atunci cand = Æ.

Initial, S = = . In pasul curent al algoritmului, se alege un varf din si se va "explora", considerand "urmatorul" vecin din lista sa de adiacenta (inca neexaminat). Daca lista sa de adiacenta a fost parcursa, atunci se poate "scoate" acest varf din . Daca exista acel urmator vecin si n-a fost inca vizitat, el se adauga la S si la . "Pozitia" urmatorului vecin neexaminat din lista de adiacenta a unui varf i se va gestiona cu ajutorul unui pointer p[i], care initial are valoarea cap[i] si va fi avansat in timpul parcurgerii listei vecinilor lui i.

Descriem aceasta "vizitare" a varfurilor (di)grafului in procedura nerecursiva exploraredin(s).

type pointer = ^arc;

arc = record

varf : 1 . . n;

prec : pointer;

end;

var cap, p : array[1 . . n] of pointer;

procedure exploraredin (s : 1 . . n);

begin

S := S È ;

:= ;

while ¹ Ø do

begin

alege v I

if p[v] = nil then

sterge v din

else

begin

w := p[v]^.varf;

p[v] := p[v]^.prec;

if w Ï S then

begin

adauga w la S;

adauga w la ;

end;

end;

end;

end;

Presupunand ca operatiile subliniate necesita timpul de O(1), atunci se observa ca aplicarea lui exploraredin(s) va necesita timpul O(n_s + e_s) unde, n_s = || si e_s = numarul arcelor (muchiilor) cu ambele extremitati in multimea finala S. Acest ordin de complexitate rezulta din faptul ca la fiecare iteratie a ciclului while, in timp constant, sau se adauga un nou varf la S (), sau se progreseaza in lista de adiacente a unui varf din .

Pentru ca operatiile subliniate sa se execute in O(1) va trebui ca S sa fie reprezentata cu ajutorul unui tablou boolean [S : array[1 . . n] of boolean; initializarea lui S (pe fals) inaintea apelului lui exploraredin, necesita O(n) operatii; testul if w Ï S este if not S(w), deci O(1); atribuirea S := S È este S(s) := true; (adauga w la S) este S(w) := true] iar ca o lista inlantuita:

Daca va fi o stiva cu top : pointer capul ei, atunci:

:= s new(top); top^.varf := s; top^.prec := nil.

¹ Ø top ¹ nil.

alege v I v := top^.varf (nu se modifica top)

sterge v din top := top^.prec

adauga w la new(l); l^.varf := w; l^.prec := top; top := l.

In acest caz , de fiecare data, va fi ales pentru explorare ultimul varf introdus in si parcurgerea se face "mai intai in adancime", depth first search (dfs).

Daca va fi o coada cu cap, spate : pointer inceputul si sfarsitul ei, atunci:

:= s; new(l); l^.varf := s; l^.prec := nil; cap := l; spate := l;

¹ Ø cap ¹ nil;

alege v I v := cap^.varf (nu se modifica nici cap nici spate).

sterge v din cap := cap^.prec; (if cap = nil then spate := nil)

adauga w la new(l); l^.varf := w; spate^.prec := l; spate := l; (l^.prec := nil)

In acest caz, de fiecare data, va fi ales spre explorare cel mai "vechi" varf introdus in si un varf va fi scos din abia dupa ce i se introduc toti vecinii neexplorati inca. Parcurgerea va fi deci "mai intai la latime" breadth first search (bfs).

Implementarea lui ca o stiva (deci dfs) se poate face explicit, asa cum am aratat mai sus, dar si implicit scriind o forma recursiva a lui exploraredin(s). Vom face acest lucru in aplicatia urmatoare, in care vom lista componentele conexe ale unui graf reprezentat cu ajutorul listelor de adiacenta in O(n + e), n = | V |, e = | E |.

var cap, p : array[1 . . n] of pointer;

i, nrcconexa : integer;

l, topc : pointer;

procedure dfs(v : 1 . . n);

var p1 : pointer;

w : 1 . . n;

begin

p1 := p[v];

while p1 ¹ nil do

begin

w := p1^.varf;

p1 := p1^.prec;

if not S[w] then

begin

new(l);

l^.varf := w;

l^.prec := topc;

topc := l;

S[w] := true;

dfs(w)

end;

end;

end;

begin

for i := 1 to n do S[i] := false;

for i := 1 to n do p[i] := cap[i];

nrcconexa := 0;

for i := 1 to n do

if not S[i] then

begin

nrcconexa := nrcconexa + 1;

S[i] := true;

new(topc);

topc^.varf := i;

topc^.prec := nil;

dfs(i);

writeln('componenta conexa ', nrcconexa);

while topc ¹ nil do

begin

write(topc^.varf);

topc := topc^.prec;

end;

end;

end.

Vom face in continuare, o analiza a comportarii logice a parcurgerii dfs a unui (di)graf, pentru a pune in evidenta modul de accesare a varfurilor, precum si o partitie a multimii muchiilor (arcelor), relevante in aplicatii (care necesita parcurgerea sistematica a (di)grafului in scopul calcularii recursive a unor functii definite pe multimea varfurilor sale, in ordinul O(n + m)).

In aceleasi ipoteze referitoare la tipurile de date si variabilele folosite mai sus, consideram modulul apelant:

begin

for v := 1 to n do

begin

p[v] := cap[v];

S[v] := false;

end;

nr1 := 0;

nr2 := 0;

for v := 1 to n do

if not S[v] then

begin

nr1 := nr1 + 1;

viz[v] := nr1;

S[v] := true;

dfs(v);

nr2 := nr2 + 1;

sfv[v] := nr2

end;

end.

si procedura dfs:

procedure dfs(v : V);

var p1 : pointer;

w : V;

begin

p1 := p[v];

while p1 ¹ nil do

begin

w := p1^.varf;

p1 := p1^.prec;

if not S[w] then

begin

;}

nr1 := nr1 + 1;

viz[w] := nr1;

S[w] := true;

dfs(w);

nr2 := nr2 + 1;

sfv[v] := nr2

end

else

begin

if viz[w] > viz[v] then }

else

if drum de la w la v in (V, T) then

}

else }

end

end;

end;

S-au utilizat nr1 si nr2 pentru construirea tablourilor viz si sfv, avand semnificatia:

viz[v] = numarul de ordine al intalnirii varfului v de catre procedura dfs (apelul dfs(v) este cel de-al viz[v]-lea, in traversare (di)grafului);

svf[v] = numarul de ordine al sfarsitului vizitarii varfului v de catre procedura dfs.

De asemenea, s-au construit submultimile T, B, F, C ale lui E (in operatiile subliniate) care au urmatoarele semnificatii, in ipoteza ca G este digraf:

T - multimea arcelor utilizate de procedura dfs pentru parcurgerea digrafului; se verifica imediat ca (V, T) este o reuniune de arborescente (arborescentele dfs).

F - multimea arcelor "forward", orientate de la o extremitate initiala vizitata inaintea extremitatii finale;

B - multimea arcelor "backward", orientate de la o extremitate initiala vizitata dupa extremitatea finala si extremitatea initiala se afla in subarborescenta dfs cu radacina in extremitatea finala; mai precis, vw I B Û vw I E, viz[v] > viz[w] si sfv[v] < sfv[w].

C - multimea arcelor "cruce", orientate de la o extremitate initiala, aflata intr-o arborescenta dfs construita dupa cea in care se afla extremitatea finala; mai precis, vw I C Û vw I E, viz[v] < viz[w] si sfv[v] > sfv[w].

Se observa ca B, F, sau C pot fi vide si ca E = T È B È F È C si toate aceste multimi sunt disjuncte. Daca G este graf, atunci B = F si C = Æ, interpretarile fiind evidente.

Vom exemplifica utilitatea parcurgerii sistematice a unui digraf, pentru a depista eficient componentele sale tari-conexe (modificari minore ale metodei pe care o vom descrie permit determinarea blocurilor (componentelor biconexe) ale unui graf).

Fie G = (V, E) un digraf. Consideram, pe multimea varfurilor sale, relatia binara: vrw Û exista drum de la v la w si drum de la w la v in digraful G. Se verifica imediat ca r este relatie de echivalenta. Clasele de echivalenta in raport cu relatia r se numesc componentele tari-conexe ale digrafului G (submultimi maximale (in raport cu incluziunea) de varfuri cu proprietatea ca induc subdigrafuri tari-conexe). In digraful desenat mai jos componentele tari conexe sunt: , , , .

Idea algoritmului este urmatoarea:

se efectueaza o parcurgere dfs a digrafului, construind tablourile viz si sfv.

Daca C este o componenta tare conexa a lui G, definim

.

Fie C₀ astfel incat f(C₀) = min_C f(C), deci C₀ este prima componenta tare conexa pentru care se termina complet vizitarea.

Daca f(C₀) = sfv[v₀], atunci, notand cu subarborescenta dfs cu radacina in v₀, avem C₀ = V(). In adevar, C₀ V(), intrucat in avem varfurile accesibile prin drumuri in G (si orice varf al lui C₀ are aceasta proprietate). Daca V() - C₀ ¹ Æ, se contrazice alegerea lui C₀, intrucat x I V() - C₀ satisface sfv[x] < sfv[v₀] (x este vizitat de un apel recursiv generat de dfs(v₀)).

Rezulta ca la terminarea vizitarii varfului v₀ s-a depistat C₀.

Recunoasterea varfului v₀ este simpla: v₀ este primul varf al digrafului cu proprietatea ca din nici unul din descendentii sai dfs nu exista arce de intoarcere (B) cu extremitatea finala w avand viz[w] < viz[v₀].

Pentru G - C₀ se repeta acelasi rationament.

Daca vom considera b[v] = cel mai mic viz[w] al unui arc uw I B cu u I T_v, daca exista un astfel de arc, altfel b[v] = viz[v], atunci se observa ca intreg planul de lucru descris mai sus se realizeaza la o singura traversare a digrafului , intrucat b[v] se pot calcula recursiv, iar considerarea subdigrafului G - C₀ inseamna simpla continuare a traversarii.

Detaliile sunt descrise mai jos ( modulul apelant si procedura dfs adaptata problemei):

begin

for v:=1 to n do

begin

p[v] = cap[v];

S[v] := false

end;

nr:=0;

L:= Æ;

for v:=1 to n do

if not S[v] then

begin

nr := nr+1;

viz[v] := nr;

S[v] :=true;

adauga v la L;

dfs(v);

end

end.

procedure dfs(v : V);

var p1 : pointer; w : V;

begin

p1 :=p[v];

b[v] := viz[v];

while p1 ¹ nil do

begin

w := p1 .virf;

p1 := p1 .prec;

if not S[w] then

begin

nr := nr +1;

viz[w]:= nr;

S[w] := true;

adauga w la L;

dfs(w);

if b[w]<b[v] then

b[v]:= b[w]

end

else

if w I L and b[v] > viz[w] then

b[v] :=viz[w]

end;

if b[v] = viz[v] then

extrage din L c.t.c. cu radacina v formata din varfurile w din L cu viz[w] ³ viz[v].

end.

Pentru realizarea eficienta a operatiilor subliniate, se va implementa L ca o pereche formata dintr-un tablou boolean (pentru testarea apartenentei in O(1)) si ca o lista dublu inlantuita (pentru extragerea eficienta a varfurilor unei componente tare conexe; notam ca la insertia in L, elementele vin in ordinea crescatoare a lui viz, iar extragerea se face de la celalalt capat). Se verifica imediat ca in acest fel intreg algoritmul are complexitatea O(|V| + |E|).

Probleme de drum minim.

Fie G = (V, E) un digraf cu multimea varfurilor V = . Consideram data o functie a : E R cu interpretarea : ij I E a(ij) = costul arcului ij (ponderea, lungimea, etc.). Daca digraful G este reprezentat cu ajutorul listelor de adiacenta, atunci costul arcului ij este un camp in articolul ce reprezinta acest arc in lista de adiacenta a lui i. Pentru comoditatea notatiilor vom folosi reprezentarea digrafului G cu ajutorul matricii de cost-adiacenta A = (a_ij)_{n n} cu

Notam ca ¥ desemneaza un numar real mare in raport cu celelalte costuri (de exemplu ¥ > n max_{ij I E} a(ij)) si vom presupune in plus ca ¥ a = ¥, ¥ + ¥ = ¥.

(Este posibil, de asemenea , ca ¥ sa semnifice acces terminat cu insucces in structura de date in care se reprezinta matricea A).

Daca i, j IV, vom nota cu D_ij = . Pentru D_ij I D _ij

D_ij : (i =)v₀ ,v₀v₁, v₁, ., v_r-1, v_r-1v_r, v_r(= j )

multimea varfurilor este V(D_ij) =

si multimea arcelor E(D_ij) = .

Orice varf k ¹ i, j al lui D_ij, determina pe D_ij doua drumuri D_ik I D_ik si D_kj I D_kj. Vom nota D_ij = D_ik o D_kj.

Costul unui drum D_ij I D _ij se defineste

In particular, a(D_ii) = 0. Principalele probleme de drum (de cost) minim care apar in aplicatii practice (sau sunt utile in rezolvarea altor probleme de optimizare combinatorie) sunt:

(P1) Date: G digraf, a : E(G) R, s, t I V(G) s ¹ t.

Sa se determine D^*_st I D_st astfel incat

a(D^*_st) = min

(P2) Date: G digraf, a : E(G) R, s I V(G).

Sa se determine D^*_si I D_si i I V(G), astfel incat

a(D^*_st) = min i I V(G)

(P3) Date: G digraf, a : E(G) R.

Sa se determine D^*_ij I D_ij i, j IV(G), astfel incat

a(D^*_ij) = min.

Observatii: 1. Cu conventia folosita in reprezentarea matricilor de cost adiacenta, se poate considera ca D_ij ¹ Æ i, j I V. Daca a(D_ij) < ¥ atunci D_ij, este drum in G de la i la j iar daca a(D_ij) = ¥, atunci D_ij este drum in digraful complet simetric obtinut din G prin adaugarea arcelor lipsa, cu ponderea ¥. Rezulta ca toate multimile, pe care se considera minimele in problemele precedente, sunt nevide si, cum digrafurile considerate sunt finite, rezulta ca aceste multimi sunt finite (in fiecare drum varfurile sunt distincte), deci minimele considerate exista.

2. Algoritmii de rezolvare a problemei (P1) se obtin din algoritmii de rezolvare a problemei (P2) adauganduli-se un test suplimentar (evident) de oprire. Problema (P3) se poate rezolva iterand un algoritm de rezolvare a problemei (P2). Sunt posibile insa solutii mai eficiente.

Ne vom ocupa in continuare de rezolvarea problemei (P2).

Teorema 1. Fie G = (V, E) digraf, V = , s I V si a : E R, astfel incat

(I) C circuit in G, a(C) > 0.

Atunci (u₁, ., u_n) este o solutia sistemului

(*)

daca si numai daca i I V, D^*_si I D_si astfel incat a(D^*_si) = u_i si a(D^*_si) = min.

Demonstratie : " " Fie D^*_si (i I V) solutii ale problemei (P2) cu a(D^*_si) = min. Notam cu u_i = a(D^*_si) (i I V).

Sa observam ca ipoteza (I) asigura faptul ca u_s = 0; Pentru i ¹ s drumul D^*_si are un penultim varf j. Daca D_sj este drumul de la s la j determinat pe D^*_si de varful j, avem: u_i = a(D^*_si) = a(D_sj) + a_ji ³ a(D^*_sj) + a_ji = u_j + a_ji.

Presupunem ca u_i > u_j + a_ji, adica a(D_sj) > a(D^*_sj).

Avem 2 cazuri posibile :

i Ï V(D^*_sj). Atunci D¹ =D^*_sj (j, ji, i) I D_si si a(D¹) = a(D^*_sj) + a_ji < a(D_sj) + a_ji = a(D^*_si), ceea ce contrazice alegerea drumului D^*_si .

i I V(D_sj^*). Fie D_si^* = (D_sj) (D_ij) cele doua drumuri determinate pe D_sj^* de varful i. Atunci circuitul C = (D_ij) (j, ji, i) are costul a(C) = a(D_ij) + a_ji = a(D_sj^*) - a(D_sj) + a_ji = u_j + a_ji - a(D_sj) £ u_j + a_ji - a(D_sj^*) = u_j + a_ji - u_i < 0, contrazicand ipoteza (I)

Rezulta ca presupunerea ca u_i nu satisface (*) este falsa si suficienta teoremei este demonstrata.

Notam ca de fapt am dovedit mai sus ca a(D_sj) = a(D _sj) adica, daca j este varful dinaintea lui i pe un drum de cost minim de la s la i atunci si portiunea de drum de la s la j este de cost minim de la s la j. Inductiv rezulta ca: (Principiul optimalitatii al lui Bellman) daca D*_si este drum de cost minim de la s la i atunci j I V(D*_si) daca D*_si = D_sj D_ji atunci D_sj (respectiv D_ji) sunt drumuri de cost minim de la s la j (respectiv de la j la i).

'Þ'. Dovedim ca daca (u₁, ., u_n) este o solutie a lui (*) atunci:

a)      D_si I D_si : u_i = a(D_si) i I V

b)      Pentru orice i I V, u_i =min (=a(D*_si))

a)            Daca i = s atunci u_s = 0 si drumul D_ss satisface a(D_ss) = 0 = u_s. Daca i ¹ s, consideram urmatorul algoritm :

begin

v:=i;

k:=0;

while v ¹ s do

begin

determina w astfel incat u_v = u_w + a_wv ;

i_k:=v;

k:=k+1;

v:=w;

end;

i_k+1:=s

end.

Sa observam ca algoritmul determina drumul :

D : (s =) i_k+1, i_k+1i_k, . . ., i₁, i₁i₀, i₀ (= i)

cu D I D_si satisfacand a(D) = a(i_k+1i_k) + . + a(i₁i₀) = = u_i - u_s = u_i.

Nu este posibil ca intr-o iteratie oarecare ca w I , caci atunci s-ar obtine un circuit C de cost total 0, contrazicand ipoteza (I).

Din constructie se observa ca .

b)            Fie = a(D*_si) i I V. Conform primei parti a demonstratiei , , satisfac sistemul (*). Presupunem ca u = (u₁, . . ., u_n) ¹ . Cum u_s = = 0, rezulta ca exista i ¹ s astfel incat u_i ¹ si j I V(D_si), j ¹ i, u_j = , unde D_si este drumul construit la (a) pentru . Atunci avem:

Observatii 1. Din demonstratie rezulta ca pentru rezolvarea problemei P2 este suficient sa obtinem o solutie a sistemului (*). Drumurile corespunzatoare se obtin ca la (a). Algoritmii pe care ii vom prezenta se vor ocupa de rezolvarea sistemului (*). Totusi, daca avem u_i = u_k + a_ki atunci asa cum am vazut, k este varful dinaintea lui i de pe drumul minim de la s la i de cost u_i. Rezulta ca daca in algoritmul de rezolvare a lui (*) construim un vector inainte = array[1..n] of V cu interpretarea finala 'inainte[i] = varful dinaintea lui i de pe drumul minim de la s la i', atunci varfurile acestui drum pot fi determinate in O(n) construind sirul i, inainte[i], inainte[inainte[i]], ., pana se depisteaza varful s.

2. Daca algoritmii de rezolvare a lui (*) vor evita (prin modul de actualizare a vectorului inainte) aparitia circuitelor de cost total 0, atunci se observa ca, desi nu mai are loc unicitatea solutiei sistemului (*), problema (P2) este rezolvata. Rezulta ca acesti algoritmi vor rezolva problema (P2) in conditia:

(I') C circuit in G, a(C) ³ 0.

3. In cazul grafurilor, rezolvarea problemelor (P1) - (P3) corespunzatoare se poate face utilizand algoritmii pentru digrafuri, prin inlocuirea fiecarei muchii cu o pereche de arce simetrice de acelasi cost ca si muchia pe care o inlocuiesc. Dificultatea unei astfel de abordari rezulta din introducerea pentru muchii de cost negativ a unor circuite de lungime 2 de cost negativ. Deci, in cazul garfurilor, algoritmii pentru digrafuri sunt valabili doar daca toate costurile sunt nenegative.

4. Avand in vedere ca multimile D_ij sunt finite se pot considera probleme analoage problemelor (P1) - (P3) inlocuind min cu max. Utilizarea ideii uzuale,

prin inlocuirea costurilor a_ij cu - a_ij este posibila doar in cazul digrafurilor in care pentru orice circuit C avem a(C) £ 0. In particular, aceasta abordare este posibila in cazul digrafurilor fara circuite (ca in aplicatiile b) si c) prezentate). Daca digraful initial are circuite, problemele de drum de cost maxim se pot dovedi usor prin reducerea polinomiala la probleme hamiltoniene) a NP - dificile.

Rezolvarea problemei (P2) in cazul digrafurilor fara circuite

In acest caz sortarea topologica a digrafului, care ofera o numerotare aciclica, sistemul (*) se poate rezolva prin substitutie :

begin

Sorteaza topologic G;

u₁ := 0; inainte[1] := 0;

for i:=2 to n do

begin

u_i :=¥;

inainte[i]:=0;

for j:=1 to i -1 do

if u_i > u_j + a_ji then

begin

u_i := u_j + a_ij;

inainte[i]:=j;

end;

end;

end.

Complexitatea pasului 2 este, evident O(1+2+.+n-1)=O(n²)

Notam ca in enuntul algoritmului am presupus ca varful s in problema (P2) devine in numerotarea aciclica varful 1, (altfel se rezolva problema P2 doar in subdigraful indus de varfurile i, care vor fi in numerotarea aciclica mai mari sau egale decat s).

Rezolvarea problemei (P2) in cazul costurilor nenegative.

Daca a_ij ³ 0 ij I E atunci conditia (I) este indeplinita si o solutie a sistemului (*) se poate obtine cu ajutorul urmatorului algoritm (Dijkstra, 1961) .

Se considera S V astfel incat pe tot parcursul algoritmului are loc

(D)

Daca se reuseste construirea lui S astfel incat S = V, atunci problema este rezolvata. Initial, se va considera S = si in n - 1 pasi se adauga la S cate un varf nou din V

Algoritmul lui Dijkstra

begin

S:=s; u_s :=0;inainte[s]:=0;

for i I V do

begin

u_i := a_si; inainte[i]:=s;

end;

while S ¹ V do

begin

determina j*IVS a.i. u_j*=min;

S:=SU;

for j I V S do

if u_j > u_j* + a_j*j then

begin

u_j := u_j* + a_j*j;

inainte[j]:=j*;

end;

end;

end.

Corectitudinea algoritmului va rezulta daca vom arata ca, daca inaintea unei iteratii din pasul 2 are loc (D), atunci, dupa executia acelei iteratii, (D) are loc de asemenea .

Aratam mai intai ca in ipoteza ca (D) are loc, atunci adaugarea lui j* la S nu contrazice (D). Deci trebuie dovedit ca daca u_j* = min atunci u_j* = min. Presupunem ca daca exista D¹_sj* I D_sj* astfel incat a(D¹_sj*) < u_j*. Fie k primul varf al drumului D¹_sj* (in parcurgerea sa din s), astfel incat k Ï S, atunci a(D¹_sj*) = a(D¹_sk) + a(D¹_kj*).

Din alegerea lui k, avem V(D¹_sk) S = si cum (D) are loc, avem a(D¹_sk) = u_k. Obtinem u_j* > a(D¹_sk*) = u_k + a(D^*_kj) ³ u_k (costurile sunt nenegative), ceea ce contrazice alegerea lui j*. Contradictia obtinuta arata ca, dupa atribuirea S := SU, prima parte a conditiei (D) are loc.

Pentru ca si cea de-a doua parte a conditiei (D) sa aiba loc dupa aceasta atribuire, sa observam ca j I V (S È ) avem min{a(D_sj) | D_sj I D_sj, V(D_sj) (S È ) = } = min(min{a(D_sj) | D_sj I D_sj, V(D_sj) S = }, min).

Cum (D) are loc, primul dintre cele doua minime de mai sus este u_j. Fie a_j valoarea celui de-al doilea minim si fie D¹_sj drumul pentru care se realizeaza. Cum j* I V(D¹_sj) avem a_j = a(D¹_sj*) + a(D¹_j*j).

Intrucat S È satisface prima parte a lui (D), avem a(D¹_sj*) = u_j* (altfel s-ar contrazice alegerea lui D¹_sj inlocuind in D¹_sj, portiunea D¹_sj* cu un drum de cost mai mic). Deci a_j = u_j* + a(D¹_j*j).

Daca drumul D¹_j*j este de lungime 1 atunci avem a_j = u_j + a(D¹_j*j). Altfel, considerand k varful dinaintea lui j de pe drumul D¹_sj avem k ¹ j, k S si a_j = a(D¹_sk) + a_kj. Cum S È satisface prima parte a lui (D), obtinem a_j = u_k + a_kj.

Intrucat S satisface (D), u_k este costul unui drum minim de la s la k cu varfurile continute in S deci a_j este costul unui drum de la s la j cu varfurile continute in S. Rezulta ca a_j ³ u_j caci S satisface (D). Am obtinut ca singurul caz cand a_j < u_j este atunci cand a_j = u_j* + a_j*j, situatie testata in ciclul for al pasului 2.

Rezulta ca (D) are loc pe tot parcursul algoritmului si deci valorile finale ale variabilelor u_i reprezinta solutia sistemului (*). Evident, tabloul inainte este actualizat pentru memorarea implicita a drumurilor de cost minim. Complexitatea algoritmului, in descrierea data este O(n²) datorita selectarii minimelor de la pasul 2.

Observatii :

Este posibila organizarea unei cozi cu prioritate pentru memorarea valorilor u_i, i I V S, astfel incat extragerea minimului sa se faca in O(1), iar actualizarile necesare in pasul 2 sa se faca in timp total de O(m log n) unde m = | E |.

Daca se doreste rezolvarea problemei (P1) cu ajutorul algoritmului lui Dijkstra, atunci la introducerea lui t in S, se poate opri algoritmul. Complexitatea, in cazul cel mai nefavorabil, ramane aceeasi. Totusi, in situatii practice concrete exista posibilitatea de a grabi introducerea lui t in S utilizand o functie de dirijare a procesului de constructie a lui S.

O functie g : V R₊ se numeste estimator consistent daca :

i         (i) i I V u_i + g(i) £ min

ii       (ii) ij I E g(i) £ a_ij + g(j).

Sa observam ca g(i) = 0, i este un estimator consistent. Daca V(G) este o multime de puncte din plan, atunci g(i) = distanta (euclidiana) de la i la t este un estimator consistent, daca sunt satisfacute conditiile (ii). Daca g este un estimator consistent atunci se poate modifica alegerea lui j* in algoritm astfel: u_j* + g(j*) = min. Algoritmul ramane valabil (demonstratia este identica situatiei g(i) = 0, i si se foloseste (ii) repetat ). Avantajul este acela ca se vor introduce in S varfuri care sa ne apropie de t.

In implementarea care rezulta din descrierea algoritmului lui Dijkstra, s-a presupus (asa cum am precizat) ca se dispune de matricea de cost-adiacenta a digrafului. In cazul digrafurilor cu multe varfuri ( in care, de exemplu, listele de adiacenta sunt memorate in memoria secundara), sau in cazul digrafurilor date functional (se dispune de o procedura care construieste pentru un varf dat, lista sa de adiacenta, ca de exemplu in aplicatia c)) aceasta implementare este neeficienta, respectiv neaplicabila. O implementare care nu are aceste deficiente este urmatoarea data de Glover, Klingman si Philips (1985) ( Partition Shortest Path algorithm, PSP algorithm)

begin

u_s:=0; inainte[s] := 0; S := 0; NOW := s; NEXT :=Ø ;

while NOW È NEXT ¹ Ø do

begin

while NOW ¹ Ø do

begin

Extrage i din NOW;

S := S È ;

L := N⁺_G(i);

for j I L S do

if j Ï NOW È NEXT then

begin

u_j:= u_i+ a_ij;inainte(j):=i;

introdu j in NEXT

end

else

if u_j > u_i + a_ij then

begin

u_j:= u_i+ a_ij;

inainte(j):=i;

end

end;

if NEXT ¹ Ø then

begin

determina d = min;

transfera i I NEXT cu u_i = d in NOW

end

end.

Rezolvarea problemei ( P2 ) in cazul general.

Daca exista ij I E astfel incat a_ij < 0 algoritmul lui Dijkstra nu mai este valabil in general (introducerea lui j* in S poate conduce la violarea conditiei (D)). Considerand indeplinita conditia (I') vom rezolva sistemul (*) prin aproximatii succesive.

Consideram i I V si m = 1, ., n-1

(BM) u_i^m = min

Cum orice drum in G are cel mult n - 1 arce rezulta ca daca reusim constructia lui

u¹= (u₁¹, , u_n¹), u²= (u₁², , u_n²), ., u^n-1 =( u₁^n-1, , u_n^n-1) , atunci u^n-1 este solutia sistemului (*). Algoritmul care rezulta este urmatorul:

Algoritmul lui Bellman, Ford, Moore ( aproximativ 1960 )

begin

u_s¹:=0; for i I V do u_i¹:= a_si ;

for m = 1 to n - 2 do

for i = 1 to n do

u_i^m+1 := min(u_i^m, min_j¹i(u_j^m + a_ji))

end.

Pentru a demonstra corectitudinea algoritmului, aratam ca daca u^m (m ³ 1) satisface (BM) atunci si u^m+1 o satisface. Fie i I V si consideram multimile de drumuri:

A = .

B = .

C = .

Atunci A = B È C si min = min(min, min).

Cum u^m satisfac (BM) rezulta ca

min(a(D) | D I A) = min(u_i^m, min). Fie min = a(D⁰), D⁰ I C. Daca j este varful ce-l precede pe i in D⁰ (exista, intrucat D⁰ are macar 2 arce) atunci a(D⁰) = a(D⁰_sj) + a_ji ³ u_j^m + a_ji intrucat D⁰_sj are m arce si u^m satisface (BM).

Rezulta ca min = min valoare care in algoritm se atribuie lui u_i^m+1. Observam ca algoritmul are complexitate de O(n³) daca determinarea minimului din pasul doi necesita O(n) operatii. Determinarea drumurilor minime se face mentinand vectorul inainte, initializat in mod evident in pasul 1 si actualizat in mod corespunzator, la stabilirea minimului din pasul 2.

Observatii:

Daca la algoritm se adauga si pasul 3:

if ( i I V astfel incat u_i^n-1 > min_{j ¹ i}(u_i^n-1 + a_ji)) then

"Exista circuit de cost negativ" .

se obtine posibilitatea testarii in O(n³) a existentei unui circuit de cost negativ in digraful G. In adevar, daca

(1) u_i^n-1 > min_j¹i(u_j^n-1 + a_ji) = u_k^n-1 + a_ki,

atunci, din demonstratia corectitudinii algoritmului, rezulta ca singura posibilitate este ca u_k^n-1 = a(D⁰), unde D⁰ ID_sk are exact n - 1 arce si deci varful i I V(D_sk). Deci u_k^n-1 = a(D⁰) = a(D⁰_si) + a(D⁰_ik) = u_i^n-1 + a(D⁰_ik) (u^n-1 este solutie a sistemului (*), si se aplica principiul optimalitatii a lui Bellman).

Circuitul C = D⁰_ik (k, ki, i) are costul a(C) = a(D⁰_ik) + a_ki = u_k^n-1 - u_i^n-1 + a_ki < 0, din ipoteza (1). Depistarea circuitului C se face simplu (O(n)) utilizand vectorul inainte: ( k, inainte(k), inainte(inainte(k)), ., i, k) sunt varfurile sale in ordinea inversa a parcurgerii).

2. daca k < n-1 astfel incat u^k = u^k+1 atunci algoritmul se poate opri.

Descriem in continuare o implementare a acestui algoritm, care are complexitatea O(nm) (m = | E |). Vom folosi o coada UQ in care se vor pastra varfurile i carora li se modifica u_i curent (se va renunta, evident, la memorarea tuturor aproximatiilor succesive). Prezenta unui varf in coada se va face utilizand un vector boolean UB. Vom utiliza de asemenea un tablou nr = array[1..n] of integer care contorizeaza pentru fiecare varf i numarul modificarilor variabilei u_i corespunzator lui i. Atunci cand nr(i) ³ n suntem in situatia din observatia 1 precedenta si putem opri algoritmul cu mesajul existentei circuitului negativ. Descrierea algoritmului :

begin

1: u_s=0; inainte(s) := 0; UQ = ; UB[s] := true; nr[s] := 1;

for i I V do

begin

u_i := infinit; UB[i] := false; nr[I] := 0;

end;

2: while UQ<>0 do

begin

extrage primul element i din UQ

nr[i] := nr[i] + 1

if nr[i] >= n + 1 then

begin

"exista circuit de cost negativ ce trece prin varful i"

goto 3;

end;

UB[I] := false;

for j I A(i) do

if u_i + a_ij < u_j then

begin

u_j =u_i + a_ij;

if not UB[j] then

begin

adauga j la UQ;

UB[j] := true;

end;

end;

end;

3 : end.

Nu am mai introdus operatiile necesare intretinerii tabloului inainte intrucat sunt evidente si ar ingreuna lecturarea textului.

Rezolvarea problemei (P3).

Consideram u_ij = min, i,j I V. Problema se reduce la determinarea matricii U = (u_ij)_nn, atunci cand se cunoaste A, matricea de cost - adiacenta. Drumurile de cost minim vor fi obtinute in O(n) daca odata cu determinarea matricii U se va construi matricea Inainte = (inainte(i, j))_nn cu elementele avand semnificatia inainte(ij) = varful dinaintea lui j de pe drumul de cost minim de la i la j in G.

Sa observam ca daca a_ij ³ 0 i, j atunci, iterand algoritmul lui Dijkstra pentru s I , se obtine un algoritm de complexitate O(n³).

Daca G nu contine circuite de cost negativ, dar exista si arce de cost negativ, iterand algoritmul lui Bellman-Ford pentru s = 1..n se obtine un algoritm de complexitate O(n⁴). Aratam in continuare ca se poate proceda si mai eficient.

Solutia I^a . Fie a : V R a. i. i, j I E a(i) + a_ij ³ a(j). Consideram a*: E R₊ data de

a*_ij = a_ij + a(i) - a(j), i, j I E. Avem a*_ij ³ 0 si, in plus, D_ij I D_ij,

(2) a*(D_ij) = a(D) + a(i) - a(j).

Rezulta ca se poate itera algoritmul Dijkstra pentru obtinerea drumului de cost a* minim si din relatia (2) se observa ca un drum este de cost a* minim daca si numai daca este drum de cost a minim. Rezulta urmatorul algoritm :

determina a si construieste A* .

rezolva (P3) pentru A* construind U* si Inainte.

3. determina U (u_ij = u*_ij - a (i) + a(j), ij).

Pasul 2 al algoritmului necesita O(n³) operatii prin iterarea algoritmului lui Dijkstra. Pasul 1 se poate realiza in O(n³) operatii, fixand s I V si rezolvand (P2) cu algoritmul Bellman - Ford. In adevar, daca u_i, i I V este solutia lui (P2) atunci u_i, i I V este solutie a sistemului (*), deci u_j = min_i¹j adica ij I E, u_j £ u_i + a_ij, deci a_ij + u_i - u_j ³ 0. Prin urmare se poate considera a(i) = u_i, i I V.

Solutia a II-a.

Fie u_ij^m = min } i, j, m I

Atunci, evident u_ij¹=a_ij i, j I V (presupunem, din nou matricea A avand elementele diagonale egale cu 0). In plus,

u_ij^m+1 = min i, j I V, m = 1, 2, , n

Aceasta ultima relatie se poate justifica inductiv: un drum de cost minim de la i la j care nu are varfuri interioare ³ m + 1 poate sa nu contina varful m, si atunci are costul u_ij^m, sau poate contine varful m, si atunci, din principiul optimalitatii al lui Bellman si ipoteza inductiva, este u_im^m + u_mj^m.

Evident, daca se obtine u_ii^m < 0 atunci digraful contine un circuit de cost negativ C care trece prin varful i, cu V(C) . Aceasta solutie a problemei (P3) este cunoscuta ca algoritmul lui Floyd -Warshal si poate fi descris astfel:

begin

1: for i:=1 to n do

for j:=1 to n do

begin

inainte(i,j):=i;

if i = j then

begin

a_ii := 0; inainte(i, i):=0

end

end;

2: for m:=1 to n do

for i:=1 to n do for j:=1 to n do

if a_ij>a_im+a_mj then

begin

a_ij:=a_im+a_mj;

inainte(i,j):=inainte(m,j)

if (i=j and a_ij<0) then

begin

"circuit negativ" ;

goto 3

end

end;

3: end.

Evident, complexitatea algoritmului este de O(n³).

Observatie. Daca digraful nu contine circuite de cost negativ, atunci initializand

a_ii :=0, valorile finale ale elementelor diagonale dau costul minim al cate unui circuit ce trece prin varful corespunzator.

Teorema lui Menger si aplicatii ale acesteia.

Definitie. Fie G = (V, E) (di)graf si X,Y V. Numim XY - drum in G orice drum D in G de la un varf x I X la un varf y I Y, astfel incat

V(D) X = si V(D) Y = .

Vom nota cu D(X, Y; G) multimea tuturor XY-drumurilor in G .

Sa observam ca daca x I X Y atunci drumul de lungime 0 , D = , este XY-drum.

Vom spune ca drumurile D₁ si D₂ sunt disjuncte daca V(D₁) V(D₂) = Ø.

Probleme practice evidente, din retelele de comunicatie, dar si unele probleme legate de conexiunea garfurilor si digrafurilor, necesita determinarea unor multimi de XY - drumuri disjuncte si cu numar maxim de elemente. Vom nota cu p(X, Y; G) numarul maxim de XY - drumuri disjuncte in (di)graful G. Teorema care precizeaza acest numar a fost stabilita de Menger in 1927 si constituie unul din rezultatele fundamentale din teoria garfurilor.

Definitie. Fie G = (V, E) un digraf si X, Y V. Numim multime XY - separatoare in G o multime Z V astfel incat D I D(X, Y; G), V(D) Z ¹ Ø.

Notam cu S(X, Y; G) = si k(X, Y; G) = min. Din definitie, rezulta urmatoarele proprietati imediate ale multimilor XY - separatoare:

(a)    Daca Z I S(X, Y; G) atunci D I D(X, Y; G) D nu este drum in G - Z.

(b)   X, Y I S(X, Y; G)

(c)    Daca Z I S(X, Y; G) atunci A astfel incat Z A V avem A I S(X, Y; G).

(d)   Daca Z I S(X, Y; G) si T I S(X, Z; G) sau T I S(Z , Y; G) atunci T I S(X, Y; G)

Teorema 1. Fie G = (V, E) (di)graf si X, Y V. Atunci

p(X, Y; G) = k(X, Y; G).

Demonstratie: 1⁰. Daca p = p(X, Y; G) si D₁, D₂, ., D_p sunt XY - drumuri disjuncte in G, atunci Z I S(X, Y; G) avem Z V(D_i) ¹ Ø si cum D_i sunt disjuncte (i = 1, p): |Z| ³ |Z È_i^p₌₁ V(D_i)| =

=å_{i=1, p} |Z V(D_i) | ³ å_{i=1, p} 1 = p.

Deci Z I S(X, Y; G) |Z| ³ p; in particular k(X, Y; G) ³ p(X, Y; G).

2⁰. Aratam prin inductie dupa a(G) = | V | + | E | ca

(*) G = (V, E) , X, Y V, k(X, Y; G) XY - drumuri disjuncte in G.

(Evident din (*) rezulta ca p(X, Y; G) ³ k(X, Y; G) si deci teorema e demonstrata). Cum (*) se verifica pentru (di)grafuri G cu a(G) = 1, 2, consideram in pasul inductiv ca (*) are loc pentru orice (di)graf G' si orice X', Y' V(G'), cu a(G') < a(G). Pentru a exclude cazurile banale, vom presupune ca X Y, Y X si k = k(X, Y; G) > 0.

Cazul 1. Exista Z I S(X, Y; G) a. i. |Z| = k, Z ¹ X, Y .

Consideram V_XZ = si V_ZY = .

Sa observam ca V_XZ V_ZY = Z (daca exista v I V_XZ È V_ZY - Z, atunci se obtine ca Z nu este XY - separatoare; daca exista z I Z a. i. z Ï V_XZ V_ZY atunci Z - este XY - separatoare, contrazicand | Z | = k(X, Y; G)). Pe de alta parte, exista x I X - Z (daca X Z, atunci cum X I S(X, Y; G) si | Z | = k(X, Y; G) rezulta X = Z, contrazicand ipoteza cazului 1) si evident x Ï V_ZY (altfel, Z nu ar fi XY - separatoare). Rezulta |V_ZY| < | V |. In mod similar |V_XZ| < | V |.

Fie G_XZ = [V_XZ]_G si G_ZY = [V_ZY]_G. Din observatiile precedente: a(G_XZ), a(G_ZY) < a(G).

Sa observam ca k(X, Z; G_XZ) = k si k(Z, Y; G_ZY) = k (Z este XZ - separatoare in G_XZ, respectiv ZY - separatoare in G_ZY si are cardinalul k; daca in unul din cele doua grafuri, ar exista o multime T separatoare de cardinal < k, atunci, utilizand observatia (d), se contrazice definitia lui k pentru G, X si Y).

Din ipoteza inductiva, rezulta ca exista k X Z - drumuri disjuncte in G_XZ si k Z Y - drumuri disjuncte in G_ZY. Cum V_XZ V_ZY = Z si | Z | = k, rezulta ca aceste 2k drumuri se pot concatena doua cate doua in G si deci (*) are loc.

Cazul 2. Z X Y - separatoare a. i. | Z | = k avem Z = X sau Z = Y.

Presupunem, pentru precizarea notatiilor, Z = X. Cum X Y, x I X Y. X - nu este XY - separatoare (are mai putin de k elemente). Exista deci un XY - drum in G. Fie e = xy prima muchie (arc) a acestui drum (exista!). Sa observam ca y Ï X. Consideram G' = G - e. Avem a(G') < a(G), deci (*) are loc pentru G', X si Y.

Daca k(X, Y; G') = k, atunci cele k XY - drumuri disjuncte din G' sunt XY - drumuri disjuncte si in G deci (*) are loc pentru G, X si Y.

Daca k(X, Y; G') < k, atunci in G' exista Z' XY - separatoare cu | Z' | = k - 1 (se aplica, eventual proprietatea (c)). Z' nu este XY - separatoare in G (| Z' | < k). Singurele XY - drumuri pe care Z nu le intersecteaza sunt cele care au drept prima muchie (arc) pe e. Din definitia lui k, rezulta ca x Ï Z', y Ï Z' si |Z' È | = |Z' È | = k. Din alegerea lui x, y avem Z' È ¹ Y si Z' È ¹ X. Din ipoteza cazului 2, rezulta atunci ca Z' È = X si Z' È = Y. Cele k drumuri din (*) sunt in acest caz _zIZ' si (x, xy, y).

Cu acestea , teorema este demonstrata.

Observatii :

1⁰ Egalitatea min-max din enuntul teoremei este interesanta si conduce, asa cum vom vedea, la rezultate importante, in cazuri particulare.

2⁰. Teorema se poate demonstra si algoritmic ca o consecinta a teoremei fluxului maxim-sectiunii minime.

Forma echivalenta in care a fost enuntata si demonstrata initial de Menger (1927) teorema 1 este:

Teorema 1'. Fie G = (V, E) un (di)graf si s, t I V, astfel incat s ¹ t , st Ï E. Exista k drumuri intern disjuncte de la s la t in graful G daca si numai daca indepartand mai putin de k varfuri diferite de s si t, in graful ramas exista un drum de la s la t.

Notam ca doua drumuri sunt intern disjuncte daca nu au varfuri comune cu exceptia extremitatilor. Se observa ca daca se considera X = N_G(s) si Y = N_G(t) (respectiv, N⁺_G(s) si N^-_G(t) in cazul digrafurilor) teorema 1' se obtine imediat din teorema 1. Reciproc, o constructie inversa celei de mai sus asupra tripletului G, X, Y din teorema 1, arata ca teorema 1 se obtine din teorema 1'.

Am definit un graf G p - conex (p I N^* ) daca G = K_p sau daca | G | > p si G nu poate fi deconectat prin indepartarea a mai putin de p varfuri. Utilizand teorema 1' obtinem.

Consecinta. Un graf G este p - conex daca G = K_p sau st I E() exista p drumuri intern disjuncte de la s la t in G.

Determinarea numarului k(G) de conexiune a grafului G (cea mai mare valoare a lui p pentru care G este p-conex) se reduce deci la determinarea lui p(, ; G) problema care vom dovedi ca se poate rezolva in timp polinomial.

Un caz particular interesant al teoremei 1, se obtine atunci cand G este un graf bipartit iar X si Y sunt cele doua clase ale bipartitiei :

Teorema 2. (Konig,1931) Daca G = (S, R; E) este un graf bipartit, atunci cardinalul maxim al unui cuplaj este egal cu cardinalul minim al unei multimi de varfuri incidente cu toate muchiile grafului.

Demonstratie: Evident, cardinalul maxim al unui cuplaj in G este p(S, R; G), care este egal, conform teoremei 2, cu k(S, R; G). Teorema rezulta imediat daca observam ca o multime de varfuri este SR - separatoare daca si numai daca este incidenta cu orice muchie a grafului.

O aplicatie, fundamentala in numeroase rationamente combinatorii, a acestei teoreme este teorema lui Hall (1935).

Definitie : Fie I si S multimi finite nevide. Numim familie de submultimi ale lui S (indexata dupa I) orice aplicatie A : I 2^S. Vom nota familia A = (A_i; i I I) si vom folosi notatia functionala uzuala A(J) = U_jIJA_j (pentru J I).

Daca A = (A_i; i I I) este o familie de submultimi ale lui S, o functie r_A : I S cu proprietatea ca r_A(i) I A_i, i I I se numeste functie de reprezentare pentru familia A. In acest caz, (r_A(i); i I I) formeaza un sistem de reprezentanti a familiei A. Daca functia de reprezentare r_A este injectiva atunci r_A(I) S se numeste sistem de reprezentanti distincti ai familiei A, sau transversala.

Problema centrala in teoria transversalelor este aceea de a caracteriza familiile A care admit transversale (eventual cu anumite proprietati). Prima teorema de acest tip a fost stabilita de Hall in 1935 :

Teorema 3. Familia A = (A_i; i I I) de submultimi ale lui S admite o transversala daca si numai daca

(H) | A(J) | ³ | J | J I.

Demonstratie: Necesitatea este evidenta : daca A admite o functie r_A de reprezentare injectiva atunci J I , r_A(J) A(J) si deci | A(J) | ³ | r_A(J) | ³ | J | (intrucat r_A este injectiva).

Suficienta. Consideram graful bipartit G_A = (I, S; E) unde am presupus I S = Ø (altfel, se considera copii izomorfe disjuncte) iar E = . Se observa ca N_GA(i) = A_i si ca A are o transversala daca si numai daca G_A are un cuplaj de cardinal |I|. In ipoteza ca (H) are loc, aratam ca orice multime de varfuri incidenta cu toate muchiile lui G_A are macar | I | elemente, ceea ce dovedeste existenta cuplajului de cardinal | I | (utilizand teorema 2).

Fie X = I' È S' Ì I È S o multime de varfuri incidenta cu toate muchiile. Rezulta ca N_GA(I - I') S', adica A(I - I') S'. Atunci, | X | = | I' | + | S' | ³ | I' | + |A(I - I')|. Folosind conditia (H) obtinem in continuare: | X | ³ | I' | + |A(I - I')| ³ | I' | + |I - I'| = | I |.

Structura garfurilor p-conexe

Lema 1. Fie G = (V, E) p-conex, | V | ³ p + 1, U V, | U | = p si x I V - U. Exista in G p xU - drumuri cu singurul varf comun x.

Demonstratie: Consideram graful G' = (V È , E'), unde E' = E È . G' este p-conex . In adevar, oricare A cu | A | £ p - 1 G' - A este conex (daca z I A, acest lucru este evident din p-conexiunea lui G; daca A V atunci G' - A este conex intrucat G - A este conex si y I U cu zy I E(G' - A)).

Lema rezulta, aplicand teorema 1' grafului G' si perechii x, z.

Lema 2. Daca G = (V, E) este un graf p-conex p ³ 2, atunci doua muchii e₁ si e₂ si p - 2 varfuri x₁, ., x_p-2 exista un circuit in G care le contine.

Demonstratie: Inductie dupa p.

Daca p = 2, trebuie sa dovedim ca in orice graf 2-conex, prin orice doua muchii trece un circuit. Consideram G' obtinut din G prin insertia cate unui varf pe muchiile e₁(a) si e₂(b). Noul graf este tot 2-conex, deoarece orice varf am scoate, nu se pierde conexiunea. Exista deci in G' doua ab - drumuri disjuncte, care in G ofera un circuit ce contine e₁ si e₂.

Fie p > 2 si presupunem afirmatia adevarata pentru orice graf k-conex, k < p. Fie G p-conex.

Putem presupune ca extremitatile muchiilor e₁ si e₂ nu sunt printre x₁, ., x_p-2, deoarece altfel, afirmatia ar rezulta prin inductie. Graful G - x_p-2 este (p - 1)-conex. Conform ipotezei inductive exista un circuit C ce contine x₁, ., x_p-3 si e₁, e₂. Fie Y multimea varfurilor lui C, | Y | ³ p. Folosind lema 2, exista in G p x_p-2y drumuri cu y I Y, disjuncte. Putem presupune ca pentru un drum x_p-2y, y este primul varf din Y intalnit, asa ca aceste drumuri au cate un singur varf comun cu Y. Dam o orientare circuitului si numerotam varfurile sale conform acestei orientari. Avem deci drumurile

. Varfurile y₁, ., y_p descompun circuitul in drumurile .

Exista un drum dintre acestea, in care nu este continut nici unul de elementele x₁, ., x_p-3, e₁, e₂. Fie acest drum ; atunci

este un circuit ce contine x₁, x₂, ., x_p-2, e₁ si e₂, si lema este demonstrata.

Teorema 4. (Dirac 1953) Daca G = (V, E) este un graf p-conex p ³ 2, atunci prin orice p varfuri ale sale trece un circuit.

Demonstratie. Fie x₁, ., x_p-1, x_p p - varfuri oarecare a lui G. Deoarece graful G este conex, exista e₁ = xx_p-1 si e₂ = yx_p si aplicam lema 3.

Aplicam aceasta teorema precum si idea utilizata in demonstratia lemei 2, pentru a demonstra o conditie suficienta de hamiltonietate interesanta datorata lui Erdos si Chvatal (1972).

Teorema 5. Fie G p-conex. Daca a(G) < p atunci G este hamiltonian.

Demonstratie: Presupunem ca G nu este hamiltonian. Vom obtine o contradictie. Cum G este p-conex , un circuit de lungime cel putin p (conform teoremei lui Dirac de mai sus). Fie C un circuit de lungime maxima in G. Daca G nu este hamiltonian, v Ï C. Intrucat | C | ³ p, conform lemei 2, exista p vC-drumuri disjuncte (cu exceptia lui v) fie ele (numerotarea varfurilor este in ordinea intalnirii lor intr-o parcurgere fixata a circuitului). Notam, pentru fiecare v_i cu w_i varful succesor al lui v_i in parcurgerea lui C.

Atunci, vw_i Ï E, caci altfel am avea circuitul vw_i, w_i, C -w_iv_i, de lungime mai mare decat C. Cum a(G) £ p, atunci multimea nu este stabila. Deci, exista w_sw_t I E. Dar atunci: , drumul (invers) pe C de la v_s la w_t , muchia w_tw_s , drumul (invers) pe C de la w_s la v_t si este un circuit de lungime mai mare decat C, contrazicand ipoteza ca C este de lungime maxima.