Grafuri Neorientate
I. Parcurgerea unui graf
1. Un joc de cuvinte
Acesta e un exemplu mult mai abstract și interesant, găsit pe CSAcademy. Să presupunem că pornim de la un cuvânt de trei litere, căruia îi putem schimba succesiv câte o literă astfel încât să obținem un nou cuvânt valid. Scopul este de a ajunge la un cuvânt dat printr-un număr minim de pași. De exemplu (nu prea am găsit cuvinte în română):
dog > bog > bot > batPutem modela un graf neorientat în care fiecare nod reține câte un cuvânt valid de trei litere. O muchie reprezintă faptul că se poate ajunge de la o extremitate la cealaltă printr-un singur pas. Pentru a rezolva problema va mai trebui doar să determinăm drumul minim de la nodul cu primul cuvânt la cel cu al doilea.
1
Romania
Moldova
Ucraina
Bulgaria
Ungaria
2. Tari vecine
Nodurile sunt reprezentate de tari, iar muchia reprezinta faptul ca doua tari sunt vecine
II. Algoritmi specifici grafurilor1. In graful cu nodurile orase si muchiile drumurile dintre orase, sa se
afle drumul minim dintre doua orase 2. Se da graful tarilor(tarile reprezinta nodurile si muchia reprezinta
faptul ca doua tari sunt vecine). Se stie ca tarile pot fi colorate cu 4 culori, astfel incat sa nu avem doua tari vecine cu aceeasi culoare. Sa se determine toate posibilitatile de colorare a tarilor.
3. Problema podurilor din Königsberg sau calea catre teoria grafurilor
2
Franta
Elvetia
În continuare vom relata o asemenea poveste ale cărei începuturi datează de pe la mijlocul secolului al XVIII-lea. În acele vremuri, în orăşelul Königsberg din Prusia Orientală, locuitorii găsiseră o distracţie destul de originală. Oraşul era străbătut de râul Pregel, care pe teritoriul oraşului se bifurca într-un mod interesant, două braţe ale râului se uneau, apoi se separau din nou, ca iar să se unească, formând o insulă, numită Kneiphof. Insula era legată de maluri cu cinci poduri iar pe fiecare braţ mai avea câte un pod.
Locuitorii se îndârjeau, în zilele de promenadă, să găsească un traseu care să străbată în circuit închis cele 7 poduri o singură dată. Neputând să găsească un astfel de traseu, distracţia s-a transformat în obsesie, apoi s-a apelat la matematicieni pentru găsirea soluţiei. Problema a fost analizată de renumitul matematician Leonhard Euler(1707-1783), născut în Elveţia, la Bâle, care a avut contribuţii hotărâtoare în toate domeniile matematicii cunoscute în epoca sa, precum şi în astronomie.
Euler a cercetat în mod ştiinţific problema şi a făcut o comunicare pe această temă la Academia din St.
3
Petersburg în anul 1736, cu titlul: “Soluţia unei probleme ce aparţine geometriei de poziţie.” El a arătat că problema, în forma în care a fost prezentată, nu are soluţie. Aceasta nu depindea de lungimea, forma sau distanţa podurilor, ci numai de poziţia lor unul faţă de altul. Pentru a putea fi rezolvată problema, Euler a propus să se mai construiască un pod, lucru care s-a înfăptuit mult mai târziu, în secolul XX.
În esenţă problema s-a redus la trasarea unei reţele cu un anumit număr de noduri, printr-un traseu continuu, pornind dintr-un anumit punct, fără a trece de mai multe ori pe acelaşi traseu. A fost definit ordinul unui nod, adică numărul de linii care pleacă din acel nod. Astfel, reţeaua noastră avea 4 noduri, din care 3 de ordinul trei şi unul de ordinul cinci.
4. Problema comis-voiajorului pune următoarea întrebare: „Dată fiind o listă de orașe si drumurile dintre acestea , exista traseu care vizitează fiecare oraș o singură dată și se întoarce la orașul de origine?”
III. Definitie in grafuri si reprezentarea grafurilor
Fie G=(N,M) graf. Orice element din M este o submultime {x,y} cu x si y din M. Vom nota [x,y]={x,y}.Avem [x,y]=[y,x].
Propozitie: Cu o multime cu n noduri putem forma grafuriDemonstratie
Un graf poate avea maxim n*(n-1)/2 muchii({m1,m2,...,mn*(n-1)/2}). Avem grafuri cu 0 ( =Cn(n−1)/2
0 ) muchii, 1 ( =Cn(n−1)/21 ) muchii,..., n*(n-1)/2(=Cn(n−1)/2
n(n−1)/2) muchii.In total sunt Cn(n−1)/2
0 + =Cn(n−1) /21 )+....+Cn(n−1)/2
n(n−1)/2=2n(n-1)/2 grafuri.
Fiind date muchiile [x,y], [x,t] si [a,b] avem urmatoarele definitii:1. Nodurile x si y se numesc extremitati pentru muchia [x,y]
4
12
3 4
5
2. Nodurile x si y se numesc adiacente, deoarece sunt extremitati pentru aceeasi muchie
3. Muchiile care au un varf comun se numesc muchii incidente4. Se numeste grad al unui nod x, numarul de muchii pentru care x este
extremitate(grd(x))5. Un nod de grad 0, se numeste grad izolat6. Un nod de grad 1, se numeste nod terminal sau nod frunza
Propozitie: G=(N,M) graf cu |M|=m 2*m=∑x∈ N
grd (x)
DemonstratieDaca m=1 rezulta ca 2*1=1+1Presupunem ca pentru m muchii avem 2*m=∑
x∈ Ngrd (x)
Fie G un graf cu m+1 muchii. Prin eliminarea unei muchii [x1,x2], obtinem graful G1 cu N=N1 si M1=M-{[x1,x2]} G1 are m muchii 2*m=∑
x∈ N−{x 1 , x 2}grd ( x )+grd ( x1 )−1+grd ( x 2 )−1. Prin adaugarea muchiei [x1,x2] obtinem
graful initial 2*m+2= ∑x∈N−{x 1 , x 2}
grd ( x )+grd ( x1 )−1+1+grd ( x 2 )−1+1 2*(m+1)=∑x∈ N
grd (x)
Definitie: gradul unui graf G este egal cu suma gradelor tuturor nodurilor. Grad(G)=∑
x∈ Ngrd (x).
Reprezentarea grafurilor se face cu ajutorul:1. lista de adiacenta utilizata la prelucrarea dinamica a
grafului2. matricea de adiacenta utilizata la prelucrarea statica a
grafului3. lista muchiilor utilizata pentru citirea grafului din fisier
Exemplu:
1. 1: 2,32: 1,3,53: 1,24:5: 2
5
2. 0 1 1 0 01 0 1 0 11 1 0 0 00 0 0 0 00 1 0 0 0
aij={ 1 ;daca [ i , j ] emuchie0 ;dacanu existamuchie de lai la j
3. 5 41 21 32 32 5
5=n numar de noduri 4=m numar de muchiiUrmeaza in fisier unele sub altele toate cele 4=m muchii.
//CITIRE-1 MATRICE DE ADIACENTAint a[100][100],n,m;ifstream f(„adiacenta.txt”);void citire-1(){ int i,j;f>>n>>m; for(i=1;i<=n;i++) for(j=1;j<=n;j++) f>>a[i][j];f.close();}
//CITIRE-2 MATRICE DE ADIACENTAint a[100][100],n,m;ifstream f(„adiacenta.txt”);
void citire-1(){ int i,x,y;f>>n>>m;
6
for(i=1;i<=m;i++) { f>>x>>y; a[x][y]=a[y][x]= }f.close();}
Proprietati ale matricei de adiacenta:1. Este simetrica2. Suma elementelor de pe linia i, reprezinta gradul nodului i3. Suma elementelor de pe coloana i, reprezinta gradul nodului i4. Suma elementelor matricei, reprezinta gradul grafului5. Suma elementelor de pe linia i este egala cu suma elementelor de pe
coloan i.Propozitie: Numarul elementelor de grad impar este par
DemonstratieFie n numar de noduri, dintre care imp sunt impare si par sunt pare.
Imp+par=n si imp∩par=Ø. ∑x∈ N
grd ( x )=∑x∈ imp
grd ( x )+∑x∈ par
grd ( x ). Cum ∑x∈ N
grd ( x ) si ∑
x∈ pargrd ( x ) sun pare, atunci ∑
x∈ impgrd ( x ) este par. Cum fiecare termen al sumei
este impar ca numarul de termeni este par, adica numarul nodurilor de grad impar este par.Propozitie: Dacă graful G neorientat are n noduri, n>2, atunci cel puţin 2 noduri au acelaşi grad.
Demonstratie Presupunand ca nu exista doua noduri cu acelasi grad rezulta ca∑x∈N
grd ( x )=grd (x1 )+grd (x2 )+…+grd(xn)≥ 0+1+2+…+(n−1 )=(n−1)∗n /2, deoarece nu exista doua noduri cu acelasi grad.
∑x∈ N
grd ( x )=2∗m
Cum ∑x∈ N
grd ( x )=n∗(n−1)/2
rezulta ca graful este complet si deci toate nodurile au acelasi grad contradictie
Definitii: 1. Se numeste lant (drum) intr-un graf G, un sir de noduri x1,x2,...,xn cu
proprietatea ca (x1,x2),( x2,x3),...,( xn-1,xn) sunt muchii2. Un lant se numeste ELEMENTAR, daca toate nodurile din lant sunt
distincte doua cate doua, altfel este NEELEMENTAR3. Un lant se numeste SIMPLU, daca toate muchiile din lant sunt
distincte doua cate doua, altfel este COMPUS7
4. Un drum se numeste hamiltonian, daca este elementar si contine toate nodurile grafului
5. Un drum se numeste eulerian, daca este simplu si contine toate muchiile grafului
6. Se numeste ciclu intr-un graf G, un lant in care extremitatea initiala x1 coincide cu extremitatea finala xn
7. Un ciclu se numeste ELEMENTAR, daca toate nodurile din lant sunt distincte doua cate doua, in afara de primul si ultimul
8. Un ciclu se numeste SIMPLU, daca toate muchiile din lant sunt distincte doua cate doua, altfel este COMPUS
9. Un ciclu se numeste hamiltonian, daca este elementar si contine toate nodurile grafului
10. Un drum se numeste eulerian, daca este simplu si contine toate muchiile grafului
11. Numarul de muchii al unui lant reprezinta lungimea lantuluiProprietati:
a) Un lant hamiltonian are lungimea n-1b) Un ciclu hamiltonian are lungimea nc) Un lant elementar are lungimea ≤n-1d) Un ciclu elementar are lungimea ≤ne) Un lant simplu are lungimea ≤m-1f) Un ciclu simplu are lungimea ≤mg) Un lant eulerian are lungimea mh) Un ciclu eulerian are lungimea m
IV. Tipuri de grafuri 1. CONEX / NECONEX
Un graf se numeste conex, daca exista lant intre oricare doua noduri.G1=(N1,M1) este subgraf conex a lui G=(N,M) daca intre oricare doua noduri din N1 exista lantG1 este componenta conexa a lui G, daca: G1 subgraf al lui G Intre oricare 2 noduri din G1 exista lant G1 este maximal cu cele doua proprietati de mai sus, adica
oricare x ∈N-N1, atunci subgraful G2=(N1∪{x },M ∩ P 2(N 1∪{x }) nu mai este conex
8
Propozitie: Daca un graf G=(N,M) are p componente conexe G1, G2,...,Gp, atunci: n=n1+n2+...+np m=m1+m2+...+mp
2. CICLIC / ACICLICUn graf este ciclic, daca are cel putin un cicluIntr-un graf cu n noduri un ciclu hamiltonian are n muchii
3. ARBOREUn graf aciclic si conex poarta denumirea de arbore. Un arbore are o singura componenta conexaPropozitie: Un arbore cu n≥2 are cel putin doua varfuri terminale
DemonstratieDaca n-am avea nod terminal grad(xi) ≥2, deoarece e conex si nu avem noduri terminale. Avem muchie x1-x2. Avem muchie x2-x3 cu x3≠x1.Avem muchie x3-x4 cu x4≠x1 si x4≠x2. Avem muchie xn-1-xn. Deoarece grad(xn) ≥2 exista muchie intre xn si una din muchiile x1, x2,..., xn-2, adica graful nu e arbore(are cel putin un ciclu).Presupunem ca avem un singur nod terminal x1. La fel se demonstreaza.TeoremăUrmătoarele afirmații sunt echivalente pentru un graf G cu n noduri și m muchii:(1) G este un arbore.(2) G este un graf aciclic cu n-1 muchii.(3) G este un graf conex cu n-1 muchii.
Demonstratie(1)(2) G este aciclic si demonstram prin inductie ca are n-1
muchii, daca G are n noduri. Pentru n=2 este acyclic si are o muchie. Presupunem ca pentru n-1 este acyclic si are n-2 muchii. Daca graful are n noduri, atunci stim ca are cel putin un nod terminal. Eliminand nodul terminal se elimina si o muchie astfel incat graful ramane acyclic, de unde rezulta ca noul graf are n-2 muchii.Adaugand nodul eliminat, graful ramane acyclic si are n-1 muchii.
(1)(3) Se demonstreaza ca la (1) (2)(3) (1) Graful este conex si are n-1 muchii. Ramane sa demonstram ca este acyclic. Daca este cyclic, putem elimina muchii astfel incat graful sa ramana conex si acyclic cu n noduri si n-p<n-1 muchii. Contradictie, deoarece orice arbore cu n noduri
9
are n-1 muchii.Propozitie: Orice pereche de noduri este legată printr-un lanț și numai unul.
DemonstratiePresupunem ca exista doua drumuri distincte intre x1 si x2. Primul este x1,y1,y2,…,x2, iar al doilea este x1,z1,z2,…,x2 exista ciclu c.c.t.d.Propoziție. Orice arbore cu n noduri are n-1 muchii.
DemonstratieRezulta din teorema de mai sus
4. COMPLETUn graf e complet daca intre oricare doua noduri exista muchiePropozitie: Daca G=(N,M) e un graf complet cu n=|N| noduri, atunci graful are 1+2+...+(n-1) =n*(n-1)/2 muchii
5. EULERIANUn graf se numeste eulerian, daca are un ciclu eulerian, sau cu alte cuvinte are un ciclu simplu(care contine toate muchiile grafului o singura data)Propozitie: Pentru un graf conectat G, afirmatiile urmatoare sunt echivalente: 1) G este Eulerian. 2) Fiecare nod al lui G are grad par. 3) Muchiile lui G pot fi partitionate ın cicluri care nu au muchii ın comun
Demonstratie1) 2) G eulerian exista un ciclu simplu care contine toate muchiile
grafului orice intrare intr-un nod are iesirea pe o muchie pe care n-a mai fost toate nodurile au grad par. Daca un nod e izolat, atunci are gradul 0.
2) 3) Cn sunt grafuri euleriene.Graful G nu are niciun nod de grad 1 nu este arbore exista cel putin un Cn1. Eliminand muchiile lui Cn1
obtinem G’ care are toate nodurile de grad impar. Procedand la fel obtinem pe G partitionat in cicluri(Cn1, Cn2, Cn3,..., Cnp)
3) 1) Presupunem ca muchiile lui G pot fi partitionate ın k cicluri disjuncte Cn1 , . . . , Cnk . Deoarece G este conectat, fiecare ciclu este un circuit Eulerian care are un nod comun cu alt ciclu ⇒ ciclurile pot fi ınlantuite pana se obtine un circuit Eulerian care contine toate muchiile lui G.
10
Problema podurilor din Königsber
g
11
Exista nod de grad impar nu este eulerian.
6. HAMILTONIANUn graf este hamiltonian, daca are cel putin un ciclu hamiltonian
Se cunosc conditii suficiente pentru ca un graf sa fie sau sa nu fie hamiltonian:
Teorema lui Dirac: Fie G un graf simplu cu ordinul n ≥ 3. Daca grd(p) ≥ n/2 oricare p∈N, atunci G este Hamiltonian
Demonstratie. Presupunem ca G satisface conditile date, insa G nu este hamiltonian. Fie P=v1,....,vp o cale simpla in G de lungime maximala => toti vecinii lui v1 si ai lui vp sunt pe P. Deasemenea, v1 si vp au cel putin n/2 vecini pe P fiindca grad(G)>=n/2. Demonstram ca exista j apartinand {1,....,p-1} astfel incat vj apartine N(vp) si vj+1 apartine N(v1).Daca n-ar fi a¸sa, atunci pentru fiecare vecin vi de pe P al lui vp (retinem ca sunt ≥ n/2 astfel de vi), vi+1 nu este vecin al lui v1. Ar rezulta ca grad(v1) ≤ p − 1 − n /2 < n − n /2 = n/ 2 , contradictie cu faptul ca grad(G) ≥ n/2.Fie C ciclul v1, v2, . . . , vj , vp, vp−1, . . . , vj+1, v1. Presupunand ca G nu este hamiltonian, exista un nod
12
al lui G care nu este ın P. grad(G) ≥ n/2 ¸si n ≥ 3 implica grad(G) ≥ 2 , deci G este conectat ⇒ G are un nod w care nu-i in P ¸si este adiacent la un nod vi din P. Dar atunci calea care porneste cu w, vi ¸si continua ın jurul ciclului C este mai lunga decat P, contradictie. In concluzie G trebuie sa fie graf hamiltonian.
7. BIPARTITUn graf G=(N,M) este bipartit, daca exista X≠Ø , Y≠Ø , X ∩Y=∅ , X∪Y=N si oricare [a,b] muchie a∈ X si b∈YPropozitie: Intrun graf bipartit nu pot exista cicluri de lungime imparaDaca |N|=n, |X|=p |Y|=n-p si Nr. muchii G ≤p*(n-p)
8. BIPARTIT COMPLETUn graf bipartit complet, este un graf bipartit astfel incat intre oricare a∈ X si b∈Y exista muchieDaca |N|=n, |X|=p |Y|=n-p si Nr. muchii G =p*(n-p)
9. SUBGRAFG1=(N1,M1) se numeste subgraf al grafului G=(N,M), daca N1⊆NM1 M∩⊆ P2(N1)Propozitie: Cu o multime cu n noduri se pot forma 2n-1 grafuri partiale
Demonstratie Putem elimina un nod in Cn
1 moduri.....................Putem elimina n-1noduri in Cn
n−1 moduriIn total sunt Cn
0 + Cn1 +....+Cn
n−1=2n-1 grafuri partiale.
10. GRAF PARTIALUn graf G1=(N1,M1), se numeste subgraf partial al grafului G=(N,M), daca N=N1 si M1⊆MPropozitie: Numarul subgrafurilor lui G=(N,M) este 2m-1, unde m=|M|
DemonstratiePutem elimina o muchie in Cm
1 feluri;Putem elimina doua muchii in Cm
2 feluri;.....................................Putem elimina m muchii in Cm
mfeluri;
13
Obtinem Cm1 +Cm
2 +…+Cmm=2m−1 grafuri partiale
Dacă un graf neorientat conex are n noduri şi m muchii, numărul de muchii care trebuie eliminate, pentru a obţine un arbore este m-n+1.
Dacă un graf are n noduri , m muchii şi p componente conexe , numărul de muchii care trebuie eliminate pentru a obţine un graf aciclic este egal cu m-n+p
V. Algoritmi in grafuri neorientate 1. Determinarea tuturor drumurilor elementare intre doua noduri
#include <iostream>#include <fstream>using namespace std;int a[50][50],n,m,k,as,ev,st[50];
void citire(){ int x,y; ifstream f("muchii.txt"); f>>n>>m; for(int i=1;i<=m;i++) {f>>x>>y; a[x][y]=a[y][x]=1; } f.close();
}
int succesor(int x,int y,int k){ if(st[k]<n) {st[k]++;return 1;} else return 0;}
int valid(int x,int y,int k){ int ok=1; if(a[st[k]][st[k-1]]==0) ok=0; else { for(int i=1;i<=k-1;i++) if(st[k]==st[i]) ok=0; } return ok;}void init(int k){ st[k]=0;}
#include<iostream.h>#include<conio.h>int st[20],n; void tipar(){for(int i=1;i<=n;i++) cout<<st[i]<<' ';cout<<endl;} int valid(int k){ for(int i=1;i<=k-1;i++) if (st[i]==st[k]) return 0; return 1;} void back(int k){for(int i=1;i<=n;i++) {st[k]=i; if (valid(k)) if(k==n) tipar(); else back(k+1); }} void main()
14
int solutie(int x,int y, int k){ if(st[k]==y) return 1; else return 0;
}void afisare(int k){
for(int p=1;p<=k-1;p++) cout<<st[p]<<","; cout<<st[k]<<endl;}
void determinare(int x,int y){ st[1]=x; k=2; init(k); while(k>1) { do { as=succesor(x,y,k); if(as) ev=valid(x,y,k); }while(as&&!ev); if(as) if(solutie(x,y,k)) afisare(k); else {k++;init(k);} else k--;
}}
int main(){ int i,j; citire(); for(i=1;i<=n-1;i++) for(j=i+1;j<=n;j++) determinare(i,j);
return 0;}
{clrscr();cout<<"n=";cin>>n;back(1);getch();}
for (int i = 2; i <= n; i++)
if (!vis[i] && ad[tr[pos - 1]][i]) {
vis[tr[pos] = i] = true; // Adăugăm i la traseu și îl marcăm ca vizitat.
lg += ad[tr[pos - 1]][i]; // Actualizăm lungimea traseului curent.
// Continuăm generarea:
15
bkt(pos + 1);
// Restaurăm vis[i] și lg:
vis[i] = false;
lg -= ad[tr[pos - 1]][i];
}
Dacă am ajuns în schimb la poziția n + 1, înseamnă că am terminat generarea unui traseu. Acum trebuie să ne întoarcem în orașul inițial. Deci, vom verifica dacă există stradă de la 1 la tr[n]. Dacă nu, traseul nu este valid. Dacă da, mai rămâne să adăugăm la lungime costul ultimei muchii a ciclului, adică ad[tr[n]][1]. Apoi comparăm lg cu lgMin și actualizăm soluția dacă este cazul.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
if (pos == n + 1) {
if (!ad[tr[n]][1])
return;
lg += ad[tr[n]][1];
if (lg < lgMin) { // Actualizăm soluția:
lgMin = lg;
for (int i = 1; i <= n; i++)
trMin[i] = tr[i];
}
lg -= ad[tr[n]][1];
return;
}
Optimizare prin branch and boundSe observă ușor că, dacă la un apel al funcției bkt lungimea curentă este mai mare sau egală cu lungimea minimă obținută până atunci, sigur acel început de traseu nu va duce la o soluție mai bună decât cea pe care o avem deja. În acest caz, putem ieși din apel printr-un simplu return.
16
1
2
if (lg >= lgMin)
return;
Acest procedeu de optimizare se numește branch and bound, și se aplică adesea problemelor de backtracking în care trebuie să determinăm un cost minim. El reduce crucial timpul de execuție a programului, deoarece sare peste o grămadă de trasee nefolositoare.Mai jos este un GIF făcut de mine, care ilustrează modul în care funcționează backtracking-ul în această problemă:
Sursă C++Iată o sursă C++ ce implementează algoritmul descris mai sus, rezolvând problema comis-voiajorului.
1
2
3
#include <climits>
#include <fstream>
17
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#define DMAX 100
std::ifstream fin("tsp.in");
std::ofstream fout("tsp.out");
int n, m;
int ad[DMAX][DMAX];
int lgMin;
int trMin[DMAX];
int lg;
int tr[DMAX];
bool vis[DMAX];
void bkt(int pos) {
if (lg >= lgMin)
return;
if (pos == n + 1) {
if (!ad[tr[n]][1])
return;
lg += ad[tr[n]][1];
if (lg < lgMin) {
lgMin = lg;
for (int i = 1; i <= n; i++)
trMin[i] = tr[i];
}
lg -= ad[tr[n]][1];
return;
}
18
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
for (int i = 2; i <= n; i++)
if (!vis[i] && ad[tr[pos - 1]][i]) {
vis[tr[pos] = i] = true;
lg += ad[tr[pos - 1]][i];
bkt(pos + 1);
vis[i] = false;
lg -= ad[tr[pos - 1]][i];
}
}
int main() {
int x, y, z;
lgMin = INT_MAX;
fin >> n >> m;
for (int i = 0; i < m; i++) {
fin >> x >> y >> z;
ad[x][y] = ad[y][x] = z;
}
vis[tr[1] = 1] = true;
bkt(2);
fout << lgMin << '\n';
for (int i = 1; i <= n; i++)
fout << trMin[i] << ' ';
fout << '\n';
fout.close();
return 0;
19
70 }
ComplexitateÎn cel mai nefavorabil caz, numărul total de cicluri hamiltoniene ale grafului dat este (n−1)!/2(n−1)!/2; asta se întâmplă atunci când graful este complet. Există cazuri în care, chiar și cu optimizarea făcută prin branch and bound, vom fi nevoiți să generăm toate aceste cicluri; de exemplu atunci când toate muchiile grafului au același cost.Prin urmare, complexitatea algoritmului este O(n!)O(n!). Teoretic, este o complexitate foarte proastă, însă în practică (pe teste obișnuite, cu n până în 40-60), algoritmul se comportă destul de bine. Există și o soluție ce folosește programare dinamică, de complexitate exponențială, însă nu este foarte practică din cauza cantității mare de spațiu necesară. Voi analiza această abordare într-un articol viitor.
2. Determinarea tuturor drumurilor simple intre doua noduri3. Determinare cicluri elementare plecand de la nodul x14. Determinare cicluri simple plecand de la nodul x15. Determinare ciclu eulerian6. Determinare ciclu hamiltonian(problema comis voiajorului)7. Sa se determine numarul de drumuri dintre oricare doua noduri8. Sa se determine existenta unui drum intre oricare doua noduri9. Percurgerea BFS a unui graf10. Parcurgerea DFS a unui graf11. Algoritmul lui LEE12. Determinarea componentelor conexe13. Colorarea hartilor
1. Notiuni generaleIn scopul descrierii unor activitati din cadrul unui proces de productie sau a relatiilor existente intre elementele unei
structuri organizatorice se pot folosi imagini grafice gen diagrame, schite, grafice etc. O reprezentare dintre cele mai utilizate este cea prin grafuri. Acestea sunt utilizate in special pentru vizualizarea sistemelor si situatiilor complexe.
In general, vom reprezenta-componentele acestora prin puncte in plan-relatiile (legaturile, dependentele, influentele etc) dintre componente prin arce de curba cu extremitatile in punctele
corespunzatoare.Intre doua puncte pot exista unul sau mai multe segmente (in functie de cate relatii dintre acestea, care ne intereseaza,
exista) iar segmentelor li se pot asocia sau nu orientari (dupa cum se influenteaza cele doua componente intre ele), numere care sa exprime intensitatea relatiilor dintre componente etc.
20
Definitia 1. a)Se numeste multigraf un triplet G = (X, A, f) in care X si A sunt doua multimi iar f este o
functie definita pe produsul vectorial al lui X cu el insusi (X2 = XX), care ia valori in multimea partilor multimii A (notata P(A)). b)Multimea X se numeste multimea nodurilor multigrafului si elementele sale se numesc noduri (sau varfuri) ale multigrafului, iar A reprezinta multimea relatiilor (legaturilor) posibile intre doua noduri ale multigrafului.
Definitia 2. a)Se numeste graf orientat un multigraf in care multimea A are un singur element: A = .(In acest caz multimea partilor multimii A are doar doua elemente: multimea vida si intreaga multime A). b)Daca unei perechi orientate (xi, xj) din X2 i se asociaza prin functia f multimea A atunci spunem ca exista arc de la nodul xi la nodul xj iar perechea (xi,xj) se va numi arcul (xi,xj).
c)Nodul xi se numeste nod initial sau extremitate initiala a arcului (xi,xj) iar nodul xj se numeste nod final sau extremitate finala a arcului (xi,xj).
d)Arcul (xi,xj) este incident spre interior varfului xj si incident spre exterior varfului xi. e)Daca pentru un arc nodul initial coincide cu nodul final atunci acesta se numeste bucla. f)Nodurile xi si xj se vor numi adiacente daca exista cel putin unul din arcele (xi,xj) si (xj,xi). g) Daca unei perechi orientate (xi, xj) din X2 i se asociaza prin functia f multimea vida atunci spunem ca nu
exista arc de la nodul xi la nodul xj.Este evident ca a cunoaste un graf orientat este echivalent cu a cunoaste varfurile si arcele sale. Din acest motiv putem defini un graf orientat prin perechea (X,U), unde X este multimea varfurilor sale iar U multimea arcelor sale.
De asemenea, putem cunoaste un graf orientat cunoscand multimea nodurilor si, pentru fiecare nod, multimea arcelor incidente spre exterior. Din acest motiv putem defini un graf orientat ca o pereche (X, ) unde X este perechea nodurilor iar este o functie definita pe X cu valori in multimea partilor lui X, valoarea acesteia intr-un nod x i, (x i) X fiind multimea nodurilor adiacente nodului xi, prin arce pentru care xi este extremitatea initiala .
Definitia 3 Se numeste graf neorientat un multigraf in care multimea A are un singur element iar functia f are proprietatea:
f[(xi,xj)] = f[(xj,xi)] , oricare ar fi nodurile xi si xj din XIn aceste conditii, daca f[(xi,xj)] = f[(xj,xi)] = A atunci perechea neorientata este o muchie iar daca f[(xi,xj)] = f[(xj,xi)]
= spunem ca nu exista muchie intre varfurile xi si xj.Deoarece, in cele mai multe din cazurile practice care vor fi analizate in acest capitol, situatia este modelata matematic
printr-un graf orientat, vom folosi, pentru simplificarea expunerii, denumirea de graf in locul celei de graf orientat iar in cazul in care graful este neorientat vom specifica acest fapt la momentul respectiv.
2. Moduri de reprezentare ale unui grafA. O prima modalitate de reprezentare este listarea efectiva a tuturor nodurilor si a arcelor sale.B. Putem reprezenta graful dand pentru fiecare nod multimea nodurilor cu care formeaza arce in care el este pe prima
pozitie.C. Putem reprezenta geometric graful, printr-un desen in plan, reprezentand fiecare nod printr-un punct(cerculet) si fiecare
arc printr-un segment de curba care are ca extremitati nodurile arcului si pe care este trecuta o sageata orientata de la nodul initial spre cel final.
D. Putem folosi o reprezentare geometrica in care nodurile sunt reprezentate de doua ori, in doua siruri paralele, de la fiecare nod din unul din siruri plecand sageti spre nodurile cu care formeaza arce in care el este pe prima pozitie, de pe al doilea sir (reprezentarea prin corespondenta).
E. Un graf poate fi reprezentat printr-o matrice patratica booleana, de dimensiune egala cu numarul de noduri, in care o pozitie aij va fi 1 daca exista arcul (xi,xj) si 0 in caz contrar, numita matricea adiacentelor directe.
F. Un graf poate fi reprezentat printr-o matrice patratica latina, de dimensiune egala cu numarul de noduri, in care pe o pozitie aij va fi xixjdaca exista arcul (xi,xj) si 0 in caz contrar.
Exemplu: Daca in reprezentarea A avem graful G = (X,U), unde X = si U = , atunci in celelalte reprezentari vom avea:
B) x1 C)x2 x3 x4 x5 x6
D (reprezentarea prin corespondenta)
x1 x2 x3 x4 x5 x6x1 x2 x3 x4 x5 x6
x1 x2 x3 x4 x5 x6
x1 1 1 0 1 1 0x2 0 0 1 1 0 1
21
x3 1 1 0 0 0 0x4 0 0 0 0 1 0x5 0 1 0 0 0 0x6 0 0 0 1 0 0
x1 x2 x3 x4 x5 x6
x1 x1x1 x1x2 0 x1x4 x1x5 0x2 0 0 x2x3 x2x4 0 x2x6
x3 x3x1 x3x2 0 0 0 0x4 0 0 0 0 x4x5 0x5
0 x5x2 0 0 00
x6 0 0 0 x6x4 0 0
E) F)3. Concepte de baza in teoria grafurilor
1. semigraf interior al unui nod xk: este multimea arcelor = care sunt incidente spre interior nodului xk;
2. semigraf exterior al unui nod xk: este multimea arcelor = care sunt incidente spre exterior nodului xk;3. semigradul interior al unui nod xk: este numarul arcelor care sunt incidente spre interior nodului x k = cardinalul
lui si se noteaza cu ;4. semigradul exterior al unui nod xk: este numarul arcelor care sunt incidente spre exterior nodului xk = cardinalul
lui si se noteaza cu ;
5. gradul unui nod xk: este suma semigradelor nodului xk: = + ;6. nod izolat: este un nod cu gradul 0;7. nod suspendat: este un nod cu gradul 1;8. arce adiacente: arce care au o extremitate comuna;9. drum intr-un graf: o multime ordonata de noduri ale grafului: (x1, x2, , xk), cu proprietatea ca exista in graf toate
arcele de forma (xi,xi+1) i = 1,,k-1;10. lungimea unui drum: este numarul arcelor care il formeaza;11. drum elementar: un drum in care fiecare nod apare o singura data;12. drum simplu: un drum in care fiecare arc apare o singura data;13. putere de atingere a unui nod xi X in graful G: numarul de noduri la care se poate ajunge din xi. Puterea de
atingere se noteaza cu p(xi), 1 i n si evident p(xi) .14. drum hamiltonian: un drum elementar care trece prin toate nodurile grafului;15. drum eulerian: un drum simplu care contine toate arcele grafului;16. lant: un drum in care arcele nu au neaparat acelasi sens de parcurgere;17. circuit: un drum in care nodul initial coincide cu cel final;18. circuit elementar: un drum in care fiecare nod apare o singura data, cu exceptia celui final, care coincide cu cel
initial;19. circuit simplu: un drum in care fiecare arc apare o singura data;20. circuit hamiltonian: un circuit care trece prin toate nodurile grafului;21. ciclu: este un circuit in care arcele nu au neaparat acelasi sens de parcurgere;22. ciclu elementar: un ciclu in care fiecare nod apare o singura data, cu exceptia celui final, care coincide cu cel initial;23. ciclu simplu: un ciclu in care fiecare arc apare o singura data;
Observatie: Intr-un graf neorientat notiunile de drum si lant sunt echivalente si de asemenea cele de circuit si ciclu.24. graf partial al unui graf G = (X,U): este un graf G'(X,U') cu U' U;25. subgraf al unui graf G = (X,): este un graf G'(X',') unde X' X si '(xi) = (xi) X' pentru orice xi X';26. graf redus al unui graf G = (X,U): este un graf G*(X*,U*) unde X* este formata din multimile unei partitii de multimi
nevide ale lui X, iar ( , ) exista doar daca i j si exista cel putin un arc in U, de la un nod din la un nod
din .27. graf tare conex: este un graf in care intre oricare doua noduri exista cel putin un drum;28. graf simplu conex: este un graf in care intre oricare doua noduri exista cel putin un lant;Observatie: Pentru grafuri neorientat notiunile de tare conex si simplu conex sunt echivalente, graful numindu-se doar conex;
22
29. componenta tare conexa a unui graf G = (X,U): este un subgraf al lui G care este tare conex si nu este subgraful nici unui alt subgraf tare conex al lui G (altfel spus, intre oricare doua noduri din componenta exista cel putin un drum si nu mai exista nici un nod in afara componentei legat printr-un drum de un nod al componentei).
4. Gasirea drumurilor intr-un graf orientatDaca privim graful ca imagine a unui sistem, nodurile reprezentand componentele sistemului, atunci o interpretare imediata a unui arc (xi,xj) este urmatoarea: componenta xi influenteaza direct componenta xj. Daca nodurile au semnificatia de stari posibile ale unui sistem atunci un arc (x i,xj) semnifica faptul ca sistemul poate trece direct din starea xi in starea xj.In ambele cazuri se vede ca avem de-a face doar cu informatii despre legaturi directe; totusi, chiar daca o componenta xi nu influenteaza direct componenta xj ea o poate influenta prin intermediul altor componente, existand un sir de componente intermediare: x1 x2 ,, xk, fiecare influentand-o direct pe urmatoarea si xi direct pe x1 iar xk direct pe xj.Astfel, daca dintr-o stare xi nu se poate trece direct intr-o stare xj s-ar putea totusi in mai multe etape, prin alte stari intermediare. Deoarece gasirea acestor influente sau treceri posibile este de obicei foarte importanta iar pentru un sistem cu mii sau zeci de mii de componente acest lucru nu mai poate fi facut 'din ochi', este necesara formalizarea notiunii de 'influente' si 'treceri' posibile, nu neaparat directe. Acest lucru a si fost facut mai sus, deoarece este evident ca 'xi influenteaza xj' sau 'din starea xi se poate trece in starea xj' este echivalent cu existenta in graf a unui drum de la nodul xi la nodul xj.
In continuare vom da un algoritm prin care putem gasi toate drumurile dintr-un graf orientat cu un numar finit de noduri.Pasul 1. Se construieste matricea booleana a adiacentelor directe corespunzatoare grafului, notata cu A. In aceasta se afla,
evident, toate drumurile de lungime 1.Este interesant de vazut ce legatura exista intre aceasta matrice si drumurile de lungime 2. Fie doua noduri x i si
xj oarecare din graf. Existenta unui drum de lungime 2 intre ele presupune existenta unui nod xk, din graf, cu proprietatea ca exista atat arcul (xi,xk) cat si arcul (xi,xk). Pentru a vedea daca acesta exista, luam pe rand fiecare nod al grafului si verificam daca exista sau nu ambele arce ((xi,xk) si (xi,xk)). Aceasta este echivalent cu a verifica daca, in matricea booleana a adiacentelor directe, exista vreun indice k astfel incat elementul k al liniei i si elementul k al coloanei j sa fie ambele egale cu 1. Daca folosim operatiile algebrei booleene de adunare si inmultire:
0 1 0 1
0 0 1 0 0 01 1 1 1 0 1
atunci verificarile de mai sus sunt echivalente cu a verifica daca elementul de pe pozitia (i,j) din A2 este egal cu 1. Valoarea 1 spune doar ca exista cel putin un drum de lungime 2 de la x i la xj. Daca dorim sa vedem si cate sunt, vom folosi regulile de inmultire si adunare obisnuita.
De asemenea, se poate observa ca existenta unui drum de lungime 3 de la x i la xj presupune existenta unui nod xk astfel incat sa existe un drum de lungime 2 de la xi la xk si un arc de la xk la xj, care este echivalent cu a verifica daca exista vreun indice k astfel incat elementul k al liniei i din matricea A2 si elementul k al coloanei j din A sunt ambele egale cu 1 sau, mai simplu, daca elementul (i,j) din A3 este 1.
Din cele de mai sus se observa ca existenta drumurilor de lungime k este data de valorile matricei A k, daca s-au folosit regulile algebrei booleene si numarul lor este dat de Ak, daca s-au folosit regulile obisnuite.Pasul 2. Vom calcula succesiv puterile lui A pana la puterea An-1
Daca intre nodurile xi si xj exista un drum de lungime n atunci el va contine un numar de noduri mai mare sau egal nu n+1 si, cum in graf sunt doar n varfuri, este clar ca cel putin unul, sa zicem x k, va aparea de doua ori. Vom avea in acest caz un drum de la xi pana la prima aparitie a lui xk, si un drum de la ultima aparitie a lui xk la xj. Eliminand toate nodurile dintre prima aparitie a lui xk si ultima aparitie a sa vom obtine un drum de la x i la xj, in care xk apare o singura data. Aplicand acest procedeu pentru toate nodurile care apar de mai multe ori pe drum, vom obtine un drum de la x i la xj, in care fiecare nod apare o singura data (deci un drum elementar), care are evident cel mult n-1 arce. In concluzie, daca exista vreun drum de la x i la xj atunci exista si un drum elementar si, deci, va exista o putere a lui A, intre A1 si An-1, in care pozitia (i,j) este diferita de 0. Pentru deciderea existentei unui drum intre oricare doua noduri este suficienta, deci, calcularea doar a primelor n-1 puteri ale lui A. Pasul 3. Se calculeaza matricea D = A + A2 + + An-1
Daca ne intereseaza doar existenta drumurilor dintre noduri, nu si numarul lor, vom folosi inmultirea si adunarea booleana si conform observatiei de mai sus:
dij = In acest caz, observand ca:
A(A + I)n–2 = A + A2 + A3 + + An–1 = A + A2 + A3 + + An-1 = Drezulta ca e suficient sa calculam doar puterea n-2 a matricei A + I si apoi s-o inmultim cu A. Avantajul acestei metode, in ceea ce priveste economia de timp, este sustinut si de urmatoarea observatie: daca D contine toate perechile de arce intre care exista drum atunci:
23
D = (A + A2 + + An-1) + An + An+1 + + An+k = D oricare ar fi k 0 A(A + I)n–2+k = (A + A2 + + An-1) + An + An+1 + + An+k-1 = D = A(A + I)n–2
A(A + I)n–2+k = A(A + I)n–2 oricare ar fi k 0deci de la puterea k = n-2 toate matricile Ak sunt egale. Putem, deci, calcula direct orice putere a lui A+I mai mare sau egala cu n-1 (de exemplu calculand (A+I)2, (A+I)4, (A+I)8, , , r fiind prima putere a lui 2 pentru care 2r n-2).
Procedeul de mai sus nu asigura decat aflarea faptului daca exista sau nu drum intre doua noduri, eventual ce lungime are si cate sunt de aceasta lungime. Totusi, in problemele practice cel mai important este sa stim care sunt efectiv aceste drumuri. Deoarece toate drumurile pot fi descompuse in drumuri elementare si in problemele practice in general acestea sunt cele care intereseaza, pasii urmatori ai algoritmului vor fi dedicati gasirii lor.
Pentru gasirea acestora se foloseste reprezentarea grafului prin matricea latina de la cazul F.Pasul 4. Construim matricea latina L asociata grafului, unde:
lij =
si matricea , definita prin:
= numita matricea latina redusa.
Gasirea unui drum de lungime 2 de la xi la xj presupune gasirea unui nod cu proprietatea ca exista arcele (xi,xk) si (xk,xj) si memorarea vectorului (xi, xk, xj). Aceasta este echivalent cu a gasi un indice k astfel incat elementul de pe pozitia k a liniei i, din
matricea L, sa fie xi,xk si elementul de pe pozitia k al coloanei j, din matricea , sa fie xj. Vom inmulti deci matricea L cu
matricea , folosind insa niste reguli de calcul speciale, numite inmultire si adunare latina.Definitia 1: Se numeste alfabet o multime de semne numite simboluri sau litere unde I este o multime oarecare de
indici, finita sau nu.
Definitia 2: Se numeste cuvant un sir finit de simboluri notat .
Definitia 3: Se numeste inmultire latina o operatie definita pe multimea cuvintelor unui alfabet, notata ' ', astfel:
= (produsul a doua cuvinte se obtine prin concatenarea lor)
Inmultirea latina este asociativa, are ca element neutru cuvantul vid, nu e comutativa si un element este inversabil doar daca este cuvantul vid.
Definitia 3: Se numeste adunare latina o functie definita pe multimea cuvintelor unui alfabet cu valori in multimea
partilor multimi cuvintelor, notata ' ' astfel:
= (suma a doua cuvinte este multimea formata din cele doua cuvinte)
Pasul 5. Se calculeaza succesiv matricile:
L2 = L , L3 = L2 , ,Lk+1 = Lk folosind operatiile de inmultire si adunare latina, alfabetul fiind multimea nodurilor grafului, unde operatia de inmultire este usor modificata, produsul dintre doua elemente ale matricilor fiind 0, daca unul dintre ele este 0 sau au un nod comun si este produsul latin al lor, in caz contrar.
Din felul cum a fost construita, matricea Lk va contine toate drumurile elementare de lungime k. Cum un drum elementar poate avea cel mult n noduri (cate are graful cu totul) rezulta ca:
primele n-1 puteri ale lui L contin toate drumurile elementare din graf; puterile lui L mai mari sau egale cu n au toate elementele egale cu 0; matricea Ln-1 contine toate drumurile hamiltoniene din graf (daca exista).
24
Observatie: Deoarece obtinerea matricii D prin metoda de mai sus presupune un volum foarte mare de calcule (de exemplu, daca graful are 100 de noduri, ridicarea unei matrici de 100×100 la puterea 100) pentru obtinerea acesteia se poate aplica si urmatorul algoritm:
Pas 1. Se construieste matricea de adiacenta A;Pas 2. Pentru fiecare linie i se aduna boolean la aceasta toate liniile j
pentru care aij = 1.Pas 3. Se reia pasul 2 pana cand, dupa o aplicare a acestuia, matricea
ramane aceeasi (nu mai apare nici un 1)Ultima matrice obtinuta este matricea drumurilor D numita si matricea
conexiunilor totale.Aceasta metoda, desi mai simpla nu spune insa si care sunt aceste
drumuri, pentru gasirea lor aplicandu-se, de exemplu, inmultirea latina
5. Drumuri si circuite hamiltoniene
Una dintre cele mai cunoscute probleme economice este problema comis voiajorului. Comis voiajorul este un individ care trebuie sa prezinte s-au sa distribuie marfa comandata la o serie de centre distribuite in general neliniar pe o anumita zona teritoriala (localitatile dintr-un judet, magazinele dintr-un cartier, persoanele dintr-un sat etc). Daca numarul de obiective care trebuie vizitate este mare sau foarte mare iar timpul disponibil foarte limitat atunci devine vitala o asemenea organizare a trecerii pe la fiecare obiectiv incat sa se efectueze in timpul minim posibil. Acest timp minim se traduce prin drumul cel mai scurt, iar cel mai scurt drum este evident cel in care se trece pe la fiecare obiectiv o singura data. In plus, la sfarsit trebuie sa se afle in punctul initial, adica sediul firmei la care lucreaza.O reprezentare a regiunii aprovizionate, in care centrele pe la care se trece sunt vizualizate prin puncte iar caile de acces la acestea prin segmente de curbe, va fi evident un graf, problema reducandu-se la a gasi circuitul hamiltonian de lungime minima.In timp, s-au evidentiat o multitudine de probleme reductibile la gasirea unui drum (sau circuit) hamiltonian intr-un graf, cum ar fi:
1. Problema postasului (gasirea traseului cel mai scurt care trece pe la toate locuintele ce apartin de oficiul postal la care lucreaza acesta);
2. Problema adunarii deseurilor (cel mai scurt drum care trece pe la toate punctele de depozitate a deseurilor);3. Problema succesiunii operatiilor (executarea mai multor operatii pe o masina in acea ordine in care suma timpilor
consumati cu pregatirea masinii pentru trecerea de la o operatie la urmatoarea sa fie minim)4. Ordinea lipirii unor componente electronice pe o placa, etc;Determinarea drumurilor hamiltonieneProblema determinarii drumului (circuitului) hamiltonian de valoare
optima s-a dovedit deosebit de dificila, neexistand nici acum un algoritm care sa rezolve problema in timp polinomial si nici macar o metoda simpla prin care sa se decida daca intr-un graf dat exista sau nu drumuri hamiltoniene.
Exista insa mai multi algoritmi, care reusesc, intr-un caz sau altul, sa rezolve problema satisfacator si in timp util.
A. Algoritmul lui FoulkesPasul 1. Se scrie matricea booleana A asociata grafului G.Pasul 2. Se determina matricea D a drumurilor grafului G prin procedeul
expus la inceputul capitolului si apoi matricea M = I + D.Pasul 3. Se imparte multimea nodurilor grafului in submultimi disjuncte
astfel:1. Se considera in matricea M liniile pline (cu toate elementele 1). Nodurile
ce corespund liniilor pline cu 1 formeaza submultimea C1.2. Se elimina liniile si coloanele care corespund nodurilor din submultimea
stabilita.
25
3. Se reia rationamentul de la punctul 1 pe matricea redusa obtinuta la punctul 2 obtinandu-se urmatoarea submultime si in continuare toate celelalte pana se epuizeaza toate liniile matricei.
Pasul 4. Se construieste graful G' in care:1. Nodurile care formeaza o submultime sunt reprezentate prin
puncte in interiorul unui dreptunghi si intre acestea se traseaza arcele existente in graful initial G.
2. Se traseaza legaturile dintre submultimi. Ele sunt reprezentate prin arcele existente in graful initial G intre nodurile submultimii C1 si cele ale submultimii C2, intre nodurile submultimii C2 si cele ale submultimii C3 etc.
Pasul 5. Se gasesc drumurile hamiltonieneUn drum hamiltonian se gaseste plecand de la un varf din submultimea
C1, trecand prin toate varfurile acesteia cu un drum hamiltonian, din ultimul varf la care se ajunge in C1 trecand la un varf din C2, parcurgand in continuare un drum hamiltonian in a doua submultime si tot asa, trecand prin toate submultimile si parcurgand, deci, toate nodurile grafului initial, o singura data. Aplicand acest procedeu in toate modurile posibile se obtin toate drumurile hamiltoniene din graful initial G. (Observatie: poate sa nu existe nici un drum hamiltonian in graful G, caz in care algoritmul se opreste deoarece la un anumit pas nu mai exista nici o linie plina cu 1).
Observatie. Algoritmul lui Foulkes reduce gasirea drumurilor hamiltoniene in graful initial G (care in problemele practice este foarte mare) la gasirea mai multor drumuri hamiltoniene mai mici in componente tare conexe ale grafului. Daca un graf are o singura componenta tare conexa, algoritmul lui Foulkes nu este eficient, in acest caz trebuind aplicati alti algoritmi cum ar fi cel bazat pe inmultirea latina.
B. Algoritmul lui Chen pentru determinarea drumurilor hamiltoniene in grafuri fara circuite-tema referat
C. Algoritmul lui KaufmannPasul 1. Construim matricea latina L asociata grafului, unde:
lij =
Pasul 2. Construim matricea , definita prin:
= numita matricea latina redusa.Pasul 3. Se calculeaza succesiv matricile:
L2 = L , L3 = L2 , , Lk+1 = Lk ,folosind operatiile de inmultire si adunare latina, alfabetul fiind multimea nodurilor grafului, unde operatia de inmultire este usor modificata, produsul dintre doua elemente ale matricilor fiind 0, daca unul dintre ele este 0 sau au un nod comun, si este produsul latin al lor, in caz contrar.
Din felul cum a fost construita, matricea Lk va contine toate drumurile elementare de lungime k. Cum un drum elementar poate avea cel mult n noduri (cate are graful cu totul) rezulta ca:
primele n-1 puteri ale L contin toate drumurile elementare din graf; puterile lui L mai mari sau egale cu n au toate elementele egale cu 0; matricea Ln-1 contine toate drumurile hamiltoniene din graf.
26
Pasul 4. Daca se doresc si circuitele atunci se verifica pentru fiecare drum hamiltonian daca poate fi completat pana la un circuit (adica daca exista in graf arcul care uneste nodul final cu cel initial);
Pasul 5. Daca se doreste si drumul (sau circuitul) de valoare optima (maxima sau minima) se calculeaza suma valorilor pentru fiecare drum si/sau circuit si se alege cel cu valoarea optima.
In concluzie, metoda inmultirii latine (A. Kaufmann – J. Melgrange) determina toate drumurile elementare din graf, prin calcularea matricelor M(1) , M(2) , M(3) , …, M(n-1) .
In matricea M(n-1) se citesc drumurile hamiltoniene.Aceasta metoda a inmultirii latine (algoritmul lui Kaufmann) este utila,
mai ales, in cazul grafurilor tare conexe, unde algoritmul lui Foulkes nu este eficient. Totusi, metoda este greu de aplicat in grafuri cu un numar mare de noduri. In acest caz este preferabil sa se construiasca graful condensat, sa se determine drumurile hamiltoniene in fiecare in parte cu algoritmul lui Kaufmann si apoi, ca la algoritmul lui Foulkes, sa se caute drumurile hamiltoniene in graful initial.
D. Un algoritm bazat pe algoritmul ungar-tema referat6. Drumuri optime intr-un graf
In marea majoritate a problemelor care pot fi modelate prin grafuri nu ne intereseaza numai daca exista sau nu legaturi intre componentele reprezentate prin nodurile grafului ci si intensitatea acestora. Aceasta intensitate are semnificatia unei valori numerice (pozitive sau negative) asociate arcului corespunzator legaturii a carei intensitate o masoara.
In aplicatiile economice aceasta valoare poate fi: lungimea drumului dintre doua localitati; costul parcurgerii rutei reprezentate prin arcul corespunzator; durata parcurgerii rutei respective; cantitatea transportata pe ruta respectiva; capacitatea maxima a rutei respective; castigul realizat prin trecerea de la o stare la alta a sistemului; consum de energie pentru efectuarea trecerii respective; punctaj realizat etc.Una din problemele care poate aparea in aceste situatii este gasirea,
pentru o anumita pereche de noduri (sau mai multe perechi), a drumului optim intre acestea.
Pentru formalizarea problemei vom introduce notiunea de valoare a unui drum, care este egala cu suma valorilor arcelor care il compun. Vom nota in continuare valoarea unui arc (xi,xj) cu v(xi,xj) sau cu vij. In aceste conditii putem enunta problema drumului optim astfel:
'Dat un graf G = (X,U) si o functie care asociaza fiecarui arc o valoare reala, sa se gaseasca, pentru o pereche data de noduri, drumul (drumurile) de valoare optima (minima sau/si maxima) intre cele doua noduri si valoarea acestuia (acestora)'
Deoarece este vorba de gasirea minimului unei multimi de numere reale, prima intrebare care se pune este daca aceasta admite minim. Daca multimea nodurilor grafului este infinita atunci pot exista o infinitate de
27
drumuri elementare distincte intre cele doua noduri si multimea valorilor acestora poate avea orice forma (inchisa sau nu, marginita sau nu) devenind foarte greu de caracterizat cazurile cand minimul dorit exista. Deoarece totusi majoritatea covarsitoare a problemelor economice se modeleaza prin grafuri cu numar finit de noduri, ne vom limita in continuare doar la acestea.
Un numar finit de noduri n atrage dupa sine existenta unui numar finit de arce (cel mult n2 ) si a unui numar finit de drumuri elementare ( cel mult
nn! ). Deoarece oricarui drum d ii corespunde un drum elementar de(obtinut prin eliminarea tuturor subcircuitelor lui d) putem calcula valoarea oricarui drum ca suma intre valoarea drumului elementar corespunzator si valorile unor subcircuite ale sale, fiecare inmultita cu numarul de parcurgeri ale circuitului respectiv.
In concluzie, daca exista un circuit de valoare negativa inseamna ca exista drumuri de valoare oricat de mica (cele care contin acest circuit), obtinuta prin parcurgerea acestuia de oricate ori dorim) si, deci, multimea valorilor drumurilor este nemarginita inferior, neexistand drum de valoare minima. Daca exista un circuit de valoare pozitiva atunci exista drumuri de valoare oricat de mare si multimea valorilor drumurilor este nemarginita superior, neexistand drum de valoare maxima.
Daca nu exista circuite de valoare negativa atunci valoarea oricarui drum este mai mare sau egala cu a drumului elementar corespunzator, deci drumul de valoare minima (daca exista) va fi un drum elementar. Cum multimea drumurilor elementare este finita (si deci si multimea valorilor lor) va avea minorant si am lamurit problema compatibilitatii problemei. Analog, daca nu exista circuite de valoare pozitiva atunci valoarea oricarui drum este mai mica sau egala cu a drumului elementar corespunzator, deci drumul de valoare maxima (daca exista) va fi un drum elementar. Cum multimea drumurilor elementare este finita (si deci si multimea valorilor lor), va avea majorant.
Obs. 1. Daca in graf nu exista decat arce de valoare pozitiva atunci exista drum de valoare minima.
Obs. 1. Daca in graf nu exista decat arce de valoare negativa atunci exista drum de valoare maxima.
Obs. 1. Daca in graf nu exista circuite atunci exista si drum de valoare minima si drum de valoare maxima.
Deoarece din cele de mai sus se sesizeaza importanta existentei circuitelor intr-un graf vom da in continuare un algoritm de depistare a existentei circuitelor intr-un graf:Pasul 1. Se construieste multimea A formata din nodurile pentru care toate
arcele incidente sunt incidente spre interior ( noduri in care toate arcele 'intra' sau, altfel spus, noduri din care nu 'pleaca' nici un arc).
Pasul 2. Se gasesc toate nodurile care nu sunt din A pentru care toate arcele incidente au cealalta extremitate in A (noduri din care se poate 'ajunge' doar in A). Daca nu exista nici un astfel de arc se trece la pasul 4.
28
Pasul 3. Se adauga arcele gasite la pasul 2 la multimea A apoi se reia algoritmul de la pasul 2, pentru noua multime A.
Pasul 4. Daca A contine multimea tuturor nodurilor atunci graful nu contine circuite. Daca au ramas noduri in afara lui A atunci graful contine circuite.Algoritmi de gasire a drumului optim
Din cauza varietatii nelimitate a grafurilor posibile, nu exista un algoritm care sa rezolve orice problema in timp util, dar s-au elaborat o multime de algoritmi, fiecare fiind cel mai eficace in anumite cazuri. Acesti algoritmi pot fi grupati in cinci categorii:
1. Algoritmi prin calcul matricial (Bellman-Kalaba, I. Tomescu, Bellman-Schimbell);
2. Algoritmi prin ajustari succesive: (Ford);3. Algoritmi prin inductie (Dantzig);4. Algoritmi prin ordonare prealabila a varfurilor grafului;5. Algoritmi prin extindere selectiva (Dijkstra).1. Algoritmul lui Bellman - KalabaAlgoritmul se aplica in grafuri finite care nu au circuite de valoare
negativa (pentru o problema de minim) sau care nu au circuite de valoare pozitiva (intr-o problema de maxim) si gaseste drumurile de valoare minima (maxima) de la toate nodurile grafului la un nod oarecare, fixat. Daca dorim sa cunoastem drumurile de valoare minima (maxima) intre oricare doua noduri vom aplica algoritmul, pe rand, pentru fiecare nod al grafului.
Fie G = un graf orientat finit. Presupunem (fara a restrange generalitatea, ca am numerotat nodurile astfel incat nodul spre care cautam drumurile de valoare minima (maxima) de la celelalte noduri sa fie xn.Pasul 1. Se construieste matricea patratica M cu dimensiunea egala cu
numarul de noduri ale grafului ale carei elemente sunt:
mij = Pasul 2. Se adauga succesiv liniile Li la matricea M, elementele acestora
calculandu-se prin relatiile de recurenta:1. L1j = mjn j = 1,,n (prima linie este ultima coloana, transpusa, a
matricii M)
2. Lij = min (Li-1,j , (mjk + Li-1,k)) intr-o problema de minim
sau Lij = max (Li-1,j , (mjk + Li-1,k)) intr-o problema de maximPasul 3. Dupa calcularea fiecarei linii noi se compara elementele ei cu cele
ale precedentei: Daca Lij = Li-1,j pentru orice j = 1,,n atunci se opreste recurenta
si ultima linie calculata contine valorile minime ale drumurilor de la celelalte noduri la nodul xn.
29
Daca exista cel putin un indice j cu Lij Li-1,j se trece la calcularea noii linii Li+1
Pasul 4. Pentru gasirea drumului care da valoarea minima de la un nod xj la nodul xn se gasesc, incepand inapoi de la ultima linie, pe care s-au obtinut valorile finale, notata Lf, nodurile , , , care formeaza drumul cautat, unde = xj, = xn si fiecare alt indice ki+1 este cel pentru care s-a obtinut minimul(maximul) de pe pozitia ki al liniei Li.
Observatie: Pentru grafuri foarte mari, algoritmul necesita un volum mare de memorie, prin necesitatea memorarii matricei M, care este greu de manipulat. Chiar daca din cele n2 arce posibile graful ar avea doar un procent foarte mic matricea grafului va avea tot n2 pozitii de memorat si analizat.Exemplu: Presupunem dat graful orientat de mai jos, in care se dores
Într-un graf neorientat, nodurile cu gradul 00 se numesc noduri izolate, iar cele cu gradul 11 se numesc noduri terminale.Graf simplu, multigrafÎntre oricare două noduri ale unui graf simplu poate exista cel mult o muchie/arc. În caz contrar, structura de date se va numi multigraf. Într-un multigraf, muchiile cu aceeași pereche de extremități se numesc muchii paralele. În plus, muchiile cu extremități identice (de la un nod la el însuși), se numesc bucle.Aici apare o discuție, deoarece unii autori de specialitate consideră că doar multigrafurile (nu și grafurile) pot avea bucle, pe când ceilalți susțin contrariul. Preferabilă este prima variantă, pentru că altfel multe formule clasice legate de grafuri s-ar complica. De obicei se specifică în enunțul problemelor dacă graful poate avea bucle sau nu. Oricum, noi vom lucra doar cu grafuri simple.
30
Numărul maxim de muchii/arceNumărul maxim de muchii ale unui graf neorientat cu nn noduri este n(n−1)/2n(n−1)/2, pentru că, având la dispoziție nn noduri, se pot forma C2n=n(n−1)/2Cn2=n(n−1)/2 perechi neordonate, iar în cel mai fericit caz, pentru oricare două noduri xx și yy din VVexistă muchia [x,y][x,y]. Similar, numărul maxim de arce ale unui graf orientat cu nnnoduri este 2C2n=n(n−1)2Cn2=n(n−1), pentru că două noduri xx și yy pot contribui cu maxim două arce: (x,y)(x,y) și (y,x)(y,x).Numărul de grafuri orientate/neorientateDe aici mai putem deduce două formule: Numărul de grafuri neorientate cu nnnoduri este 2n(n−1)/22n(n−1)/2, pentru că între fiecare două noduri pot exista 00 sau 11muchii. Analog, numărul de grafuri orientate cu nn noduri este 4n(n−1)/24n(n−1)/2, pentru că între fiecare două noduri xx și yy pot exista arcul (x,y)(x,y), arcul (y,x)(y,x), ambele sau niciunul.Gradul unui nodÎntr-un graf neorientat, gradul unui nod reprezintă numărul de muchii incidente cu acesta, și se notează cu d(x)d(x). Într-un graf orientat, gradul interior al nodului xxse notează cu d−(x)d−(x) și este egal cu numărul de arce cu extremitatea finală xx, iar gradul exterior, notat cu d+(x)d+(x) este numărul arcelor cu extremitatea inițială xx.
31
32
Suma gradelor nodurilor unui graf neorientat este egală cu dublul numărului său de muchii, pentru că fiecare muchie contribuie cu câte o unitate la gradul a două noduri:
∑x∈Vd(x)=2|E|∑x∈Vd(x)=2|E|Atât suma gradelor interioare cât și suma gradelor exterioare ale nodurilor unui graf orientat sunt egale cu numărul de arce ale grafului, pentru că fiecare muchie contribuie cu câte o unitate la fiecare sumă:
∑x∈Vd−(x)=∑x∈Vd+(x)=|E|∑x∈Vd−(x)=∑x∈Vd+(x)=|E|Grafuri asociate unui grafFie graful G=(V,E)G=(V,E). Graful G′=(V,E′)G′=(V,E′), cu E′⊂EE′⊂E este un graf parțial al grafului GG. Se observă că acesta se poate obține prin eliminarea unor muchii/arce din graful inițial. Numărul grafurilor parțiale ale lui GG este 2|E|2|E| (pentru fiecare muchie avem două variante: o ștergem sau nu).Graful G′′=(V′′,E′′)G′′=(V′′,E′′) cu V′′⊂VV′′⊂V și E′′E′′ mulțimea tuturor muchiilor/arcelor din EE cu ambele extremități în V′′V′′ se numește subgraf al lui GG. Acesta poate fi obținut eliminând unele noduri din GG, împreună cu toate muchiile incidente la acestea. Numărul de subgrafuri ale lui GG este 2|V|−12|V|−1 (numărul submulțimilor lui VV, excluzând mulțimea vidă, deoarece graful nu poate avea 00 noduri).Un subgraf parțial este, după cum îi spune și numele, un subgraf din care s-au eliminat niște muchii.
I. Definitii II. Reprezentare grafuri III. Tipuri de grafuri IV. Algoritmi V. Grafuri ponderate
Definiție 1.2.1.1 Se numește graf neorientat o pereche ordonată de mulțimi (X, U), unde:
X este o mulțime finită și nevidă de elemente numite noduri; U este o mulțime de perechi neordonate de câte două elemente din X, perechi
numite muchii.Notații:Fie un graf neorientat G=(X, U). Se realizează următoarele notații:
se notează cu n numărul de noduri din graf (adică |X|=n); se notează cu m numărul de muchii din graf (adică |U|=m); dacă o muchie trece prin nodurile x, y ale grafului G, atunci muchia se notează
cu [x, y]. Pentru că perechile care formează mulţimea U sunt neordonate, muchia [x, y] este aceeaşi cu muchia [y, x];
33
o modalitate de notare a grafului este următoarea: G=(X, U), apoi enumererarea elementelor celor două mulţimi X, respectiv U.
Exemplu: G=(X, U), X={1, 2, 3, 4, 5, 6, 7}, U={[1, 2], [2, 3], [2, 4], [3, 4], [5, 6]}.
o altă modalitate de notare a grafului este notarea grafică, unde nodurile vor fi reprezentate prin puncte însoţite de numărul nodului, iar muchiile vor fi reprezentate prin linii drepte sau curbe între nodurile cu care sunt incidente.
Exemplu:
AdiancenţăDefiniţie 1.2.1.2 Fie un graf neorientat G=(X, U) şi u din U, cu u=[x, y]. Spunem în acest caz despre nodurile x şi y că sunt adiacente.
IncidenţăDefiniţie 1.2.1.3 Fie un graf neorientat G=(X, U) şi u din U, cu u=[x, y]. Spunem în acest caz despre muchia u şi nodul x că sunt incidente, la fel despre muchia u şi nodul y.
GradDefiniţie 1.2.1.4 Fie un graf neorientat G=(X, U) şi x din X. Se numeşte gradul
nodului x numărul muchiilor incidente cu nodul x.Gradul unui nod x se notează cu d(x).Definiţie 1.2.1.5 Fie un graf neorientat G=(X, U) şi x din X.
dacă d(x)=0, atunci nodul x se numeşte nod izolat; dacă d(x)=1, atunci nodul x se numeşte nod terminal.
Teoremă 1.2.1.6 Fie un graf neorientat G=(X, U) cu n noduri şi m muchii. Are loc următoarea egalitate: suma gradelor tuturor nodurilor este egală cu de două ori numărul muchiilor.
Demonstraţia este evidentă. Fiecare muchie de forma [xi, xj] (unde xi şi xj sunt noduri cu i, j din mulţimea {1, 2, …, n}), contribuie cu o unitate la gradul nodului xi şi cu o unitate la gradul nodului xj. Aşadar fiecare muchie din graf adaugă două unităţi la suma gradelor. Fiind m muchii, rezultă foarte clar că suma gradelor tuturor nodurilor este 2m.
Graf Parţial34
Definiţie 1.2.1.7 Fie un graf neorientat G=(X, U). Se numeşte graf parţial al grafului G un graf G1=(X, V) cu mulţimea V inclusă în mulţimea U. Altfel spus, un graf parţial G1 al lui G este chiar G sau se obţine din graful G păstrând toate nodurile şi eliminând anumite muchii.
Exemplu: Pentru graful G=(X, U) din figura 1.11, se construieşte alăturat graful parţial obţinut prin eliminarea muchiilor incidente cu nodul 4 (figura 1.12).
Figura 1.11 Figura 1.12
SubgrafDefiniţie 1.2.1.8 Fie un graf neorientat G=(X, U). Se numeşte subgraf al grafului G un graf G1=(Y, V) cu mulţimea Y inclusă în mulţimea V şi mulţimea V inclusă în mulţimea U, astfel încât V va conţine doar muchiile care au ambele extremităţi în Y. Altfel spus, un subgraf G1 al lui G este chiar G sau se obţine din graful G eliminând anumite noduri şi muchiile incidente cu acestea.Exemplu: Pentru graful G=(X, U) din figura 1.11, se construieşe în figura 1.13 subgraful obţnut prin eliminarea nodurilor 1 ş 6 precum ş a muchiilor incidente cu acestea.
Figura 1.11 Figura
1.13
Graf CompletDefiniţie 1.2.1.9 Fie un graf neorientat G=(X, U). Graful G se numeşte complet dacă
oricare două noduri distincte sunt adiacente.Un graf neorientat complet cu n noduri se notează Kn.Un exemplu de graf complet cu 5 noduri este prezentat în figura 1.14.
35
Figura 1.14
Teoremă 1.2.1.10 Fie un graf neorientat complet Kn. Acest graf are n*(n -1)/2 muchii.
Ne putem convinge uşor de adevărul afirmaţiei imaginând următorul procedeu de numărare a muchiilor. Pornim de la primul nod şi trasăm n-1 muchii. Apoi considerăm al doilea nod şi obţinem de asemenea n-1 muchii.
Deoarece procedeul se poate aplica pentru fiecare dintre cele n noduri se obţin n*(n-1) muchii.
În acest fel am numărat fiecare muchie de două ori, şi anume, de fiecare dată când am luat în considerare un capăt al ei. În consecinţă un graf complet cu n noduri are exact n*(n-1)/2 muchii.
Graf Bipartit CompletDefiniţie 1.2.1.11 Fie un graf neorientat G=(X, U). Graful G se numeşte bipartit dacă
există două mulţimi A şi B incluse în X astfel încât mulţimile A şi B nu au nici un punct comun; reuniunea mulţimilor A şi B o constituie mulţimea X; toate muchiile grafului au o extremitate în A şi cealaltă în B.
Figura 1.15Definiţie 1.2.1.12 Fie un graf neorientat G=(X, U). Graful G se numeşte bipartit
complet dacă este bipartit şi are în plus proprietatea că pentru orice nod x din A şi orice nod y din B există muchia [x, y].
Exemplu:
36
LanţDefiniţie 1.2.3.1 Fie un graf neorientat G=(X, U). Se numeşte lanţ al grafului G o
succesiune de noduri L=[x1, x2, ..., xk], unde x1, x2, ..., xkX, cu proprietatea că [x1, x2], [x2, x3], ..., [xk-1, xk]U (adică există muchiile [x1, x2], [x2, x3], ..., [xk-1, xk] în graful G).
Definiţe 1.2.3.2 Fie un graf neorientat G=(X, U) ş L=[x1, x2, ..., xk] un lanţal grafului G. x1 şi xk se numesc extremităţle lanţlui, iar număul muchiilor care intră în componenţa lanţului reprezintă lungimealanţului.
Exemplu: Pentru graful din figura 1.19 se pot distinge mai multe lanţuri printre careL1=[1, 2, 3, 5, 4, 8], L2=[1, 2, 3, 2], L3=[9, 3, 5, 4, 3, 2], L4=[6, 7, 3, 5, 4, 8]
Figura 1.19
Definiţie 1.2.3.3 Fie un graf neorientat G=(X, U) şi L=[x1, x2, ..., xk] un lanţ al grafului G. Dacă nodurile x1, x2, ..., xk sunt distincte două câte două, atunci lanţul se numeşte elementar. În caz contrar lanţul se numeşte ne-elementar.
Exemplu: Lanţurile L1 şi L4 din exemplul anterior sunt elementare. Lanţurile L2 şi L3 din exemplul anterior sunt ne-elementare.
Definiţie 1.2.3.4 Fie un graf neorientat G=(X, U) şi L=[x1, x2, ..., xk] un lanţ al grafului G. Dacă muchiile [x1, x2], [x2, x3], ..., [xk-1, xk] sunt distincte două câte două, atunci lanţul se numeşte simplu. În caz contrar lanţul se numeşte compus.
Exemplu: Lanţurile L1, L3, L4 din exemplul anterior sunt simple. Lanţul L2 din exemplul anterior este compus.
Observaţie: Orice lanţ elementar este simplu. Reciproca nu este valabilă (se poate întâmpla ca lanţul să fie simplu, dar să fie ne-elementar – vezi lanţul L3 din exemplul lanţurilor).
CicluDefiniţie 1.2.3.5 Fie un graf neorientat G=(X, U). Se numeşte ciclul al grafului G un
lanţ L=[x1, x2, ..., xk] simplu al grafului G cu proprietatea că x1=xk (primul şi ultimul nod coincid).
Exemplu: Pentru graful din figura 1.19 C1=[3, 4, 5, 3, 7, 6, 1, 2, 3], C2=[1, 2, 3, 7, 6, 1], C3=[3, 5, 4, 9, 3] sunt cicluri.
Figura 1.19
37
Definiţie 1.2.3.6 Fie un graf neorientat G=(X, U) şi C=[x1, x2, ..., xk] un ciclul al grafului G. Dacă toate nodurile cu excepţia primului şi a ultimului sunt distincte două câte două, atunci ciclul se numeşteelementar. În caz contrar se numeşte ne-elementar.
Exemplu: Ciclurile C2 şi C3 din exemplul anterior sunt cicluri elementare. Ciclul C1 din exemplul anterior este ciclul ne-elementar.
Observaţie: Orice lanţ elementar este simplu. Reciproca nu este valabilă (se poate
întâmpla ca lanţul să fie simplu, dar să fie ne-elementar – vezi lanţul L3 din exemplul lanţurilor).
ELEMENTE DE TEORIA GRAFURILOR
1. Noţiuni generale
În general, pentru situaţiile care necesită la rezolvare un oarecare efort mintal (şi un caz tipic este cel al celor din economie), se caută, în primul rând, o metodă de reprezentare a lor care să permită receptarea întregii probleme dintr-o privire (pe cât posibil) şi prin care să se evidenţieze cât mai clar toate aspectele acesteia.
În acest scop se folosesc imagini grafice gen diagrame, schiţe, grafice etc. O reprezentare dintre cele mai utilizate este cea prin grafuri. Acestea sunt utilizate în special pentru vizualizarea sistemelor şi situaţiilor complexe. În general, vom reprezenta componentele acestora prin puncte în plan iar relaţiile (legăturile, dependenţele, influenţele etc) dintre componente prin arce de curbă cu extremităţile în punctele corespunzătoare. Între două puncte pot exista unul sau mai multe segmente (în funcţie de câte relaţii dintre acestea, care ne interesează, există) iar segmentelor li se pot asocia sau nu orientări (după cum se influenţează cele două componente între ele), numere care să exprime intensitatea relaţiilor dintre componente etc.
Este evident, totuşi, că această metodă are limite, atât din punct de vedere uman (prea multe puncte şi segmente vor face desenul atât de complicat încât se va pierde chiar scopul pentru care a fost creat claritatea şi simplitatea reprezentării, aceasta� devenind neinteligibilă) cât şi din punct de vedere al tehnicii de calcul (un calculator nu poate "privi" un desen ca un om).
Din acest motiv, alături de expunerea naiv-intuitivă a ceea ce este un graf, dată mai sus, se impune atât o definiţie riguroasă cât şi alte modalităţi de reprezentare a acestora, adecvate în general rezolvărilor matematice.
38
Definiţia 1 Se numeşte multigraf un triplet G = (X, A, f) în care X şi A sunt
două mulţimi iar f este o funcţie, definită pe produsul vectorial al lui X cu el însuşi (X2 = XX), care ia valori în mulţimea părţilor mulţimii A (notată P(A))
Mulţimea X se numeşte mulţimea nodurilor multigrafului şi elementele sale se
numesc noduri (sau vârfuri) ale multigrafului, iar A reprezintă mulţimea relaţiilor (legăturilor) posibile între două noduri ale multigrafului.
Definiţia 2 Se numeşte graf orientat un multigraf în care mulţimea A are un
singur element: A = {a}. În acest caz mulţimea părţilor mulţimii A are doar două elemente: mulţimea
vidă şi întreaga mulţime A. Dacă unei perechi orientate (x i, xj) din X2 i se asociază prin funcţia f mulţimea A atunci spunem ca există arc de la nodul x i la nodul xj iar perechea (xi,xj) se va numi arcul (xi,xj). Nodul xi se numeşte nod iniţial sau extremitate iniţială a arcului (xi,xj) iar nodul xj se numeşte nod final sau extremitate finală a arcului (xi,xj). Arcul (xi,xj) este incident spre interior vârfului xj şi incident spre exterior vârfului xi. Dacă pentru un arc nodul iniţial coincide cu nodul final atunci acesta se numeşte buclă. Nodurile xi şi xj se vor numi adiacente dacă există cel puţin unul din arcele (xi,xj) şi (xj,xi).
Dacă unei perechi orientate (xi, xj) din X2 i se asociază prin funcţia f mulţimea vidă atunci spunem că nu există arc de la nodul xi la nodul xj.
Este evident că a cunoaşte un graf orientat este echivalent cu a cunoaşte vârfurile şi arcele sale. Din acest motiv putem defini un graf orientat prin perechea (X,U), unde X este mulţimea vârfurilor sale iar U mulţimea arcelor sale.
De asemenea, putem cunoaşte un graf orientat cunoscând mulţimea nodurilor şi, pentru fiecare nod, mulţimea arcelor incidente spre exterior. Din acest motiv putem defini un graf orientat ca o pereche (X,) unde X este perechea nodurilor iar este o funcţie definită pe X cu valori în mulţimea părţilor lui X, valoarea acesteia într-un nod xi, (xi) X fiind mulţimea nodurilor adiacente nodului xi, prin arce pentru care xi este extremitatea iniţială.
Definiţia 3 Se numeşte graf neorientat un multigraf în care mulţimea A are
un singur element iar funcţia f are proprietatea:f[(xi,xj)] = f[(xj,xi)] , oricare ar fi nodurile xi şi xj din X
În aceste condiţii, dacă f[(xi,xj)] = f[(xj,xi)] = A atunci perechea neorientată {xi,xj} este o muchie iar dacă f[(xi,xj)] = f[(xj,xi)] = spunem că nu există muchie între vârfurile xi şi xj.
Deoarece, în cele mai multe din cazurile practice care vor fi analizate în acest capitol, situaţia este modelată matematic printr-un graf orientat, vom folosi, pentru simplificarea expunerii, denumirea de graf în locul celei de graf orientat iar în cazul în care graful este neorientat vom specifica acest fapt la momentul respectiv.
39
2. Moduri de reprezentare ale unui graf
A. O primă modalitate de reprezentare este listarea efectivă a tuturor nodurilor
şi a arcelor sale.B. Putem reprezenta graful dând pentru fiecare nod mulţimea nodurilor cu care
formează arce în care el este pe prima poziţie.C. Putem reprezenta geometric graful, printr-un desen în plan, reprezentând
fiecare nod printr-un punct(cerculeţ) şi fiecare arc printr-un segment de curbă care are ca extremităţi nodurile arcului şi pe care este trecută o săgeată orientată de la nodul iniţial spre cel final.
D. Putem folosi o reprezentare geometrică în care nodurile sunt reprezentate de două ori, în două şiruri paralele, de la fiecare nod din unul din şiruri plecând săgeţi spre nodurile cu care formează arce în care el este pe prima poziţie, de pe al doilea şir (reprezentarea prin corespondenţă).
E. Un graf poate fi reprezentat printr-o matrice pătratică booleană, de dimensiune egală cu numărul de noduri, în care o poziţie a ij va fi 1 dacă există arcul (xi,xj) şi 0 în caz contrar, numită matricea adiacenţelor directe.
F. Un graf poate fi reprezentat printr-o matrice pătratică latină, de dimensiune egală cu numărul de noduri, în care pe o poziţie aij va fi xixj dacă există arcul (xi,xj) şi 0 în caz contrar.
Exemplu: Dacă în reprezentarea A avem graful G = (X,U), unde X = {x1, x2, x3, x4, x5, x6} şi U = {(x1,x1), (x1,x2), (x1,x4), (x1,x5), (x2,x3), (x2,x4), (x2,x6), (x3,x1), (x3,x2), (x4,x5), (x5,x2), (x6,x4)}, atunci în celelalte reprezentări vom avea:
B x1 {x1, x2, x4, x5} C
x2 {x3, x4, x6}x3 {x1, x2}x4 {x5}x5 {x2}x6 {x4}
D (reprezentarea prin corespondenţă)
x1 x2 x3 x4 x5 x6
40
x1 x2 x3 x4 x5 x6
x1 x2 x3 x4 x5 x6
x1 x1x1 x1x2 0 x1x4 x1x5 0x2 0 0 x2x3 x2x4 0 x2x6
x3 x3x1 x3x2 0 0 0 0x4 0 0 0 0 x4x5 0x5 0 x5x2 0 0 0 0x6 0 0 0 x6x4 0 0
x1 x2 x3 x4 x5 x6
x1 1 1 0 1 1 0x2 0 0 1 1 0 1x3 1 1 0 0 0 0x4 0 0 0 0 1 0x5 0 1 0 0 0 0x6 0 0 0 1 0 0
E F
3. Concepte de bază în teoria grafurilor
1. semigraf interior al unui nod xk: este mulţimea arcelor = {(xj,xk)/ (xj,xk) U} care sunt incidente spre interior nodului xk;
2. semigraf exterior al unui nod xk: este mulţimea arcelor = {(xk,xi)/ (xk,xi) U} care sunt incidente spre exterior nodului xk;
3. semigradul interior al unui nod xk: este numărul arcelor care sunt
incidente spre interior nodului xk = cardinalul lui şi se notează cu ;
41
4. semigradul exterior al unui nod xk: este numărul arcelor care sunt
incidente spre exterior nodului xk = cardinalul lui şi se notează cu ;
5. gradul unui nod xk: este suma semigradelor nodului xk: = + ;6. nod izolat: este un nod cu gradul 0;7. nod suspendat: este un nod cu gradul 1;8. arce adiacente: arce care au o extremitate comună;9. drum într-un graf: o mulţime ordonată de noduri ale grafului: (x1, x2, ...,
xk), cu proprietatea că există în graf toate arcele de forma (x i,xi+1) i = 1,...,k-1;
10. lungimea unui drum: este numărul arcelor care îl formează;11. drum elementar: un drum în care fiecare nod apare o singură dată;12. drum simplu: un drum în care fiecare arc apare o singură dată;13. putere de atingere a unui nod xi X în graful G: numărul de noduri la
care se poate ajunge din xi. Puterea de atingere se notează cu p(x i),
1 i n şi evident p(xi) .14. drum hamiltonian: un drum elementar care trece prin toate nodurile
grafului;15. drum eulerian: un drum simplu care conţine toate arcele grafului;16. lanţ: un drum în care arcele nu au neapărat acelaşi sens de parcurgere;17. circuit: un drum în care nodul iniţial coincide cu cel final;18. circuit elementar: un drum în care fiecare nod apare o singură dată, cu
excepţia celui final, care coincide cu cel iniţial;19. circuit simplu: un drum în care fiecare arc apare o singură dată;20. circuit hamiltonian: un circuit care trece prin toate nodurile grafului;21. ciclu: este un circuit în care arcele nu au neapărat acelaşi sens de
parcurgere;22. ciclu elementar: un ciclu în care fiecare nod apare o singură dată, cu
excepţia celui final, care coincide cu cel iniţial;23. ciclu simplu: un ciclu în care fiecare arc apare o singură dată;
Observaţie: Într-un graf neorientat noţiunile de drum şi lanţ sunt echivalente şi de asemenea cele de circuit şi ciclu.
24. graf parţial al unui graf G = (X,U): este un graf G'(X,U') cu U' U;25. subgraf al unui graf G = (X,): este un graf G'(X',') unde X' X şi '(xi)
= (xi) X' pentru orice xi X';26. graf redus al unui graf G = (X,U): este un graf G*(X*,U*) unde X* este
formată din mulţimile unei partiţii de mulţimi nevide ale lui X, iar ( , )
există doar dacă i j şi există cel puţin un arc în U, de la un nod din la
un nod din .27. graf tare conex: este un graf în care între oricare două noduri există cel
puţin un drum;42
28. graf simplu conex: este un graf în care între oricare două noduri există cel puţin un lanţ;
Observaţie: Pentru grafuri neorientat noţiunile de tare conex şi simplu conex sunt echivalente, graful numindu-se doar conex;29. componentă tare conexă a unui graf G = (X,U): este un subgraf al lui G
care este tare conex şi nu este subgraful nici unui alt subgraf tare conex al lui G (altfel spus, între oricare două noduri din componentă există cel puţin un drum şi nu mai există nici un nod în afara componentei legat printr-un drum de un nod al componentei).
4. Găsirea drumurilor într-un graf orientat
Dacă privim graful ca imagine a unui sistem, nodurile reprezentând componentele
sistemului, atunci o interpretare imediată a unui arc (xi,xj) este că, componenta xi influenţează direct componenta xj. Dacă nodurile au semnificaţia de stări posibile ale unui sistem atunci un arc (xi,xj) semnifică faptul că sistemul poate trece direct din starea xi în starea xj. În ambele cazuri se vede că avem de-a face doar cu informaţii despre legături directe; totuşi, chiar dacă o componentă xi nu influenţează direct componenta xj ea o poate influenţa prin intermediul altor componente, existând un şir de componente intermediare: x1 x2 ,..., xk, fiecare influenţând-o direct pe următoarea şi xi direct pe x1 iar xk direct pe xj. Astfel, dacă dintr-o stare xi nu se poate trece direct într-o stare xj s-ar putea totuşi în mai multe etape, prin alte stări intermediare. Deoarece găsirea acestor influenţe sau treceri posibile este de obicei foarte importantă iar pentru un sistem cu mii sau zeci de mii de componente acest lucru nu mai poate fi făcut "din ochi", este necesară formalizarea noţiunii de "influenţe" şi "treceri" posibile, nu neapărat directe. Acest lucru a şi fost făcut mai sus, deoarece este evident că "xi influenţează xj" sau "din starea xi se poate trece în starea xj" este echivalent cu existenţa în graf a unui drum de la nodul xi la nodul xj.
În continuare vom da un algoritm prin care putem găsi toate drumurile dintr-un graf orientat cu un număr finit de noduri. Pasul 1. Se construieşte matricea booleană a adiacenţelor directe corespunzătoare
grafului, notată cu A. În aceasta se află, evident, toate drumurile de lungime 1.
Este interesant de văzut ce legătură există între această matrice şi drumurile de
lungime 2. Fie două noduri xi şi xj oarecare din graf. Existenţa unui drum de lungime 2 între ele presupune existenţa unui nod xk, din graf, cu proprietatea că există atât arcul (xi,xk) cât şi arcul (xi,xk). Pentru a vedea dacă acesta există, luăm pe rând fiecare nod al grafului şi verificăm dacă există sau nu ambele arce ((x i,xk) şi (xi,xk)). Aceasta este echivalent cu a verifica dacă, în matricea booleană a adiacenţelor directe, există vreun indice k astfel încât elementul k al liniei i şi elementul k al coloanei j să fie ambele egale cu 1. Dacă folosim operaţiile algebrei booleene de adunare şi înmulţire:
0 1 0 10 0 1 0 0 01 1 1 1 0 1
43
atunci verificările de mai sus sunt echivalente cu a verifica dacă elementul de pe poziţia (i,j) din A2 este egal cu 1. Valoarea 1 spune doar că există cel puţin un drum de lungime 2 de la xi la xj. Dacă dorim să vedem şi câte sunt, vom folosi regulile de înmulţire şi adunare obişnuită.
De asemenea, se poate observa că existenţa unui drum de lungime 3 de la x i la xj presupune existenţa unui nod xk astfel încât să existe un drum de lungime 2 de la xi la xk şi un arc de la xk la xj, care este echivalent cu a verifica dacă există vreun indice k astfel încât elementul k al liniei i din matricea A 2 şi elementul k al coloanei j din A sunt ambele egale cu 1 sau, mai simplu, dacă elementul (i,j) din A3 este 1.
Din cele de mai sus se observă că existenţa drumurilor de lungime k este dată de valorile matricei Ak, dacă s-au folosit regulile algebrei booleene şi numărul lor este dat de Ak, dacă s-au folosit regulile obişnuite.
Pasul 2. Vom calcula succesiv puterile lui A până la puterea An-1
Dacă între nodurile xi şi xj există un drum de lungime n atunci el va conţine
un număr de noduri mai mare sau egal nu n+1 şi, cum în graf sunt doar n vârfuri, este clar că cel puţin unul, să zicem xk, va apărea de două ori. Vom avea în acest caz un drum de la xi până la prima apariţie a lui xk, şi un drum de la ultima apariţie a lui xk la xj. Eliminând toate nodurile dintre prima apariţie a lui xk şi ultima apariţie a sa vom obţine un drum de la xi la xj, în care xk apare o singură dată. Aplicând acest procedeu pentru toate nodurile care apar de mai multe ori pe drum, vom obţine un drum de la xi la xj, în care fiecare nod apare o singură dată (deci un drum elementar), care are evident cel mult n-1 arce. În concluzie, dacă există vreun drum de la x i la xj atunci există şi un drum elementar şi, deci, va exista o putere a lui A, între A 1 şi An-1, în care poziţia (i,j) este diferită de 0. Pentru deciderea existenţei unui drum între oricare două noduri este suficientă, deci, calcularea doar a primelor n-1 puteri ale lui A. Pasul 3. Se calculează matricea D = A + A2 + ... + An-1
Dacă ne interesează doar existenţa drumurilor dintre noduri, nu şi numărul lor,
vom folosi înmulţirea şi adunarea booleană şi conform observaţiei de mai sus:
dij =
În acest caz, observând că:
A(A + I)n2� = A + A2 + A3 + ... + An1� = A + A2 + A3 + ... + An-
1 = D
44
rezultă că e suficient să calculăm doar puterea n-2 a matricei A + I şi apoi s-o înmulţim cu A. Avantajul acestei metode, în ceea ce priveşte economia de timp, este susţinut şi de următoarea observaţie: dacă D conţine toate perechile de arce între care există drum atunci:
D = (A + A2 + ... + An-1) + An + An+1 + ... + An+k = D oricare ar fi k 0 A(A + I)n2+k� = (A + A2 + ... + An-1) + An + An+1 + ... + An+k-1 = D = A(A + I)n2�
A(A + I)n2+k� = A(A + I)n2� oricare ar fi k 0
deci de la puterea k = n-2 toate matricile Ak sunt egale. Putem, deci, calcula direct orice putere a
lui A+I mai mare sau egală cu n-1 (de exemplu calculând (A+I)2, (A+I)4, (A+I)8, ..., , r fiind prima putere a lui 2 pentru care 2r n-2).
Procedeul de mai sus nu asigură decât aflarea faptului dacă există sau nu drum între două noduri, eventual ce lungime are şi câte sunt de această lungime. Totuşi, în problemele practice cel mai important este să ştim care sunt efectiv aceste drumuri. Deoarece toate drumurile pot fi descompuse în drumuri elementare şi în problemele practice în general acestea sunt cele care interesează, paşii următori ai algoritmului vor fi dedicaţi găsirii lor. Pentru găsirea acestora se foloseşte reprezentarea grafului prin matricea latină de la cazul F.
Pasul 4. Construim matricea latină L asociată grafului, unde:
lij = şi matricea , definită prin:
= numită matricea latină redusă.
Găsirea unui drum de lungime 2 de la xi la xj presupune găsirea unui nod cu proprietatea că există arcele (xi,xk) şi (xk,xj) şi memorarea vectorului (xi, xk, xj). Aceasta este echivalent cu a găsi un indice k astfel încât elementul de pe poziţia k a liniei i, din matricea L, să fie xi,xk şi elementul de pe poziţia k al coloanei j, din matricea , să fie xj. Vom înmulţi deci matricea L cu matricea , folosind însă nişte reguli de calcul speciale, numite înmulţire şi adunare latină.
Definiţia 1: Se numeşte alfabet o mulţime de semne
numite simboluri sau litere {si/iI} unde I este o mulţime oarecare de indici, finită sau nu.
Definiţia 2: Se numeşte cuvânt un şir finit de simboluri notat .Definiţia 3: Se numeşte înmulţire latină o operaţie definită pe mulţimea
cuvintelor unui alfabet, notată " ", astfel:
= (produsul a două cuvinte se obţine prin concatenarea lor)
45
Înmulţirea latină este asociativă, are ca element neutru cuvântul vid, nu e comutativă şi un element este inversabil doar dacă este cuvântul vid.
Definiţia 3: Se numeşte adunare latină o funcţie definită pe mulţimea cuvintelor unui alfabet cu valori în mulţimea parţilor mulţimi cuvintelor, notată " " astfel:
= (suma a două cuvinte este mulţimea formată din cele două cuvinte)
Pasul 5. Se calculează succesiv matricile:
L2 = L , L3 = L2 , ... ,Lk+1 = Lk folosind operaţiile de înmulţire şi adunare latină, alfabetul fiind mulţimea nodurilor grafului, unde operaţia de înmulţire este uşor modificată, produsul dintre două elemente ale matricilor fiind 0, dacă unul dintre ele este 0 sau au un nod comun şi este produsul latin al lor, în caz contrar.
Din felul cum a fost construită, matricea Lk va conţine toate drumurile elementare de lungime k. Cum un drum elementar poate avea cel mult n noduri (câte are graful cu totul) rezultă că:
primele n-1 puteri ale lui L conţin toate drumurile elementare din graf; puterile lui L mai mari sau egale cu n au toate elementele egale cu 0; matricea Ln-1 conţine toate drumurile hamiltoniene din graf (dacă există). Observaţie: Deoarece obţinerea matricii D prin metoda de mai sus presupune un volum
foarte mare de calcule (de exemplu, dacă graful are 100 de noduri, ridicarea unei matrici de 100×100 la puterea 100) pentru obţinerea acesteia se poate aplica şi următorul algoritm:
Pas 1. Se construieşte matricea de adiacenţă A;Pas 2. Pentru fiecare linie i se adună boolean la aceasta toate liniile j pentru care aij = 1.Pas 3. Se reia pasul 2 până când, după o aplicare a acestuia, matricea rămâne aceeaşi (nu
mai apare nici un 1)Ultima matrice obţinută este matricea drumurilor D numită şi matricea conexiunilor
totale.Această metodă, deşi mai simplă nu spune însă şi care sunt aceste drumuri, pentru găsirea
lor aplicându-se, de exemplu, înmulţirea latină
5. ARBORI. Problema arborelui de valoare optimă
În acest subcapitol grafurile vor fi considerate neorientate.
5.1. Noţiunea de arbore46
Un arbore este un graf neorientat, finit, conex şi fără cicluri. Grafurile din fig.
4.1. sunt arbori.
Studiul arborilor este justificat de existenţa în practică a unui număr mare de probleme care pot fi modelate prin arbori. Dintre acestea amintim:
1. construirea unor reţele de aprovizionare cu apă potabilă (sau cu energie
electrică sau termică etc) a unor puncte de consum, de la un punct central;2. construirea unor căi de acces între mai multe puncte izolate;3. desfăşurarea unui joc strategic;4. luarea deciziilor în mai multe etape (arbori decizionali);5. evoluţii posibile ale unui sistem pornind de la o stare iniţială;6. construirea unei reţele telefonice radiale, a unei reţele de relee electrice;7. legarea într-o reţea a unui număr mare de calculatoare;8. organigramele întreprinderilor;9. studiul circuitelor electrice în electrotehnică (grafe de fluenţă etc);
47
10. schemele bloc ale programelor pentru calculatoare etc.
În toate problemele de mai sus se doreşte ca, dintre muchiile unui graf neorientat, să se extragă arborele optim din mulţimea tuturor arborilor care pot fi extraşi din graful dat.
Deoarece definiţia arborelui este dificil de aplicat pentru deciderea faptului că un graf este arbore sau nu (şi în special sunt greu de verificat conexitatea şi mai ales existenţa ciclurilor) există mai multe caracterizări posibile ale unui arbore, acestea fiind date de teorema de mai jos:
Teoremă. Dacă H este un graf neorientat finit, atunci următoarele afirmaţii sunt
echivalente:
1) H este arbore;2) H nu conţine cicluri şi, dacă se unesc printr-o muchie două noduri
neadiacente, se formează un ciclu (şi numai unul). Arborele este, deci, pentru o mulţime de noduri dată, graful cu numărul maxim de arce astfel încât să se păstreze proprietatea că nu are cicluri);
3) H este conex şi dacă i se suprimă o muchie se creează două componente conexe (arborele este graful conex cu numărul minim de arce);
4) H este conex şi are n-1 muchii;5) H este fără cicluri şi are n-1 muchii;6) Orice pereche de noduri este legată printr-un lanţ şi numai unul.
Demonstraţie :
1) 2). între cele două noduri adiacente noii muchii introduse exista deja un drum în fostul graf. Acest drum, împreună cu noul arc va forma evident un ciclu şi afirmaţia 2) a fost demonstrată.
2)3). Pentru oricare două vârfuri neunite printr-o muchie, adăugând muchia dintre cele două vârfuri s-ar crea, conform ipotezei, un ciclu care conţine această muchie, deci două drumuri între cele două noduri, din care unul nu conţine noua muchie, adică în graful iniţial exista un drum între cele două noduri. Dacă nu există cicluri înseamnă că între oricare două noduri există un singur drum. Pentru două noduri unite printr-o muchie, aceasta este chiar drumul corespunzător celor două noduri. Dacă suprimăm această muchie între cele două noduri nu va mai exista nici un drum, formându-se două componente conexe.
3)4). Demonstraţia se face prin inducţie după n = numărul de noduri ale grafului. Pentru n=2 este evident. Presupunem afirmaţia adevărată pentru toate grafurile cu cel mult n noduri. Dacă graful are n+1 noduri, prin suprimarea unei muchii se formează două componente conexe fiecare având cel mult n noduri (n1 n, n2 n şi n1 + n2 = n+1) şi deci au n1 1 respectiv n� 2 1 muchii. În concluzie�
48
graful iniţial a avut (n1 1) + (n� 2 1) +1 = n� 1 + n2 1= (n+1)-1 muchii, ceea ce� era de demonstrat.
4)5). Dacă ar avea un ciclu atunci prin suprimarea unui arc al acestuia ar rămâne de asemenea conex. Eliminăm acest arc apoi repetăm procedeul pentru graful parţial rămas şi tot aşa până când nu mai rămâne nici un ciclu. În acest moment graful rămas este conex şi nu are cicluri deci este arbore şi deci are n-1 arce, în contradicţie cu faptul că el avea n-1 arce înainte de a începe suprimarea arcelor;
5)6). Dacă între două noduri ar exista două drumuri atunci acestea ar forma la un loc un ciclu. Deci între 2 noduri este cel mult un drum. Dacă între două noduri nu ar exista nici un drum ar fi cel puţin două componente conexe în graf, fiecare fiind arbore (pentru că nu există cicluri) şi deci fiecare ar avea un număr de arce cu 1 mai mic decât numărul de noduri. Făcând adunarea, ar rezulta că în graf sunt strict mai puţin de n-1 arce.
6)1). Dacă H ar avea un ciclu, între două noduri ale acestuia ar exista două lanţuri, în contradicţie cu ipoteza.
Presupunem că avem un graf pentru care am verificat deja dacă este conex.
Dacă nu este atunci acesta, evident, nu are nici un graf parţial care să fie arbore.Presupunem de asemenea că fiecărei muchii îi este asociată o valoare reală. 5.2. Algoritmi pentru găsirea arborelui de valoare optimă Vom da mai jos trei algoritmi pentru determinarea unui graf parţial al grafului,
care să fie arbore şi pentru care suma valorilor arcelor sale să fie minimă (sau maximă).
Toţi algoritmii descrişi în continuare extrag arborele prin colectarea una câte una a muchiilor acestuia.
A. Algoritmul lui Kruskal
Pasul 1. Dintre toate muchiile grafului se alege muchia de valoare minimă (maximă).
Dacă minimul este multiplu se alege la întâmplare una din muchiile respective. Deoarece acest "la întâmplare" trebuie cumva tradus în limbajul calculatorului, în cazul implementării unui program bazat pe acest algoritm, vom perturba din start valorile muchiilor, la k muchii cu aceiaşi valoare V adunând respectiv valorile , 2, ... , k, unde este foarte mic (în orice caz, k mai mic decât diferenţa dintre valoarea acestor arce si valoarea imediat superioară a unui arc), pozitiv.
Pasul 2. Dintre toate muchiile rămase, se alege cea de valoare minimă (maximă);Pasul 3. Dintre toate muchiile rămase, se alege cea de valoare minimă (maximă),
astfel încât să nu se formeze cicluri cu cele deja alese;Pasul 4. Se reia algoritmul de la pasul 3 până se colectează n-1 muchii.
49
Deşi s-a demonstrat că algoritmul găseşte întotdeauna arborele optim, el are
dezavantajul că este foarte laborios (de fiecare dată trebuie calculat minimul unei mulţimi mari sau foarte mari există situaţii în practică în care graful are sute de mii de� arce) şi, în plus, trebuie aplicat un algoritm special ca să respectăm condiţia de a nu se forma cicluri, la alegerea unui nou arc.
O metodă posibilă este ca, după adăugarea fiecărui arc, să se împartă graful în componente conexe şi să alegem apoi un arc care nu are ambele extremităţile în aceeaşi componentă conexă.
De asemenea este clar că, în cazul existenţei arcelor de valori egale, deoarece se alege la întâmplare, există mai multe variante de evoluţie a alegerii arcelor. Totuşi, cu toate că pot fi mai multe grafuri la care se poate ajunge prin acest algoritm, ele vor avea toate aceeaşi valoare (minima (sau maxima) posibilă).
B. Algoritmul lui Sollin
Pasul 1. Pentru fiecare nod se alege muchia adiacentă de valoare minimă (maximă).Pasul 2. Se evidenţiază componentele conexe, existente în graful parţial format din
arcele alese până în acest moment.Pasul 3. Pentru fiecare componentă conexă se alege muchia adiacentă de valoare
minimă (maximă). Prin muchie adiacentă unei componente conexe înţelegem o muchie care are o singură extremitate printre nodurile componentei respective.
Pasul 4. Se reia algoritmul de la pasul 2 până rămâne o singură componentă conexă. Aceasta este arborele optim căutat.
Acest algoritm asigură de asemenea găsirea arborelui optim, necesită mult mai
puţine calcule (la fiecare alegere se calculează minimul doar pentru muchiile adiacente unui singur nod), evită automat formarea ciclurilor, dar, pentru grafuri foarte mari, la un moment dat pot exista atât de multe componente conexe care trebuie memorate succesiv, încât calculul devine greoi sau, pe calculator, depăşeşte posibilităţile de memorare ale calculatorului.
C. O variantă a algoritmului lui Kruskal
Pasul 1. Dintre toate muchiile grafului se alege cea de valoare minimă (maximă);Pasul 2. Dintre toate muchiile adiacente componentei conexe formată din arcele alese
până în acest moment, se alege cea de valoare minimă (maximă);Pasul 3. Se reia pasul 2 până se colecţionează n-1 muchii.
50
Algoritmul are toate avantajele algoritmului lui Sollin şi, în plus, lucrează cu o singură componentă conexă, fiind mult mai uşor de implementat pe calculator şi mult mai rapid în execuţie.
Exemplu: Administraţia unei localităţi montane a hotărât construirea unor linii
de teleferic care să lege oraşul de cele 8 puncte turistice importante din jurul acestuia. În urma unui studiu au fost puse în evidenţa toate posibilităţile şi costurile de conectare a obiectivele turistice între ele şi cu oraşul, acestea fiind prezentate în figura 4.2.
Se cere găsirea variantei de construcţie de cost minim, care să asigure accesul din oraş la oricare din obiectivele turistice.
Rezolvare
Condiţia de cost minim implică două obiective:1. Să se construiască minimul de arce necesare;2. Să se construiască cele mai ieftine legături.
Referitor la numărul de arce necesar, facem observaţia că, dacă din oraş se va putea ajunge la orice obiectiv turistic, atunci se va putea ajunge şi de la orice staţiune la oricare alta (trecând prin oraş), deci trebuie ca arcele alese pentru construcţie să formeze la un loc un graf conex.
În concluzie, căutăm un graf parţial conex cu un număr minim de arce, adică un arbore. În plus, suma costurilor arcelor sale trebuie să fie minimă. Vom aplica pe rând cei trei algoritmi pentru găsirea acestuia:
51
A. Kruskal La primul pas poate fi ales unul din arcele OP3 sau OP7, ele având valoarea
minimă 2. Putem alege oricum primul arc dintre cele două pentru că la al doilea pas va fi ales celălalt.
La pasul trei poate fi ales unul din arcele OP5, OP6 sau P1P6 care au valoarea minimă 3. Nici în acest caz nu are vre-o importanţă ordinea alegerii, deoarece pot fi alese succesiv toate trei fără a se forma nici un ciclu.
Al şaselea arc poate fi ales dintre arcele P4P5 şi P1P2, care au valoarea minimă 4. Nici în acest caz nu are vre-o importanţă ordinea alegerii, deoarece pot fi alese succesiv ambele, fără a se forma nici un ciclu.
Următoarea valoare disponibilă a unui arc este 5, dar arcul opt nu poate fi ales dintre arcele OP1, P6P7, deşi au valoarea minimă 5. Arcul OP1 nu poate fi ales deoarece s-ar forma ciclul OP1P6, iar P6P7 ar duce la ciclul OP6P7. Următoarea valoare minimă este 6, pentru arcul P5P7 dar nu poate fi ales deoarece se formează ciclul OP5P7.
Valoarea următoare, 7, o au arcele OP4, P2P3 şi P5P8. OP4 nu poate fi ales deoarece s-ar forma ciclul OP5P4. Arcul P2P3 nu poate fi ales deoarece s-ar forma ciclul OP6P1P2P3. Arcul P5P8 nu formează nici un ciclu şi el va fi al optulea arc ales. În acest caz, deoarece s-au adunat 8 arce într-un graf cu 9 noduri, am obţinut graful căutat.
Acest arbore este reprezentat în figura 4.3.
B. Sollin
52
Vom alege: pentru nodul O arcul OP3
pentru nodul P1 arcul P1P6
pentru nodul P2 arcul P1P2
pentru nodul P3 arcul OP3
pentru nodul P4 arcul P4P5
pentru nodul P5 arcul OP5
pentru nodul P6 arcul P1P6
pentru nodul P7 arcul OP7
pentru nodul P8 arcul P5P8
Rezultă graful parţial:
După cum se vede, s-au format două componente conexe: C1 = {P1,P2,P6}C2 = {O,P3,P4,P5,P7,P8}.
Vom alege: pentru C1 arcul OP6
pentru C2 arcul OP6
şi obţinem o singură componentă conexă, care este arborele căutat.
C. Varianta algoritmului lui Kruskal Succesiunea alegerii arcelor va fi:
1 OP3
2 OP7
3 OP6
4 OP5
5 P1P6
53
6 P1P2
7 P4P5
8 P5P8
6. Cuplajul a două mulţimi disjuncte Probleme de afectare (de
repartiţie) În practica economică sunt foarte des întâlnite probleme în care se doreşte
asocierea optimă a elementelor unei mulţimi X = {x1, x2, ... , xn} cu elementele unei alte mulţimi Y = {y1, y2, ... , ym} în condiţiile unor limitări existente (şi cunoscute) ale posibilităţilor de asociere.
În general, fiecare asociere posibilă xi yj aduce un anumit efect aij (profit, cost etc) care poate fi calculat şi vom presupune că este cunoscut.
Limitările asupra asocierilor se traduc de obicei prin faptul că:
1. Un element xi poate fi asociat doar cu anumite elemente din Y şi reciproc;
2. La sfârşit, fiecărui element din X i s-a asociat cel mult un element din Y şi reciproc.
Asocierea optimă presupune, de obicei, două obiective:
1. Să se facă maximul de asocieri;2. Suma efectelor asocierilor să fie maximă (sau minimă, în funcţie de
semnificaţia acestora). Reprezentarea geometrică a situaţiei de mai sus este un graf de forma:
54
numit graf bipartit.
Definiţia 1: Se numeşte graf bipartit un graf G = (X, U) în care mulţimea nodurilor poate fi împărţită în două mulţimi disjuncte A şi B astfel încât orice arc are extremitatea iniţială în A şi cea finală în B.
Definiţia 2: Se numeşte cuplaj al unui graf bipartit o submulţime de arce
W U cu proprietatea că nu există două arce adiacente (sau altfel spus, pentru orice nod există cel mult un arc incident acestuia).
Definiţia 3: Se numeşte cuplaj maxim un cuplaj cu proprietatea că orice arc
care nu face parte din cuplaj este adiacent cu un arc din cuplaj ( orice arc am adăuga, nu mai rămâne cuplaj nu există nici un cuplaj în care să se includă strict conţine numărul maxim de arce neadiacente)
Este evident că numărul de arce ale unui cuplaj este mai mic sau egal cu numărul de elemente din fiecare din mulţimile A şi B ( min (A,B). Este interesant de văzut însă cât de mare este el efectiv şi în ce condiţii este egal chiar cu min (A,B).
Referitor la prima întrebare, în 1931 König a demonstrat o teoremă care permite stabilirea numărului de arce ale unui cuplaj maxim:
Teoremă: Numărul maxim de arce ale unui cuplaj într-un graf bipartit G =
(AB, ) este egal cu În ceea ce priveşte a doua problemă, observăm mai întâi că putem presupune că
întotdeauna AB, în caz contrar inversând sensul tuturor arcelor grafului, problema rămânând aceeaşi.
În acest caz:
= A � A = 0 = 0
= 0 oricare ar fi C Asau altfel spus, pentru orice submulţime C a lui A, mulţimea nodurilor atinse de arce care pleacă din nodurile sale, adică (C), are cel puţin atâtea elemente cât C.
De exemplu, la repartizarea angajaţilor pe posturi, fiecare angajat poate obţine un post dorit dacă şi numai dacă oricare ar fi mulţimea de r angajaţi există cel puţin r posturi diferite din care pot alege.
Presupunem, în continuare, că s-a asociat fiecărui arc (xi,xj) o valoare vij. Definiţia 4: Se numeşte valoare a unui cuplaj suma valorilor arcelor care îl
formează.55
În acest moment putem spune că determinarea unei asocieri optime a
mulţimilor X şi Y de la început este echivalentă matematic cu determinarea unui cuplaj maxim de valoare optimă (minimă sau maximă) în graful bipartit asociat.
Dintre problemele întâlnite în practica economică, ce se reduc matematic la găsirea unui cuplaj maxim de valoare optimă, amintim:
1. Problema repartizării muncitorilor unei secţii la utilajele acesteia în funcţie
de pregătirea şi preferinţele muncitorilor, complexitatea maşinilor etc;2. transferarea unor informaţii într-un grup;3. Repartizarea angajaţilor pe posturi;4. Formarea grupelor de lucru după afinităţile dintre membrii colectivului. În 1955, bazându-se pe teorema lui König, H.W. Kuhn a elaborat un algoritm,
cunoscut în literatura de specialitate sub denumirea de algoritmul ungar, cu ajutorul căruia se poate determina un cuplaj maxim de valoare minimă într-un graf bipartit pentru care A=B= n.
El se bazează pe observaţia că, dacă se adună (sau scade) aceeaşi număr la toate valorile arcelor, nu se modifică ierarhia cuplajelor maxime, în ceea ce priveşte valoarea lor.
Vom prezenta algoritmul concomitent cu rezolvarea unui caz particular, pentru o mai bună receptare a acestuia:
"Într-o secţie produsele finite se obţin în urma efectuării succesive a 6 operaţii pe 6 maşini. În această secţie sunt angajaţi 6 muncitori, fiecare fiind calificat pentru efectuarea oricărei din cele 6 operaţii. Pentru a optimiza activitatea în secţie cei 6 muncitori au fost supuşi la un test în care fiecare a prelucrat un număr de piese, pe toate cele şase maşini. În final, calculându-se timpul mediu în care muncitorul Mi efectuează operaţia Oj s-au obţinut valorile (în ore) date în tabelul de mai jos:
M1 M2 M3 M4 M5 M6
O1 4 3 6 2 6 8O2 5 4 8 3 8 9O3 5 6 8 2 8 7O4 4 5 7 2 7 8O5 4 6 6 3 6 7O6 6 6 8 3 8 9
Să se găsească acea repartiţie a muncitorilor la maşini astfel încât timpul în care o piesă se prelucrează succesiv pe cele 6 maşini să fie minim." Pasul 1. Se construieşte matricea pătratică M care are elementele:
mij =
56
Pentru exemplul ales vom avea: M =
Pasul 2. Se scade din fiecare linie minimul acesteia apoi, în matricea obţinută, din fiecare coloană minimul acesteia (se poate face şi invers, rezultatul final va fi acelaşi). Pentru exemplul dat vom obţine succesiv matricile:
M1 = şi apoi M2 = Ultima matrice este cea asupra căreia se aplică următoarele calcule. În acest
moment pe fiecare linie şi pe fiecare coloană se află cel puţin un 0, care corespunde celui mai mic timp. Se încearcă în continuare folosirea doar a acestor repartizări:
Pasul 3. În ordinea crescătoare a numărului de zerouri şi de sus în jos (în cazul
existenţei mai multor linii cu acelaşi număr de zerouri ) se încadrează pentru fiecare linie zeroul a cărui coloană conţine cele mai puţine zerouri (primul de la stânga dintre acestea, în caz de egaliate) şi se barează celelalte zerouri de pe linia şi coloana acestuia. Pe parcursul algoritmului sunt luate în considerare la numărare doar zerourile neîncadrate şi nebarate încă. În final, pe fiecare linie şi pe fiecare coloană va fi cel mult un zero încadrat. Dacă în final sunt n (= dimensiunea matricei) zerouri, atunci arcele corespunzătoare formează cuplajul căutat. Dacă sunt mai puţine se trece la pasul 4.
În exemplul nostru avem trei linii cu câte un zero (a 3-a, a 4-a şi a 5-a) .Îl încadrăm pe cel de pe linia 3 (prima dintre ele) şi barăm restul zerourilor de pe linia 3 şi coloana 3, obţinând:
În acest moment pe liniile 1 şi 2 se află un zero. Se încadrează cel de pe linia
1 şi se barează celelalte de pe linia 1 şi coloana 2, obţinând:
57
Ultima linie cu zerouri este linia 5 din care îl încadrăm pe primul şi le barăm
pe celelalte:
În total nu sunt 6 zerouri încadrate (sunt doar trei) şi deci trecem la pasul 4.
Pasul 4. La acest pas se va stabili numărul minim posibil de linii şi coloane care să conţină toate zerourile matricii. În acest sens vom proceda astfel:
a) se marchează liniile care nu au nici un zero încadrat;b) se marchează coloanele care au un zero barat pe o linie marcată;c) se marchează liniile care au un zero încadrat pe o linie marcată (dacă
există);Se repetă operaţiile b) şi c) până nu mai poate fi marcată nici o linie şi nici o coloană.
În cazul nostru vom avea: a) se marchează liniile 2, 4 şi 6;b) se marchează coloanele 2 şi 4;c) se marchează liniile 1 şi 3;b) nu mai marcăm nici o coloană deoarece nu mai există nici un zero barat pe liniile 1 şi 3, care să corespundă unei coloane nemarcate;c) nu mai marcăm nici o linie, deoarece nu a mai apărut nici o coloană marcată.
Rezultă:
58
Pasul 5. Se taie liniile nemarcate şi coloanele marcate:
Pasul 6. Se împart elementele matricei în trei grupe:
G1 = elemente aflate la intersecţii de linii netăiate cu coloane netăiate;G2 = elemente situate la intersecţii de linii tăiate cu coloane netăiate sau de
linii netăiate cu coloane tăiate;G3 = elemente situate la intersecţii de coloane tăiate cu linii tăiate
Pasul 7. Se găseşte minimul grupei G1, care se scade din fiecare element al lui G1 şi se adună la fiecare element al grupei G3. Elementele grupei G2 rămân neschimbate.
Pentru exemplul dat, minimul lui G1 este 1 şi obţinem noua matrice:
Pasul 8. Se reia algoritmul de la pasul 3. Vom avea după marcare:
59
Deoarece avem 6 zerouri încadrate, am obţinut cuplajul maxim de valoare minimă căutat, căruia îi va corespunde repartizarea muncitorilor pe operaţii de mai jos:
care duce la o durată totală a prelucrării unei piese de 6 + 4 + 7 + 6 + 3 = 26 ore
Observaţie: Deoarece regula de a alege de sus în jos la linii cu acelaşi număr de zerouri este arbitrară şi de asemenea alegerea primului zero de la stânga, putem ajunge şi la alte cuplaje maxime, dar toate vor avea aceeaşi valoare, cea minimă. De exemplu, un alt cuplaj optim este:
60
adică care are de asemenea valoarea 26. Observaţia 1. Dacă dorim un cuplaj de valoare maximă atunci vom calcula la
pasul 1 matricea M astfel:
1. Construind matricea A de elemente:
aij =
2. Matricea M va avea componentele: mij =
apoi aplicăm în continuare algoritmul. Observaţia 2. Dacă AB atunci aplicăm acelaşi algoritm cu singura
diferenţă că ne vom opri când vom obţine un număr de zerouri egal cu min (A,B).
7. Drumuri şi circuite hamiltoniene Una dintre cele mai cunoscute probleme economice este problema comis
voiajorului. Comis voiajorul este un individ care trebuie să prezinte s-au să distribuie marfa comandată la o serie de centre distribuite în general neliniar pe o anumită zonă teritorială (localităţile dintr-un judeţ, magazinele dintr-un cartier, persoanele dintr-un sat etc). Dacă numărul de obiective care trebuie vizitate este mare sau foarte mare iar timpul disponibil foarte limitat atunci devine vitală o asemenea organizare a trecerii pe la fiecare obiectiv încât să se efectueze în timpul minim posibil. Acest timp minim se traduce prin drumul cel mai scurt, iar cel mai scurt drum este evident cel în care se trece pe la fiecare obiectiv o singură dată. În plus, la sfârşit trebuie să se afle în punctul iniţial, adică sediul firmei la care lucrează.
O reprezentare a regiunii aprovizionate, în care centrele pe la care se trece sunt vizualizate prin puncte iar căile de acces la acestea prin segmente de curbe, va fi
61
evident un graf, problema reducându-se la a găsi circuitul hamiltonian de lungime minimă.
În timp, s-au evidenţiat o multitudine de probleme reductibile la găsirea unui drum (sau circuit) hamiltonian într-un graf, cum ar fi:
1. Problema poştaşului (găsirea traseului cel mai scurt care trece pe la toate
locuinţele ce aparţin de oficiul poştal la care lucrează acesta);2. Problema adunării deşeurilor (cel mai scurt drum care trece pe la toate
punctele de depozitate a deşeurilor);3. Problema succesiunii operaţiilor (executarea mai multor operaţii pe o
maşină în acea ordine în care suma timpilor consumaţi cu pregătirea maşinii pentru trecerea de la o operaţie la următoarea să fie minim)
4. Ordinea lipirii unor componente electronice pe o placă, etc; Determinarea drumurilor hamiltoniene Problema determinării drumului (circuitului) hamiltonian de valoare optimă s-a dovedit
deosebit de dificilă, neexistând nici acum un algoritm care să rezolve problema în timp polinomial şi nici măcar o metodă simplă prin care să se decidă dacă într-un graf dat există sau nu drumuri hamiltoniene.
Există însă mai mulţi algoritmi, unii exacţi alţii heuristici, care reuşesc, într-un caz sau altul, să rezolve problema satisfăcător şi în timp util.
A. Algoritmul lui Foulkes
Pasul 1. Se scrie matricea booleană A asociată grafului G. Pasul 2. Se determină matricea D a drumurilor grafului G prin procedeul expus la începutul
capitolului şi apoi matricea M = I + D. Pasul 3. Se împarte mulţimea nodurilor grafului în submulţimi disjuncte astfel: 1. Se consideră în matricea M liniile pline (cu toate elementele 1). Nodurile ce corespund
liniilor pline cu 1 formează submulţimea C1.2. Se elimină liniile şi coloanele care corespund nodurilor din submulţimea stabilită.3. Se reia raţionamentul de la punctul 1 pe matricea redusă obţinută la punctul 2 obţinându-se
următoarea submulţime şi în continuare toate celelalte până se epuizează toate liniile matricei.
Pasul 4. Se construieşte graful G' în care:
1. Nodurile care formează o submulţime sunt reprezentate prin puncte în interiorul unui dreptunghi şi între acestea se trasează arcele existente în graful iniţial G.
62
2. Se trasează legăturile dintre submulţimi. Ele sunt reprezentate prin arcele existente în graful iniţial G între nodurile submulţimii C1 şi cele ale submulţimii C2, între nodurile submulţimii C2 şi cele ale submulţimii C3etc.
Pasul 5. Se găsesc drumurile hamiltoniene
Un drum hamiltonian se găseşte plecând de la un vârf din submulţimea C1, trecând prin toate vârfurile acesteia cu un drum hamiltonian, din ultimul vârf la care se ajunge în C1 trecând la un vârf din C2, parcurgând în continuare un drum hamiltonian în a doua submulţime şi tot aşa, trecând prin toate submulţimile şi parcurgând, deci, toate nodurile grafului iniţial, o singură dată. Aplicând acest procedeu în toate modurile posibile se obţin toate drumurile hamiltoniene din graful iniţial G. (Observaţie: poate să nu existe nici un drum hamiltonian în graful G, caz în care algoritmul se opreşte deoarece la un anumit pas nu mai exista nici o linie plina cu 1).
Observaţie. Algoritmul lui Foulkes reduce găsirea drumurilor hamiltoniene în graful
iniţial G (care în problemele practice este foarte mare) la găsirea mai multor drumuri hamiltoniene mai mici în componente tare conexe ale grafului. Dacă un graf are o singură componentă tare conexă, algoritmul lui Foulkes nu este eficient, în acest caz trebuind aplicaţi alţi algoritmi cum ar fi cel bazat pe înmulţirea latină.
B. Algoritmul lui Chen pentru determinarea drumurilor hamiltonieneîn grafuri fără circuite
Fie G = (X,U) un graf orientat fără circuite, cu n noduri: X = {x 1, x2, , x� n}. Vom
considera că am calculat matricea drumurilor D şi puterile de atingere ale tuturor nodurilor.Dacă în graful G există un drum de la nodul x i la nodul xj atunci evident p(xi) > p(xj),
deoarece în orice vârf în care se poate ajunge din xj se poate ajunge şi din xi dar din xj nu se poate ajunge în xj pentru că nu există circuite.
Teorema 2.3 (Chen) Un graf cu n noduri, fără circuite conţine un drum hamiltonian
dacă şi numai dacă există relaţia:
Demonstraţie � � Fie H un drum hamiltonian şi presupunem că nodurile grafului au fost notate în
ordinea în care apar în acest drum. Atunci din orice nod x i se poate ajunge în toate nodurile cu indice mai mare şi numai în acestea (altfel ar exista circuite) şi deci puterea unui nod x i este n i,� de unde:
= (n 1) + (n 2) + + 1 + 0 =� � � � Ordonând vârfurile în ordinea descrescătoare a puterii lor de atingere (i > j� p(xi) <
p(xj)) şi cum graful nu are circuite, vom obţine o matrice D cu toate zerourile deasupra diagonalei (evident pe o poziţie (i,i) nu se află nici un 1 iar dacă ar fi un 1 pe poziţia (i,j) cu i > j
63
ar însemna că din xi se poate ajunge în xj, deci în toate nodurile în care se poate ajunge din x j, iar din xj nu se poate ajunge în xi, deci p(xi) > p(xj) în contradicţie cu ipoteza de ordonare a
nodurilor). Cum deasupra diagonalei sunt poziţii iar suma puterilor vârfurilor este
chiar rezultă că toate poziţiile de deasupra diagonalei sunt 1. Aceasta înseamnă că există toate arcele de forma (xi,xi+1) (altfel n-ar exista drum de la xi la xi+1, deoarece toate drumurile au indicii nodurilor în ordine descrescătoare) şi deci drumul hamiltonian (x1, x2, , x� n) q.e.d.
Teorema 2.4 Dacă într-un graf orientat fără circuite există un drum hamiltonian atunci
acesta este unic. Demonstraţie Deoarece un drum hamiltonian se identifică cu o permutare a nodurilor
grafului, existenţa a două drumuri hamiltoniene implică existenţa a două permutări distincte a nodurilor grafului şi cum două permutări distincte diferă prin cel puţin o inversiune vor exista două noduri xi şi xj în ordinea xi xj pe un drum şi invers pe celălalt, existând deci un drum atât de la xi la xj cât şi de la xj la xi, cele două formând împreună un circuit, în contradicţie cu ipoteza.
Pe aceste teoreme se bazează algoritmul lui Chen de determinare a drumului
hamiltonian într-un graf orientat fără circuite:
Pasul1. Se scrie matricea de adiacenţă APasul2. Se calculează matricea drumurilor DPasul3. Dacă există un indice i cu dii = 1 atunci graful are circuite, nu se poate aplica algoritmul
lui Chen şi algoritmul se opreşte. Dacă nu, se trece la pasul 4.Pasul4. Se calculează puterile de atingere pentru fiecare nod.
Pasul5. Dacă nu se verifică relaţia atunci graful nu are drumuri hamiltoniene şi algoritmul se opreşte, altfel se trece la pasul 6.
Pasul6. Se ordonează nodurile în ordinea descrescătoare a puterilor lor de atingere şi obţinem drumul hamiltonian căutat.
C. Algoritmul lui Kaufmann
Pasul 1. Construim matricea latină L asociată grafului, unde:
lij = Pasul 2. Construim matricea , definită prin:
= numită matricea latină redusă.
64
Pasul 3. Se calculează succesiv matricile:
L2 = L , L3 = L2 , ..., Lk+1 = Lk , ... folosind operaţiile de înmulţire şi adunare latină, alfabetul fiind mulţimea nodurilor grafului, unde operaţia de înmulţire este uşor modificată, produsul dintre două elemente ale matricilor fiind 0, dacă unul dintre ele este 0 sau au un nod comun, şi este produsul latin al lor, în caz contrar.
Din felul cum a fost construită, matricea Lk va conţine toate drumurile elementare de lungime k. Cum un drum elementar poate avea cel mult n noduri (câte are graful cu totul) rezultă că:
primele n-1 puteri ale L conţin toate drumurile elementare din graf; puterile lui L mai mari sau egale cu n au toate elementele egale cu 0; matricea Ln-1 conţine toate drumurile hamiltoniene din graf.
Pasul 4. Dacă se doresc şi circuitele atunci se verifică pentru fiecare drum hamiltonian dacă poate fi completat până la un circuit (adică dacă există în graf arcul care uneşte nodul final cu cel iniţial);
Pasul 5. Dacă se doreşte şi drumul (sau circuitul) de valoare optimă (maximă sau minimă) se calculează suma valorilor pentru fiecare drum şi/sau circuit şi se alege cel cu valoarea optimă.
În concluzie, metoda înmulţirii latine (A. Kaufmann J. Melgrange) determină toate�
drumurile elementare din graf, prin calcularea matricelor M(1), M(2), M(3), , M� (n-1).În matricea M(n-1) se citesc drumurile hamiltoniene.Această metodă a înmulţirii latine (algoritmul lui Kaufmann) este utilă, mai ales, în cazul
grafurilor tare conexe, unde algoritmul lui Foulkes nu este eficient. Totuşi, metoda este greu de aplicat în grafuri cu un număr mare de noduri. În acest caz este preferabil să se construiască graful condensat, să se determine drumurile hamiltoniene în fiecare în parte cu algoritmul lui Kaufmann şi apoi, ca la algoritmul lui Foulkes, să se caute drumurile hamiltoniene în graful iniţial.
D. Un algoritm bazat pe algoritmul ungar Fie G = (X,U) un graf orientat cu n noduri X = {x1, x2, , x� n}.
Pasul 1. Se construieşte graful bipartit H = (AB,V) în care A = B = X şi V = U (adică am folosit pentru G reprezentarea prin corespondenţă).
Pasul 2. Se găseşte pentru graful H cuplajul maxim de valoare minimă.Pasul 3. Se construieşte graful parţial al lui G format doar cu arcele cuplajului găsit. Este uşor
de demonstrat că, componentele tare conexe ale acestuia sunt toate nişte circuite. Dacă s-a format un singur circuit acesta este circuitul hamiltonian de valoare minimă. Dacă s-au format mai multe se trece la pasul 4.
65
Pasul 4. Pentru fiecare arc aflat pe circuitul de lungime minimă (dacă sunt mai multe se iau în considerare arcele tuturor) se reia algoritmul de la pasul 1 pentru graful parţial rezultat din G prin eliminarea acestui arc.
Pasul 5. Pentru fiecare graf parţial se continuă procedeul până se ajunge la unul din cazurile:
Cazul1. Cuplajului maxim găsit îi corespunde un singur circuit. Dacă acest circuit este primul obţinut atunci valoarea sa i se atribuie unei variabile Z şi circuitul este păstrat. Dacă nu este primul atunci valoarea sa se compară cu Z şi, dacă este mai mică, ea devine noua valoare a lui Z şi circuitul se păstrează, eliminându-l pe cel corespunzător fostei valori a lui Z. În caz contrar se trece la alt graf parţial neanalizat încă.
Cazul2. Cuplajul maxim are o valoare mai mare decât Z. Pentru acest graf parţial se abandonează ramificarea.
Pasul 6. Se continuă analiza grafurilor parţiale până sunt analizate toate ramificaţiile. Valoarea
Z finală este valoarea circuitului de valoare minimă iar circuitul corespunzător este cel optim.
Analiza de mai sus poate fi schematizată printr-un arbore de tipul:
în care fiecare nod este un graf parţial de analizat, iar pentru fiecare arc, nodul inferior este un graf parţial care provine din graful corespunzător nodului superior, prin suprimarea unui arc de pe circuitele de lungime minimă corespunzătoare cuplajului maxim de valoare minimă al acestuia.
Observaţie: Algoritmul asigură găsirea circuitului de valoare minimă iar în cazul în care algoritmul lui Foulkes nu funcţionează este o alternativă mai bună decât algoritmul lui Kaufmann. Totuşi el nu lucrează în timp polinomial şi în unele cazuri (de exemplu cazuri în care se formează foarte multe cicluri cu lungime minimă) necesită un număr imens de calcule.
În aceste cazuri se pot folosi metode euristice prin care se elimină din start o serie de arce, considerate a avea valori prea mari pentru a se putea afla pe circuitul hamiltonian de valoare minimă, apoi se aplică în graful parţial rămas unul din algoritmii de mai sus.
66
8. Drumuri optime într-un graf În marea majoritate a problemelor care pot fi modelate prin grafuri nu ne interesează
numai dacă există sau nu legături între componentele reprezentate prin nodurile grafului ci şi intensitatea acestora. Această intensitate are semnificaţia unei valori numerice (pozitive sau negative) asociate arcului corespunzător legăturii a cărei intensitate o măsoară.
În aplicaţiile economice această valoare poate fi: lungimea drumului dintre două localităţi; costul parcurgerii rutei reprezentate prin arcul corespunzător; durata parcurgerii rutei respective; cantitatea transportată pe ruta respectivă; capacitatea maximă a rutei respective; câştigul realizat prin trecerea de la o stare la alta a sistemului; consum de energie pentru efectuarea trecerii respective; punctaj realizat etc.
Una din problemele care poate apărea în aceste situaţii este găsirea, pentru o anumită
pereche de noduri (sau mai multe perechi), a drumului optim între acestea.Pentru formalizarea problemei vom introduce noţiunea de valoare a unui drum, care
este egală cu suma valorilor arcelor care îl compun. Vom nota în continuare valoarea unui arc (xi,xj) cu v(xi,xj) sau cu vij. În aceste condiţii putem enunţa problema drumului optim astfel:
"Dat un graf G = (X,U) şi o funcţie care asociază fiecărui arc o valoare reală, să se găsească, pentru o pereche dată de noduri, drumul (drumurile) de valoare optimă (minimă sau/şi maximă) între cele două noduri şi valoarea acestuia (acestora)"
Deoarece este vorba de găsirea minimului unei mulţimi de numere reale, prima întrebare care se pune este dacă aceasta admite minim. Dacă mulţimea nodurilor grafului este infinită atunci pot exista o infinitate de drumuri elementare distincte între cele două noduri şi mulţimea valorilor acestora poate avea orice formă (închisă sau nu, mărginită sau nu) devenind foarte greu de caracterizat cazurile când minimul dorit există. Deoarece totuşi majoritatea covârşitoare a problemelor economice se modelează prin grafuri cu număr finit de noduri, ne vom limita în continuare doar la acestea.
Un număr finit de noduri n atrage după sine existenţa unui număr finit de arce (cel mult
n2) şi a unui număr finit de drumuri elementare ( cel mult nn! ). Deoarece oricărui drum d îi corespunde un drum elementar de (obţinut prin eliminarea tuturor subcircuitelor lui d) putem calcula valoarea oricărui drum ca sumă între valoarea drumului elementar corespunzător şi valorile unor subcircuite ale sale, fiecare înmulţită cu numărul de parcurgeri ale circuitului respectiv.
În concluzie, dacă există un circuit de valoare negativă înseamnă că există drumuri de valoare oricât de mică (cele care conţin acest circuit), obţinută prin parcurgerea acestuia de oricâte ori dorim) şi, deci, mulţimea valorilor drumurilor este nemărginită inferior, neexistând drum de valoare minimă. Dacă există un circuit de valoare pozitivă atunci există drumuri de
67
valoare oricât de mare şi mulţimea valorilor drumurilor este nemărginită superior, neexistând drum de valoare maximă.
Dacă nu există circuite de valoare negativă atunci valoarea oricărui drum este mai mare sau egală cu a drumului elementar corespunzător, deci drumul de valoare minimă (dacă există) va fi un drum elementar. Cum mulţimea drumurilor elementare este finită (şi deci şi mulţimea valorilor lor) va avea minorant şi am lămurit problema compatibilităţii problemei. Analog, dacă nu există circuite de valoare pozitivă atunci valoarea oricărui drum este mai mică sau egală cu a drumului elementar corespunzător, deci drumul de valoare maximă (dacă există) va fi un drum elementar. Cum mulţimea drumurilor elementare este finită (şi deci şi mulţimea valorilor lor), va avea majorant.
Obs. 1. Dacă în graf nu există decât arce de valoare pozitivă atunci există drum de valoare minimă.
Obs. 1. Dacă în graf nu există decât arce de valoare negativă atunci există drum de valoare maximă.
Obs. 1. Dacă în graf nu există circuite atunci există şi drum de valoare minimă şi drum de valoare maximă.
Deoarece din cele de mai sus se sesizează importanţa existenţei circuitelor într-un graf vom da în continuare un algoritm de depistare a existenţei circuitelor într-un graf:
Pasul 1. Se construieşte mulţimea A formată din nodurile pentru care toate arcele incidente sunt
incidente spre interior ( noduri în care toate arcele "intră" sau, altfel spus, noduri din care nu "pleacă" nici un arc).
Pasul 2. Se găsesc toate nodurile care nu sunt din A pentru care toate arcele incidente au cealaltă extremitate în A (noduri din care se poate "ajunge" doar in A). Dacă nu există nici un astfel de arc se trece la pasul 4.
Pasul 3. Se adaugă arcele găsite la pasul 2 la mulţimea A apoi se reia algoritmul de la pasul 2, pentru noua mulţime A.
Pasul 4. Dacă A conţine mulţimea tuturor nodurilor atunci graful nu conţine circuite. Dacă au rămas noduri în afara lui A atunci graful conţine circuite.
Algoritmi de găsire a drumului optim
Din cauza varietăţii nelimitate a grafurilor posibile, nu există un algoritm care să rezolve orice problemă în timp util, dar s-au elaborat o mulţime de algoritmi, fiecare fiind cel mai eficace în anumite cazuri. Aceşti algoritmi pot fi grupaţi în cinci categorii:
1. Algoritmi prin calcul matricial (Bellman-Kalaba, I. Tomescu, Bellman-Schimbell);2. Algoritmi prin ajustări succesive: (Ford);3. Algoritmi prin inducţie (Dantzig);4. Algoritmi prin ordonare prealabilă a vârfurilor grafului;5. Algoritmi prin extindere selectivă (Dijkstra).
În continuare vom prezenta trei dintre aceşti algoritmi.
A. Algoritmul lui Bellman - Kalaba
68
Algoritmul se aplică în grafuri finite care nu au circuite de valoare negativă (pentru o problemă de minim) sau care nu au circuite de valoare pozitivă (într-o problemă de maxim) şi găseşte drumurile de valoare minimă (maximă) de la toate nodurile grafului la un nod oarecare, fixat. Dacă dorim să cunoaştem drumurile de valoare minimă (maximă) între oricare două noduri vom aplica algoritmul, pe rând, pentru fiecare nod al grafului.
Fie G = {x1, x2, ... ,xn} un graf orientat finit. Presupunem (fără a restrânge generalitatea, că am numerotat nodurile astfel încât nodul spre care căutăm drumurile de valoare minimă (maximă) de la celelalte noduri să fie xn.
Pasul 1. Se construieşte matricea pătratică M cu dimensiunea egală cu numărul de noduri ale
grafului ale cărei elemente sunt:
mij =
Pasul 2. Se adaugă succesiv liniile Li la matricea M, elementele acestora calculându-se prin relaţiile de recurenţă:
1. L1j = mjn j = 1,...,n (prima linie este ultima coloană, transpusă, a matricii M)
2. Lij = min (Li-1,j , (mjk + Li-1,k)) într-o problemă de minim
sau Lij = max (Li-1,j , (mjk + Li-1,k)) într-o problemă de maxim
Pasul 3. După calcularea fiecărei linii noi se compară elementele ei cu cele ale precedentei: Dacă Lij = Li-1,j pentru orice j = 1,...,n atunci se opreşte recurenţa şi ultima linie
calculată conţine valorile minime ale drumurilor de la celelalte noduri la nodul xn.
Dacă există cel puţin un indice j cu Lij Li-1,j se trece la calcularea noii linii Li+1
Pasul 4. Pentru găsirea drumului care dă valoarea minimă de la un nod x j la nodul xn se găsesc, începând înapoi de la ultima linie, pe care s-au obţinut valorile finale, notată Lf,
nodurile , , ..., care formează drumul căutat, unde = xj, = xn şi fiecare alt indice ki+1 este cel pentru care s-a obţinut minimul(maximul) de pe poziţia ki al liniei Li.
Observaţie: Pentru grafuri foarte mari, algoritmul necesită un volum mare de memorie, prin necesitatea memorării matricei M, care este greu de manipulat. Chiar dacă din cele n2 arce posibile graful ar avea doar un procent foarte mic matricea grafului va avea tot n2 poziţii de memorat şi analizat.Exemplu: Presupunem dat graful orientat de mai jos, în care se doreşte găsirea drumului de valoare minimă de la nodul x1 la nodul x9.
69
Matricea M va fi iar după calcularea liniilor Li obţinem:
x1 x2 x3 x4 x5 x6 x7 x8 x9
x1 0 4 5 x2 0 7 9 x3 0 3 9x4 0 3x5 8 2 7 0 3 2 9 x6 8 0 5 x7 0 6 8x8 4 0 7x9 0L1 9 3 8 7 0L2 1
26 3 10 1
38 7 0
L3 15 12
6 3 8 13
8 7 0
L4 13 12
6 3 8 13
8 7 0
L5 13 12
6 3 8 13
8 7 0
70
Deoarece L4 = L5 oprim calcularea liniilor după calcularea liniei 5. În această linie se află valorile celor mai scurte de la toate nodurile la nodul x9. Drumul dorit de noi (x1 x9) are valoarea dată de prima poziţie a liniei 5, fiind egal cu 13.
Pentru a găsi acest drum, plecăm înapoi de la linia 4 şi avem:
x1
x5
13= 8 + 5 x3
8 = 6 + 2
x4
6 = 3 + 3
3 x9
B. Algoritmul lui Ford simplificat
Algoritmul lui Ford simplificat se aplică doar în grafuri care nu admit circuite. Cu
ajutorul lui se găseşte drumul de valoare optimă între două noduri fixate xi şi xj. Printr-o eventuală renumerotare a nodurilor putem presupune că nodul de la care porneşte drumul este x1, care va fi numit nod iniţial, iar nodul la care se termină este xn, numit nod final.
Algoritmul este:
Pasul 1. I se dă vârfului iniţial valoarea 0 (zero): w(x0) = 0Pasul 2. Se construieşte mulţimea A formată din nodul iniţial: A = {x1}Pasul 3. Se analizează nodurile din afara mulţimii A.
Dacă există noduri în care se poate ajunge prin arce directe doar de la nodurile mulţimii A, acestea se adaugă la mulţimea A, cu valoarea:
w(xi) = , în problemele de minim
sau w(xi) = , în problemele de maximapoi se trece la pasul 4 Dacă nu există nici un nod de acest tip atunci nu există nici un drum de la x1 la
xn. STOP
Pasul 4. Se analizează mulţimea A:
71
Dacă xn A atunci valoarea sa reprezintă valoarea drumului de valoare optimă de la x1 la xn. Pentru găsirea acestui drum se porneşte înapoi de la nodul final xn şi se
găsesc nodurile , , ..., care formează drumul căutat, unde =
xn, = x1 şi fiecare alt indice ki+1 este cel pentru care:
w( ) + v( , ) = w( ) STOP Dacă xn A se reia algoritmul de la pasul 3.
Exemplu: Pentru acelaşi graf şi aceeaşi pereche de noduri din exemplul rezolvat cu algoritmul lui Bellman-Kalaba vom avea succesiv: pas1: w(x1) = 0pas2: A = {x1}pas3: Nodurile în care se poate ajunge doar din x1: {x5}
w{x5) = min( w(x1) + v(x1,x5)) = 0 + 5 = 5pas4: x9 Apas3: A = {x1,x5} şi nodurile în care se poate ajunge prin arce directe doar din x1 şi x5 sunt: {x6}
w{x6) = min( w(x1) + v(x1,x6), w(x5) + v(x5,x6)) = min(0 + 3 , 5 + 3) = 3pas4: x9 Apas3: A = {x1,x5,x6} şi nodurile în care se poate ajunge prin arce directe doar din x1, x5 şi x6 sunt:
{x2,x7} w{x2) = min( w(x1) + v(x1,x2), w(x5) + v(x5,x2), w(x6) + v(x6,x2)) = min(0 + 4,5 + 8,3 + 8) =
4w{x7) = min( w(x5) + v(x5,x7), w(x6) + v(x6,x7)) = min(5 + 2,3 + 5) = 7
pas4: x9 Apas3: A = {x1,x2,x5,x6,x7} şi nodurile în care se poate ajunge prin arce directe doar din x1, x2, x5,
x6 şi x7 sunt: {x3,x8} w{x3) = min( w(x2) + v(x2,x3), w(x5) + v(x5,x3)) = min(4 + 7,5 + 2) = 7w{x8) = min( w(x5) + v(x5,x8), w(x7) + v(x7,x8)) = min(5 + 9,7 + 6) = 13
pas4: x9 Apas3: A = {x1,x2,x3,x5,x6,x7,x8} şi nodurile în care se poate ajunge prin arce directe doar din x1,
x2,x3,x5, x6, x7 şi x8 sunt: {x4} w{x4) = min( w(x2) + v(x2,x4), w(x3) + v(x3,x4),w(x5) + v(x5,x4), w(x8) + v(x8,x4)) = min(4 + 9,7 + 3,5 + 7,13 + 4) = 10
pas4: x9 Apas3: A = {x1,x2,x3,x4,x5,x6,x7,x8} şi nodurile în care se poate ajunge prin arce directe doar din x1,
x2, x3, x4, x5, x6, x7 şi x8 sunt: {x9} w{x9) = min( w(x3) + v(x3,x9), w(x4) + v(x4,x9), w(x7) + v(x7,x9), w(x8) + v(x8,x9)) = min(7 + 9, 10 + 3, 7 + 8, 13 + 7) = 13
pas4: x9 A şi urmează să găsim drumul care are lungimea 13.Avem succesiv:
w(x9) = w(x4) + v(x4,x9)w(x4) = w(x3) + v(x3,x4)w(x3) = w(x5) + v(x5,x3)w(x5) = w(x1) + v(x1,x5)
deci drumul căutat este: x1 x5 x3 x4 x9
72
Observaţia 1. Dacă graful are un circuit atunci se poate demonstra uşor că nu vom putea
da valoare nici unui nod al acestuia şi dacă există vreun drum de la x1 la xn care trece prin unul din nodurile circuitului nu vom putea da valoare nici lui xn, cu toate că există drum de la x1 la xn.
Observaţia 2: Algoritmul necesită pentru memorare şi manipulare doar cunoaşterea, pentru fiecare nod, a nodurilor spre care "pleacă" arce din acesta şi valorile acestor arce, fiind mult mai uşor de aplicat sau implementat pe calculator. El are însă dezavantajul că se poate aplica doar în grafuri fără circuite.
C. Algoritmul Ford generalizat Algoritmul lui Ford generalizat a fost creat cu scopul de a putea găsi drumul optim şi în
grafurile care au circuite. Cu ajutorul lui se găseşte drumul de valoare optimă între două noduri fixate xi şi xj. Printr-o eventuală renumerotare a nodurilor putem presupune că nodul de la care porneşte drumul este x1, care va fi numit nod iniţial, iar nodul la care se termină este xn, numit nod final.
Algoritmul este:
Pasul 1. I se dă vârfului iniţial valoarea 0 (zero): w(x0) = 0 şi tuturor celelalte valoarea + (într-o problemă de minim) sau - (într-o problemă de maxim).
Pasul 2. În ordinea crescătoare a indicilor nodurilor se calculează pentru fiecare nod, pe bază fostelor valori, noile valori cu formula:
w*(xi) = în problemele de minim
sau w*(xi) = în problemele de maximPasul 3. Se compară noile valori w*(xi) cu fostele valori w(xi):
Dacă w*(xi) = w(xi) pentru orice nod xi atunci: dacă w(xn) < (la problema de minim) sau w(xn) > - (la problema de
maxim), valoarea nodului xn reprezintă valoarea drumului de valoare minimă(maximă) de la x1 la xn. Pentru găsirea acestui drum se porneşte înapoi
de la nodul final xn şi se găsesc nodurile , , ..., care formează
drumul căutat, unde = xn, = x1 şi fiecare alt indice ki+1 este cel pentru care:
w( ) + v( , ) = w( ) STOP dacă w(xn) = + (-) atunci nu există nici un drum de la x1 la xn. STOP
Dacă există cel puţin un nod pentru care w*(xi) < w(xi) se reia algoritmul de la pasul 2 pentru noile valori ale vârfurilor.
Observaţie: Algoritmul poate găsi drumul şi în grafuri cu circuite dar este evident mult
mai lent decât cel simplificat. Pentru scurtarea duratei de execuţie se poate modifica algoritmul
73
în sensul că o valoare nou calculată a unui vârf va fi folosită imediat ca atare la calculul noilor valori ale celorlalte, nu doar după ce se calculează noile valori ale tuturor vârfurilor.
D. Algoritmul lui Dijkstra În algoritmul Ford simplificat, pentru a găsi valoarea nodului final, deci a drumului
minim, plecăm de la nodul iniţial în toate direcţiile posibile, păstrând de fiecare dată toate nodurile analizate. Acest fapt duce la un consum inutil de timp, deoarece foarte multe din aceste noduri nu vor face parte din drumul optim. Pentru a elimina acest neajuns, algoritmul lui Dijkstra încearcă să păstreze, la fiecare iteraţie, mulţimea minimă de noduri care să le conţină pe toate cele care vor forma efectiv drumul optim. În plus, algoritmul se poate aplica şi în drumuri cu circuite. Ca un minus este faptul că se aplică doar la probleme de minim. Algoritmul are următorii paşi:
Pasul 1. I se dă vârfului iniţial valoarea 0 (zero): w(x0) = 0Pasul 2. Se construieşte mulţimea A formată din nodul iniţial: A = {x1}Pasul 3. Se analizează nodurile din afara mulţimii A.
Dacă există noduri în care se poate ajunge prin arce directe de la noduri din A (nu doar de la nodurile mulţimii A, ca la algoritmul lui Ford simplificat) se calculează pentru toate acestea:
w(xi) = în problemele de minim dar, spre deosebire de algoritmul lui Ford simplificat, se adaugă la mulţimea A doar cel pentru care se obţine valoarea minimă, apoi se trece la pasul 4. Dacă nu există nici un nod de acest tip atunci nu există nici un drum de la x1 la
xn. STOP
Pasul 4. Se analizează mulţimea A: Dacă xn A atunci valoarea sa reprezintă valoarea drumului de valoare optimă de
la x1 la xn. Pentru găsirea acestui drum se porneşte înapoi de la nodul final xn şi se
găsesc nodurile , , ..., care formează drumul căutat, unde =
xn, = x1 şi fiecare alt indice ki+1 este cel pentru care:
w( ) + v( , ) = w( ) STOP Dacă xn A se reia algoritmul de la pasul 3.
Exemplu Vom aplica algoritmul la acelaşi graf folosit la ceilalţi algoritmi, pentru a putea
face comparaţii:
pas1: w(x1) = 0pas2: A = {x1}pas3: Nodurile în care se poate ajunge şi din x1: {x2, x5, x6}
w{x2) = min( w(x1) + v(x1,x2)) = 0 + 4 = 4w{x5) = min( w(x1) + v(x1,x5)) = 0 + 5 = 5
74
w{x6) = min( w(x1) + v(x1,x6)) = 0 + 3 = 3min(w{x2),w{x5),w{x6)) = w{x6) = 3
pas4: x9 Apas3: A = {x1,x6} şi nodurile în care se poate ajunge prin arce directe din x1 sau x6 sunt:
{x2,x5,x7}w{x2) = min( w(x1) + v(x1,x2), w(x6) + v(x6,x2)) = min(0 + 4 , 3 + 8) = 4w{x5) = min( w(x1) + v(x1,x5)) = min(0 + 5) = 5w{x7) = min( w(x6) + v(x6,x7)) = min(3 + 5) = 8min(w{x2),w{x5),w{x7)) = w{x2) = 4
pas4: x9 Apas3: A = {x1,x2,x6} şi nodurile în care se poate ajunge prin arce directe din x1, x2 sau x6 sunt:
{x3,x4,x5,x7} w{x3) = min( w(x2) + v(x2,x3)) = min(4 + 7) = 11w{x4) = min( w(x2) + v(x2,x4)) = min(2 + 9) = 11w{x5) = min( w(x1) + v(x1,x5)) = min(0 + 5) = 5w{x7) = min( w(x6) + v(x6,x7)) = min(3 + 5) = 0min(w{x3),w{x4),w{x5),w{x7)) = w{x5) = 5
pas4: x9 Apas3: A = {x1,x2,x5,x6} şi nodurile în care se poate ajunge prin arce directe din x1, x2, x5, x6 şi
x7 sunt: {x3,x4,x7,x8} w{x3) = min( w(x2) + v(x2,x3), w(x5) + v(x5,x3)) = min(4 + 7,5 + 2) = 7w{x4) = min( w(x2) + v(x2,x4), w(x5) + v(x5,x4)) = min(4 + 9,5 + 7) = 12w{x7) = min( w(x5) + v(x5,x7), w(x6) + v(x6,x7)) = min(5 + 2,3 + 5) = 7w{x8) = min( w(x5) + v(x5,x8)) = min(5 + 9) = 14min(w{x3),w{x4),w{x7),w{x8)) = w{x3) = w{x7) = 7
pas4: x9 Apas3: A = {x1,x2,x3,x5,x6,x7} şi nodurile în care se poate ajunge prin arce directe din x1, x2, x3, x5,
x6, şi x7 sunt: {x4,x8,x9} w{x4) = min( w(x2) + v(x2,x4), w(x3) + v(x3,x4),w(x5) + v(x5,x4)) = min(4 + 9,7 + 3,5 + 7) =10w{x8) = min( w(x5) + v(x5,x8), w(x7) + v(x7,x8)) = min(5 + 9,7 + 6) = 13w{x9) = min( w(x3) + v(x3,x9), w(x7) + v(x7,x9)) = min(7 + 9,7 + 8) = 15min(w{x4),w{x8),w{x9)) = w{x4) = 10
pas4: x9 Apas3: A = {x1,x2,x3,x4,x5,x6,x7} şi nodurile în care se poate ajunge prin arce directe din x1, x2, x3,
x4, x5, x6, şi x7 sunt: {x8,x9} w{x9) = min( w(x3) + v(x3,x9), w(x4) + v(x4,x9), w(x7) + v(x7,x9)) = min(7 + 9,10 + 3,7+8)=13w{x8) = min( w(x5) + v(x5,x8), w(x7) + v(x7,x8)) = min(5 + 9,7 + 6) = 13min(w{x8),w{x9)) = w{x8) = w{x9) = 13
pas4: x9 A şi urmează să găsim drumul care are lungimea 13.Avem succesiv:
w(x9) = w(x4) + v(x4,x9)w(x4) = w(x3) + v(x3,x4)w(x3) = w(x5) + v(x5,x3)w(x5) = w(x1) + v(x1,x5)
deci drumul căutat este: x1 x5 x3 x4 x9
75
9. Reţele de transport Într-o mare varietate de situaţii concrete din practica economică se pune problema
deplasării unei cantităţi de materie, energie, informaţie etc, din anumite locuri, numite surse, în alte locuri, numite destinaţii. Pentru realizarea acestui transport se folosesc o serie de trasee, numite rute de legătură. Unităţile indivizibile ale cantităţii Q, care se deplasează de-a lungul rutelor între surse şi destinaţii, se numesc unităţi de flux, iar ansamblul rutelor, surselor, destinaţiilor şi, eventual, a altor puncte intermediare se numeşte reţea de transport.
Situaţia de mai sus poate fi reprezentată geometric printr-un graf finit, conex şi fără bucle.Pentru ca o astfel de problemă să fie suficient de complexă pentru a necesita un studiu
matematic riguros, trebuie ca fiecare sursă să poată aproviziona mai multe destinaţii şi orice destinaţie să poată fi aprovizionată de mai multe surse.
Aprovizionarea destinaţiilor se poate face direct de la surse sau prin intermediul altor puncte, numite puncte intermediare. În cazul cel mai general pot exista de asemenea legături între surse şi/sau legături între destinaţii.
Aşa cum s-a văzut şi la problema de transport, situaţia de mai sus este un cadru extrem de larg, care permite existenţa unui număr foarte mare de tipuri de probleme posibile, diferite între ele prin informaţiile suplimentare pe care le avem despre reţea şi prin obiectivele urmărite.
Una dintre acestea este problema determinării cantităţii maxime (minime) care poate fi transportată de la surse la destinaţii, în situaţia în care sursele dispun de cantităţi limitate (inferior sau superior), destinaţiile au un necesar sau o putere de absorbţie limitată inferior sau superior iar pe fiecare rută se poate transporta doar o cantitate cuprinsă între anumite limite.
Pentru studiul matematic al acestei situaţii vom da definiţiile matematice ale obiectelor implicate în problemă şi ipotezele modelului.
Definiţia 1: Se numeşte reţea de transport standard un graf finit, simplu,
conex, fără bucle G = (X,U) care are următoarele proprietăţi:
1. Există şi este unic s a.î. , (din care doar "ies" arce), numit intrarea reţelei de transport;
2. Există şi este unic t a.î. = , (în care doar "intră" arce) numit ieşirea reţelei de transport;
3. S-a definit o funcţie c: U R+ care asociază fiecărui arc u un număr strict pozitiv cu numit capacitatea arcului.
Observaţie: Este clar că exemplele obişnuite au doar rareori o singură sursă şi o singură destinaţie. Totuşi, printr-o tehnică foarte simplă, orice reţea de transport se poate aduce la forma standard:
1. Dacă sunt mai multe surse se introduce un nod suplimentar din care "pleacă" câte un arc spre fiecare sursă (şi numai spre acestea), iar capacităţile acestor arce vor fi egale cu disponibilurile surselor corespunzătoare;
76
2. Dacă sunt mai multe destinaţii se introduce un nod suplimentar spre care "pleacă" câte un arc din fiecare destinaţie (şi numai din acestea), iar capacităţile acestor arce vor fi egale cu necesarurile destinaţiilor corespunzătoare;
Definiţia 2: Se numeşte flux într-o reţea de transport R = (X,U) o funcţie :
U R+ care are următoarele proprietăţile:P1. 0 u cu oricare ar fi u din U; valoarea u se numeşte flux al arcului u
P2. oricare ar fi i s,t (suma fluxurilor arcelor care "intră" într-un nod i este egală cu suma fluxurilor arcelor care "ies" din acest nod, cu excepţia nodului iniţial şi al celui final.
Definiţia 3: Se numeşte valoare a fluxului suma fluxurilor arcelor care
"pleacă" din nodul iniţial s şi se notează cu .Observaţie: Se poate demonstra uşor că această valoare este egală şi cu suma
fluxurilor arcelor care "intră" în nodul final t. În concluzie avem:
= Valoarea fluxului reprezintă cantitatea care se transportă efectiv pe reţea de la
surse la destinaţii. Definiţia 4: Se numeşte flux de valoare maximă într-o reţea un flux în
această reţea, cu proprietatea că, pentru orice alt flux ' pe această reţea, avem '.
Valoarea fluxului de valoare maximă reprezintă cea mai mare cantitate care se
poate transporta efectiv pe reţea, de la surse la destinaţii. Economic vorbind, ne interesează, referitor la o reţea, răspunsurile la
următoarele întrebări:
1. Putem transporta întreaga cantitate necesară la destinaţii?2. Dacă da, cum transportăm efectiv această cantitate de la surse la
destinaţii?3. Dacă nu, din ce motiv nu putem realiza acest transport?4. Cum putem înlătura cu eforturi minime acest motiv?
Răspunsul la primele două întrebări se poate afla prin găsirea fluxului de
valoare maximă şi compararea valorii lui cu suma necesarurilor destinaţiilor. În plus,
77
valoarea acestuia pe un arc reprezintă cantitatea care trebuie transportată pe ruta respectivă, pentru a obţine această valoare a fluxului.
Răspunsul la ultimele două întrebări porneşte de la observaţia că cea mai mare cantitate care poate traversa reţeaua de la un cap la altul este egală cu dimensiunea celui mai îngust loc de trecere prin reţea. Dacă vrem, deci, să mărim fluxul va trebui să lărgim tocmai acest cel mai îngust loc de traversare al reţelei.
Pentru formalizarea consideraţiilor de mai sus vom introduce noţiunea de tăietură într-o reţea:
Definiţia 5: Dată o reţea de transport G(X,U) cu s = nodul iniţial şi t = nodul
final, se numeşte tăietură în reţea o partiţie a mulţimii vârfurilor reţelei de transport, formată din două submulţimi V şi W (VW = , VW = X) astfel încât s V şi t W.
O tăietură poate fi privită, intuitiv, ca o secţiune a reţelei, care lasă nodul iniţial
cu o submulţime din noduri într-o parte, nodul final cu restul nodurilor în cealaltă parte şi retează toate arcele care trec dintr-o parte în cealaltă.
A cunoaşte o tăietură este echivalent cu a cunoaşte care sunt elementele celor două mulţimi, V şi W, care formează partiţia.
Vom nota o tăietură prin T = (V,W), convenind ca mulţimea scrisă pe prima poziţie să conţină nodul iniţial s al reţelei iar cea scrisă pe a doua, nodul final t.
Definiţia 6: Se numeşte capacitate a unei tăieturi T = (V,W) într-o reţea de
transport G(X,U), notată C(T), suma capacităţilor tuturor arcelor care au extremitatea iniţială în V şi cea finală în W.
C(T) = Pentru a nu exista nici o ambiguitate, insistăm asupra faptului că se vor lua în
considerare doar arcele care trec de la mulţimea ce conţine nodul iniţial spre mulţimea care conţine nodul final, adică în sensul normal de transport (surse destinaţie).
Definiţia 7: Se numeşte tăietură de valoare minimă într-o reţea o tăietură T
în această reţea, cu proprietatea că, pentru orice altă tăietură T' în această reţea, avem C(T) C(T').
Următoarele teoreme fac legătura matematică dintre fluxurile unei reţele şi
tăieturile sale: Teorema 1. Dată o tăietură T = (V,W) şi un flux într-o reţea de transport
avem:
78
= � sau, altfel spus, valoarea unui flux oarecare este egală cu suma fluxurilor arcelor care trec de la V la W din care se scade suma fluxurilor arcelor care trec invers, de la W la V, oricare ar fi tăietura T = (V,W).
Demonstraţie: Avem succesiv:
= = + =
= + - = �
Corolar: Într-o reţea de transport valoarea oricărui flux este mai mică sau egală decât valoa-rea oricărei tăieturi.
Demonstraţie: Fie T o tăietură oarecare şi un flux oarecare. Avem succesiv:
= � = C(T) Corolar: Într-o reţea de transport valoarea fluxului maxim este mai mică sau
egală decât valoarea tăieturii minime.Demonstraţia e evidentă. În plus, din cele de mai sus se vede că egalitatea are
loc numai dacă, pentru tăietura minimă, există un flux pentru care toate arcele de la V la W sunt folosite la maxim (fluxul e egal cu capacitatea arcelor) iar pe toate arcele de la W la V nu se transportă nimic.
Teorema lui Ford-Fulkerson Dacă fluxul este maximal atunci există o
tăietură de capacitate egală cu valoarea fluxului. Demonstraţie: Fie un flux maximal. Introducem următorul procedeu de
marcare a vârfurilor:Pasul 1. Se marchează nodul iniţial s cu 0(zero);Pasul 2. Pentru fiecare vârf marcat xi se marchează cu:
79
[+xi] toate vârfurile nemarcate xj pentru care există arcul (xi,xj) şi (xi,xj) < c(xi,xj) (adica nodurile spre care mai e loc pentru a se transporta ceva din xi);
[x� i] toate vârfurile nemarcate xj pentru care există arcul (xj,xi) şi (xj,xi) > 0 (adică toate nodurile spre care pleacă deja ceva din x i);
Pasul 3. Se repetă pasul 2 până nu mai poate fi marcat nici un vârf. Dacă vârful final t ar fi marcat, atunci începând de la acesta, am putea construi
lanţul , , ..., unde = s, = t şi marcajul oricărui vârf este + sau
� . Adăugând la fluxul fiecărui arc al lanţului de tipul ( , ) valoarea:
= min( , )
şi scăzând din fluxul fiecărui arc de tipul ( , ) aceeaşi valoare , obţinem un flux de valoare + , deci fluxul nu ar fi maximal.
În concluzie vârful t nu va fi marcat. Fie tăietura T = (V,W), unde V este formată din mulţimea nodurilor marcate iar W din cele nemarcate. În acest caz, pentru fiecare arc (xi,xj) care "traversează" tăietura avem:
dacă xi V atunci (xi,xj) = c(xi,xj) deoarece nodul xj nu e marcat dacă xi W atunci (xi,xj) = 0 deoarece nodul xi nu e marcat În acest caz avem:
C(T) = = � = şi teorema e demonstrată.
Teorema lui Ford-Fulkerson poate stabili doar valoarea fluxului maxim dar nu
dă o metodă de găsire a acestuia. Pentru a rezolva problema găsirii fluxului de valoare maximă se poate folosi algoritmul lui Ford-Fulkerson.
Pentru expunerea acestuia vom introduce şi noţiunile de:
arc saturat = un arc pe care fluxul este egal cu capacitatea;drum complet = un drum de la nodul iniţial s la nodul final t care conţine cel puţin un arc saturat;flux complet = un flux pentru care orice drum de la nodul iniţial s la nodul final t este complet.
Algoritmul lui Ford-Fulkerson ETAPA I Se determină un flux complet.
80
Pasul 1. Se numerotează nodurile reţelei de transport astfel încât x1 = s şi xn = t;Pasul 2. Se asociază grafului fluxul nul (u = 0 pentru orice arc u din graf);Pasul 3. În ordine lexicografică, se ia pe rând fiecare drum D de la nodul iniţial la cel
final, se calculează valoarea D = şi se adaugă la fluxul de pe fiecare arc al drumului. Arcul(arcele) unui drum D pentru care s-a obţinut valoarea minimă D va fi după această adăugare, în mod evident, saturat şi deci drumul D va fi complet.
După epuizarea tuturor drumurilor se obţine un flux complet, de
valoare = . Deoarece alegerea drumurilor în ordine lexicografică nu ţine cont de structura reţelei, aşa cum se poate vedea pe un exemplu, acest procedeu nu asigură întotdeauna găsirea fluxului maxim. Acest impediment poate fi depăşit fie prin găsirea unei ordini de parcurgere a tuturor drumurilor, care să dea pentru fiecare reţea fluxul maxim, în urma procedeului de mai sus, fie prin redistribuirea judicioasă a fluxului găsit la etapa I. A doua variantă este cea care se aplică la etapa II.
ETAPA II Se determină fluxul maxim
Pasul 4. Se marchează nodul iniţial s cu 0(zero);Pasul 5. Pentru fiecare vârf marcat xi se marchează cu:
[+xi] toate vârfurile nemarcate xj pentru care există arcul (xi,xj) şi (xi,xj) < c(xi,xj) (adica nodurile spre care mai e loc pentru a se transporta ceva din xi);
[x� i] toate vârfurile nemarcate xj pentru care există arcul (xj,xi) şi (xj,xi) > 0 (adică toate nodurile spre care pleacă deja ceva din x i);
Pasul 6. Se repetă pasul 5 până este marcat nodul final sau până când nu mai poate fi marcat nici un vârf;
Pasul 7. Dacă nodul final a fost marcat atunci fluxul este maxim şi algoritmul se opreşte, în caz contrar trecându-se la pasul 8;
Pasul 8. Construim un lanţul L = , , ..., unde = s, = t şi marcajul oricărui vârf este + sau � . Se calculează:
L = min( , )
care se adaugă la fluxul fiecărui arc al lanţului de tipul ( , ) şi se scade din fluxul fiecărui arc de tipul ( , ).
Pasul 9. Se şterge marcajul şi se reia algoritmul de la pasul 4.
În final, tăietura de valoare minimă este cea în care V = mulţimea nodurilor marcate iar W = mulţimea nodurilor nemarcate.
81
Observaţia 1. Algoritmul nu asigură întotdeauna găsirea fluxului maxim, deoarece se poate ca creşterea fluxului la fiecare iteraţie să se facă cu cantităţi din ce în ce mai mici astfel încât suma lor să nu atingă niciodată marginea superioară dată de valoarea tăieturii minime, algoritmul având o infinitate de paşi. Teorema de mai jos dă o condiţie suficientă pentru ca algoritmul să se termine într-un număr finit de paşi:
Teoremă Dacă toate capacităţile rutelor reţelei sunt numere raţionale atunci algoritmul lui Ford-Fulkerson are un număr finit de paşi.
Demonstraţie Prin înmulţirea tuturor acestor capacităţi cu cel mai mic multiplu
comun al numitorilor se obţine o reţea cu toate capacităţile numere naturale. Ţinând cont de formula de calcul, la fiecare iteraţie cantitatea adăugată va fi număr natural şi cum valoarea fluxului maxim este mărginită de capacitatea tăieturii minime Cmin, care este de asemenea număr natural, algoritmul va avea nevoie de cel mult C min paşi pentru a o atinge.
Observaţia 2. Teorema de mai sus asigură doar o limitare superioară a
numărului de iteraţii ale algoritmului, faţă de capacitatea tăieturii minime. Această valoare poate fi însă, în anumite cazuri, foarte mare şi, dacă nu se iau precauţii suplimentare, algoritmul nu va da soluţia în timp util. Depăşirea acestei situaţii este asigurată de următoarea teoremă:
Teoremă Dacă la fiecare iteraţie se alege drumul (lanţul) de lungime minimă
atunci algoritmul va avea cel mult mn iteraţii, unde n = numărul de noduri iar m = numărul de muchii.
Observaţia 3. Există probleme în care se doreşte găsirea fluxului minim într-o
reţea, valorile fluxului pe arce fiind limitate inferior de capacităţile acestora. În acest caz se aplică de asemenea algoritmul lui Ford-Fulkerson astfel:
Pasul 1. Se calculează M = maximul capacităţilor arcelorPasul 2. Se construieşte reţeaua R', care este fosta reţea, în care au fost
modificate doar capacităţile arcelor, acestea devenind = M c� u
Pasul 3. Se găseşte cu algoritmul Ford-Fulkerson fluxul , de valoare maximă, în această reţea
Pasul 4. Fluxul de valoare minimă în reţeaua iniţială va avea valorile ' = M �
Observaţia 4. Există şi alte tipuri de probleme asemănătoare celor de mai sus.
Astfel, se poate pune problema:
82
găsirii capacităţilor minime ale arcelor cu care se poate asigura transportarea întregii cantităţi de la surse la destinaţii
fluxului minim(maxim) într-o reţea în care capacităţile rutelor sunt limitate atât superior cât şi inferior;
În cazul în care rutelor li se asociază şi costuri unitare de parcurgere, putem căuta fluxul maxim de cost minim;
83
