|
Decizii prin teoria grafurilor
1. Aspecte conceptuale
Orice activitate manageriala are 1) un inceput, 2) derularea propriu-zisa a
actiunii si 3) un sfarsit (rezultat).
Aprecierile de mai sus se regasesc in notiunea de "graf", care - simplificat -
inseamna un arc intre origine (Po = punct de pornire) si rezultat (P1 = punct final)
(fig. 3.7).
Po
G (graf)
(arc)
P1
Fig. 3.7. Reprezentarea simplificata a unui arc de graf
Un graf poate fi orientat sau neorientat.
Considerand un graf neorientat:
G = (X, U) (3.2)
unde: X = multimea varfurilor;
U = multimea muchiilor (arcelor).
Graful poate fi descris in plan, reprezentat prin segmente care unesc
perechi de varfuri.
Lantul este o succesiune de varfuri (oricare doua varfuri consecutive ale
lantului sunt unite pentru arc).
Ciclul reprezinta un lant in care varful initial (originea) este legat de varful
final (rezultatul) printr-un arc.
Graful este conex daca oricare dintre doua varfuri se leaga printr-un lant.
Structurile arborescentei se regasesc in probleme de stocare, cautare si
localizare a informatiilor, in reprezentarea grupurilor sociale s.a.
In anumiti algoritmi de optimizare se realizeaza explorarea drumurilor care
unesc radacina cu punctele finale ale arborescentei. Drumurile sunt asociate
decizional cu anumite solutii posibile ale problemei. Multimea de solutii contine si
solutia optima.