GRAF, termen utilizat si consacrat in teoria grafelor. Teoria g. pune la dispozitie algoritmi cu care se pot determina drumuri de utilizare sau lungime optima, fluxuri maxime, ordonari de operatii, ramificatii, cuplaje, amplasari, drumuri critice, etc. in felul acesta g. a devenit un instrument de mare eficacitate in analizele de structura, ori de cite ori o structura prezinta o multime de elemente distincte si exista o lege care sa sileasca o corespondenta intre aceste elemente. Intuitiv, un g. este o ura formata diritr-o multime de puncte denumite noduri, legate intre ele prin linii sau sageti. Punctele pot simboliza elemente din cele mai diferite : localitati, intreprinderi, indivizi, evenimente, actiuni, operatiuni, in general orice multime de elemente inauntrul careia se poate sili o legatura, o anumita corespondenta. Daca notam multimile cu literele A, B . . ; iar elementele unei multimi cu a; ; i = 1, 2 . ; (Relatia a f = A aratind ca elementul a apartine multimii A) ; g. este sistemul format din : a) o multime P de elemente p|, numite virfurile sau nodurile grafului ; b) o multime U de perechi ordonate si distincte ",,, = ; Pj,PjeP, numite arcele c. Deci arcul este un cuplu de doua noduri legate prin-tr-o linie cu sageata, care indica sensul corespondentei. Un g. poate astfel sa fie definit ca o aplicatie multivoca(r) a unei multimi (X) in ea insasi, fiind reprezentat printr-o multime de puncte (noduri) si arce orientate. G. astfel definit se noteaza G = (X.T). Se numeste aplicatie a unei multimi X pe o multime Y o lege care face sa corespunda fiecarui element X e X un element bine determinat "xe y care se numeste lege de corespondenta. Corespondenta dintre aceste puncte sau noduri se reprezinta prin arce orientate. Se spune ca un g. este simplu, no-trndu-se cu (P,, P2, U), atunci cind virfurile (punctele) sale se pot imparti in doua multimi disjuncte Pi, P2 astfel ca: (pj( pj) e U-> Pje Pj si pj e P2, ceea ce inseamna ca virfurile apartinind aceleiasi multimi nu sint legate prin arce ( de exemplu . 11 a, care exprima posibilitatile de aprovizionare a unor unitati comerciale C|, C2, C3 cu produse de la furnizorii di, d2, d3). Se numeste ar un g. care poate fi reprezentat pe un , astfel ca toate virfurile sa fie distincte si arcele
sa nu se intretaie decit in extremitati (virfuri sau noduri) .
Intre notiunile utilizate de teoria grafelor sint si acelea de drum si circuit. Prin drum al unui graf (Pi U) se intelege o succesiune de arce u-i, u2. . . u p , astfel ca extremitatea finala a fiecarui arc sa coincida cu extremitatea inintiala a arcului urmator. Drumul se defineste printr-o succesiune de virfuri (P1f P2 ., Pn), cu conditia ca arcele (P,, P2), (P2, P3)
(Pn_l, Pn) sa fie ale g. Drumul poate fi compus, cind acelasi arc este folosit de doua ori, si simplu, in caz contrar. De asemenea, el poate fi elementar, daca trece de doua ori prin acelasi virf si hamiltonian, daca trece numai o singura data prin fiecare virf. Circuit al unui graf se numeste drumul in care virful initial si cel final coincid. Circuitele pot fi compuse, elementare si simple. Numarul de arce al unui drum sau circuit se considera lungimea drumului sau circuitului ; lungimea unui arc este egala cu 1. Folosirea grafelor ofera reale posibilitati de optimizare a deciziilor. Teoria grafelor sta la baza metodei drumului critic (Criticai Path Me-thod ' metoda drumului critic) ( si P.E.R.T. (Program Evaluotion and Review Technique) (.
|
