LECŢIA 1. - GRAFURI CU ARCE VALORIZATE. DRUM
DE LUNGIME MINIMĂ
3.1 Noţiuni introductive. Punerea problemei
Unele procese şi fenomene practice pot fi modelate prin grafuri ale căror
arce trebuie valorizate. Aceasta înseamnă că fiecărui arc i se ataşează o valoare
numerică a cărei semnificaţie concretă diferă în raport cu natura problemei
modelate; de exemplu, aceasta poate fi de tip cost, distanţă, consum, durată,
productivitate, probabilitate etc.
Exemple
a) Dacă se pune problema efectuării unor transporturi între diferite
localităţi, legate printr-o reţea de drumuri, se poate modela această problemă
printr-un graf ale cărui vârfuri sunt localităţi. Un drum între localităţile x şi y se
va reprezenta prin arcul x, y Dacă pe acest drum circulaţia se face în ambele
sensuri, în graf va exista şi arcul y, x Dacă se studiază problema din punct de
vedere al timpului necesar efectuării transporturilor, atunci fiecărui arc i se va
ataşa un număr pozitiv reprezentând durata transportului pe drumul căruia i s-a
asociat acel arc. Putem întâlni situaţii diverse după cum se prezintă în exemplele
următoare:
Durata transportului de la x la y este
de 10 unităţi;
şi arcul y, x şi are aceeaşi
valoare cu arcul x, y ;
ambele arce x, y şi y, x ,
dar au valori diferite; obligatoriu
figurează ambele arce.
După ce se reprezintă întregul graf se poate rezolva problema următoare:
Să se determine traseul pentru efectuarea unui transport între două localităţi
astfel încât timpul necesar să fie minim.
b) Dacă se studiază problema din punct de vedere al costului
transportului, valorile arcelor vor avea altă semnificaţie (costul transportului de
la x la y) şi drumurile optime în rezolvarea unei probleme de tipul:
„determinarea traseului pentru efectuarea unui transport de cost minim între
două localităţi”, vor fi altele.
Fig. 3.1.1
78
c) În alte aplicaţii se pot întâlni şi alte semnificaţii ale valorilor arcelor.
Definiţia 3.1.1
Fiind dat un graf G X,, X x1, x2, , xn, fie U mulţimea arcelor
sale. Fiecărui arc u xi , xj U i se ataşează un număr nenegativ, notat cu
u sau xi , xj , care se va numi valoarea arcului u. Definim valoarea
drumului 1 2
Vom studia algoritmi pentru determinarea drumurilor optime (drumuri de
valoare maximă sau de valoare minimă) între două vârfuri ale grafului.
Deoarece într-un graf cu circuite pot exista drumuri de valoare oricât de
mare (obţinute prin parcurgerea repetată a unui circuit), drumuri de valoare
maximă se caută, de regulă, în grafuri fără circuite. Drumuri de valoare minimă
se caută şi în grafuri care au circuite.
Observaţia 3.1.2
Drumul de valoare minimă între două vârfuri ale unui graf este un drum
elementar (nu conţine un circuit ca subdrum).
Exemplu
Fie drumul xi , , xk , , x , , xj
Fig. 3.1.2
Acest drum de la xi la x j nu poate fi de valoare minimă, deoarece el
conţine subdrumul xi , , xk , , xj , care are valoare mai mică decât drumul
, în ipoteza reală de altfel, că circuitul xk , , x , , xk are cel puţin un arc de
valoare nenulă.
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.