Reprezentarea proceselor tehnologice si elemente de teorie a grafurilor

REPREZENTAREA PROCESELOR TEHNOLOGICE SI ELEMENTE DE TEORIE A GRAFURILOR

Datorita dezvoltarii considerabile a tehnologiilor de lucru, al numarului de operatii si al complexitatii relatiior de interdependenta logica dintre acestea, in ultimii ani s-a produs o importanta modificea modului de reprezentare a proceselor de productie  prin trecerea de la reprezentarea cu ajutorul diagramei Gantt la reprezentarea cu ajutorul altor sisteme, de exemplu schema bloc, graful de semnal si graful de activitati.

Schema bloc si graful de semnal sunt sisteme de reprezentare datorite in principal dezvoltarii sistemelor de reglare automata si sistemelor de retele electrice.

Teoria grafurilor constituie unul dintre capitolele cercetarii operationale care a permis imbunatatirea, respectiv optimizarea unui mai mare numar de probleme privind organizarea proceselor de productie. Pe baza reprezentarii grafice cu ajutorul grafurilor de activitati s-a reusit o mai fidea reprezentare a tehnologiilor de lucru, fapt care a permis dezvoltarea unor modele matematice dintre care cele mai importante sunt metoda drumului critic, analiza costului optim,analiza resurselor, probleme de fluxuri maxime in retele.

Se numeste graf orice aplicatie Γ a unei multimi X in ea insasi ; graful se noteaza :

G=(X,Γ)

Fig. 1

In figura 1   este reprezentat un graf in care :

a)       Nodul este un element al multimii X ; nodurile in figura 1 sunt marcate cu a, b, c, d, e, f, g si h ;. Daca doua noduri x si y sunt astfel incat y x, x,yX, se uneste nodul x cu o sageata orientata spre nodul y.

b)       Arcul este un element al unei multimi determinat de o pereche orientata (x,y) a doua noduri x si x. In figura 1 perechile (a,b), (a,c) .. sunt arce. Multimea arcelor o notam cu U.

c)       Drumul este o portiune dintr-un graf, alcatuit dintr-o succesiune de arce orientate care permit sa se treaca de la un nod la altul. In figura 1 succesiunile de arce determinate de nodurile (a,b,d,f,g,h), (a,c,f,g,h), sunt drumuri.

d)       Circuitul este un drum in care nodul initial coincide cu cel final; in figura1, (b, d, f, g, e, b) reprezinta un circuit.

e)       Bucla este un arc cu origine si extremitate comune in ace­lasi nod; in figura1, (c, c) si (g, g) sunt bucle.

f)   Muchia este un ansamblu alcatuit din doua noduri distincte intre care exista cel putin un arc orientat intr-un sens si in altul; in figura 1 intre nodurile b si e exista o muchie.

g)       Lantul este o succesiune de muchii indiferent de orientarea arcelor; in figura 1, suecesiunea de muchii determinate de nodurile (c,f, d, b) este un lant. De asemenea succesiunea (a, c,f, g, h) este un lant, dar care, fiind alcatuit din arce orientate, este in acelasi timp si un drum.

Un graf alcatuit din elementele prezentate poate fi:

conex, atunci cand intre doua noduri oarecare exista cel putin un lant ;

simetric, atunci cand multimea arcelor U contine pentru un arc (x ,x) si un arc (x,x);

antisimetric, atunci cand multimea arcelor U contine un arc (x ,x) dar nu contine si un arc (x,x

Un tip particular de grafuri sunt retelele care nu contin bucle sau circuite, au un singur nod initial si un nod final, si unde arcele sunt definite prin capacitatea  corespunzatoare.