Matematică discretă

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ă.