| CATEGORII DOCUMENTE |
| Astronomie | Biofizica | Biologie | Botanica | Carti | Chimie | Copii |
| Educatie civica | Fabule ghicitori | Fizica | Gramatica | Joc | Literatura romana | Logica |
| Matematica | Poezii | Psihologie psihiatrie | Sociologie |
GRAFURI
Grafuri neorientate
Definitie. Un graf
neorientat este definit de perechea ordonata 
unde 
este o multim finita, nevida de elemente
numite noduri sau varfuri, iar 
este o multime de perechi de elemente ale lui, numite muchii
sau arce.
Graful poate fi descris in plan printr-o figura in care nodurile sunt reprezentate prin puncte, iar muchiile prin segmente de dreapta sau arce de curba.
Fie 
. O muchie este o submultime cu doua
elemente din ,
deci are forma
unde 
.
Virfurile 
se numesc extremitatile muchiei.
Intrun graf neorientat notatia 
reprezinta aceeasi muchie deoarece nu este
stabilit un sens de parcurgere.
Multe realitati din jurul nostru se pot reprezenta prin grafuri : reteaua cailor de transport intre localitatile unei tari (localitatile sunt reprezentate prin noduri, iar soselele prin muchii), sustemul energetic, sistemul de comunicatii etc.
Ploiesti Brasov
Bucuresti Sibiu
Pitesti Rm. Valcea
|
Fig.FF
Figura 1
* * * * * *
Furnizor Depozit Sectia 2 Asamblare Control Beneficiar
*
Sectia 3
Figura 2
X2 X5 * *
X1 *
* *
X3 X4
Figura 3
Observatie Prin reprezentarea unor retele sau sisteme sub forma unor grafuri avem avantajul ca le putem studia mai usor, utilizand tehnica modelarii matematice si/sau simularii.
Definitie. Se spune ca varfurile sunt adiacente daca 
si se numesc incidente cu muchia
Altfel spus, doua varfuri sunt adiacente daca sunt extremitatile aceluiasi arc.
Gradul unui nod 
, notat 
este egal cu numarul muchiilor incidente lui . Daca 
atunci nodul este izolat, iar daca 
atunci nodul este terminal.
Definitie. Un graf se numeste complet daca oricare doua noduri ale sale sunt adiacente.
De exemplu, graful din figura 3 este complet.
Propozitie. Pentru un graf cu n noduri si m muchii are loc relatia :
Demonstratie. Fiecare muchie se numara de doua ori, cate o data pentru fiecare din nodurile sale.
Definitie. Se numeste subgraf al grafului 
un graf 
, unde 
iar 
este formata din
muchiile lui 
care unesc varfuri din 
.
Definitie. Se numeste lant, o succesiune de varfuri 
cu proprietatea ca
oricare doua varfuri vecine sunt adiacente, adica 
.
Varfurile 
si 
se numesc extremitatile lantului.
Definitie. Un lant ale carui varfuri sunt toate distincte, se numeste lant elementar.
Exemple. Fie grafurile :
Lanturile :
sunt elementare,deoarece contin numai varfuri distincte.
Lanturile 
nu sunt
elementare.
Definitie Se numeste ciclu, un lant in care primul vtrf coincide cu ultimul si toate muchiile sunt distincte.
Definitie. Un ciclu se numeste elementar, daca toate varfurile sale, cu exceptia primului si ultimului varf, sunt distincte.
Exemplu Fie graful neorientat :
este ciclu elementar.
nu este
ciclu elementar deoarece foloseste de doua ori muchia 
nu este ciclu elementar deoarece varful 
, care este primul si ultimul varf, mai apare o
data.
Definitie Un graf se numeste conex daca pentru oricare doua varfuri distincte ale grafului exista un lant avand ca extremitati acele varfuri.
X3
X1
X4 X5 X6 X5 X4
Graful nu este conex Graful este conex
Observatie. In cazul unui graf care nu este conexse poate pune problema determinarii componentelor sale conexe.
O componenta conexa se defineste ca un subgraf conex maximal.
 |
 |
 |
 |
 |
 |
 |
|
 |
 |
|
|
|
|
|
|
|
|
|
X1 X2 X3 X2 X3 X1 X4 X5 X6 X5 X4 Graful nu este conex Graful este conex Observatie In cazul unui graf
care nu este conex se poate pune problema determinarii componentelor sale
conexe. O componenta conexa se defineste ca un subgraf conex maximal.
Exemple
Grafuri orientate
Definitie. Un
graf orientat este definit de perechea ordonata unde este o multim finita, nevida de elemente
numite noduri sau varfuri, iar este o multime de
perechi ordonate, elemente distincte ale lui numite muchii sau arce.
Fie 
cu 
si 
Varful se numeste extremitatea initiala a arcului 
, iar 
se numeste extremitatea finala a arcului
Observatie In cazul grafurilor neorientate 
si 
reprezinta acelasi arc; in cazul grafurilor
orientate reprezinta arce diferite.
Un graf orientat are arcele reprezentate prin sageti orientate de la extremitatea initiala spre extremitatea finala a arcului respectiv.
Exemplu Graful orientat unde
Definitie. Se numeste graf partial al unui graf orientat
, un graf 
, daca 
Definitie. Se numeste subgraf al grafului orientat, un graf 
, daca 
Definitie. Un graf orientat se numeste complet daca oricare doua varfuri ale sale sunt adiacente (sunt legate printr-un arc).
Observatie. In cazul grafurilor orientate, notiunilor de lant si ciclu le corespund notiunile de drum si circuit.
Exemplu.
este drum
nu este drum
este circuit
nu este circuit.
Definitie. Un graf se numeste simetric daca pentru fiecare peeche de
varfuri din pentru care
exista arcul in , graful contine si
arcul
Exemplu. Graf simetric
X1 *
X2 * * * ** X3 X4
Definitie. Se numeste bucla un arc ale carui extremitati (initiala si finala) coincid.
Exemplu.
Definitie. Se numeste drum, un sir de varfuri 
cu
proprietatea ca 
Definitie. Un drum se numeste elementar daca toate varfurile sale sunt distincte.
Definitie Se numeste circuit un drum ale carui extremitati coincid, iar arcele sale sunt distincte.
Definitie Se numeste circuit elementar un circuit ale carui varfuri sunt distincte, cu exceptia extremitatilor.
Exemplu. Fie graful
acest lant este un drum.
este un drum elementar.
este un circuit elementar.
este un drum neelementar.
este uncircuit neelementar.
Definitie. Un graf (orientat sau neorientat) se numeste conex daca pentru oricare doua varfuri distincte ale grafului exista un lant avand ca extremitaai acele varfuri.
Definitie. Un graf orientat se numeste semi-tare conex daca
oricare ar fi doua varuri ale grafului exista cel putin un drum orientat
de la la sau de la la
Definitie. Un graf orientat se numeste tare conex daca oricare
ar fi doua varuri ale grafului exista cel putin un drum de la la si cel putin un drum de la la
Exemple.
Graf conex Graf semi-tare conex Graf tare conex
Definitie. Un drum intr-un graf se numeste hamiltonian daca trece
prin toate varfurile grafului dat o singura data.
Matrice asociate unui graf
Pentru a fi mai usor de studiat, adeseori grafurilor li se asociaza matrice, care au avantajul ca faciliteaza studiul proprietatilor grafului.
Matricea conexiunilor(tranzitiilor):
, 
Este o matrice booleana care are valoarea 1 daca in graf exista arcul si 0 in caz contrar.
Exemplu.
Matricea ponderilor(capacitatilor)
unde 
este ponderea arcului respectiv.
Matricea ponderilor difera de matricea conexiunilor prin aceea ca in locul lui 1 se pune ponderea arcului respectiv.
Matricea latina
, 
Matricea latina contine pozitiile varfurilor conectate prin arcul respectiv.
Matricea de incidenta
Matricea de incidenta 
se asociaza unui graf cu n varfuri si m arce,
avand n linii si m coloane, astfel incat elementul 
este 1, -1
sau 0 dupa cum varful este extremitatea initiala a arcului de rang
j, extremitatea finala a arcului de rang j sau nu apartine arcului de rang j.
X2 a1 a2 a3 a4 a5 a6 a7
X1 +1 -1 0 0 0 0 0
X2 -1 0 -1 +1 +1 0 0
X1
X3 0 0 0 0 -1 -1 0 X3
X4 0 0 0 -1 0 +1 -1
X5 0 +1 +1 0 0 0 +1
X5 X4
Exemplu.
Matricea drumurilor
, 
Aceasta matrice este patraatica, avand ordinul egal cu numarul varfurilor
grafului. Elementele 
sunt egale cu 1 daca
exista un drum intre si ; in caz contrar sunt egale cu 0.
Exemplu.
1.4. Drumuri de valoare optima
Rezolvarea problemelor care se pot reprezenta sub forma unor grafuri se reduce la determinarea drumurilor maxime sau minime.
Algoritmul lui Ford
Fie 
un graf in care arcele
au valorile 
Se pune problema
determinarii drumului de valoare minima de la un varf 
la 
. Fiecarui varf al grafului i se
asociaza un marcaj reprezentand valoarea unui drum arbitrar de la 
la , notat l
.
Pentru un arc al
grafului 
se pot prezenta trei
situatii:
Xj
Xh
Xk
a)
b)
c)
Din a) rezulta ca
ceea ce inseamna ca
drumul direct de la la are o valoare mai mica decat drumul de la prin la .
Din b) rezulta ca
ceea ce inseamna ca
cele doua drumuri au aceeasi valoare.
Din c) rezulta ca
drumul de la prin la are o valoare mai mica decat drumul direct la .
Cautand drumulde
valoare minima constatam ca in situatia c) exista un drum 
de valoare mai mica
decat cea initiala.
Marcajul varfului
poate fi modificat,
astfel:
Dupa un numar finit de asemenea comparatii, lund in consderatie celelalte
varfuri ale grafului, se obtine valoarea minima a drumurilor de la la .
Algoritmul lui Ford pentru determinarea drumului de valoare minima intre
varfurile si ale unui graf finit este o operatie secventiala desfasurata in
urmatoarele etape :
Fiecarui varf al grafului ise asociaza un
marcaj 
reprezentand valoarea
unui drum arbitrar de la la . In particular 
Se compara diferentele dintre marcajul
varfului final si marcajul varfului initial pe fiecare arc 
cu valoarea arcului 
si se modifica
marcajul varfului final, astfel:
Procedeul continua pana cand dupa s ajustari ale marcajului varfurilor se obtin numai inegalitati de forma:
In acest moment, 
este valoarea minima a
drumurilor de la la . Pentru identificarea
varfurilor prin care trece drumul de valoare minima din iteratia s se aleg
relatiile satisfacute prin egalitati, parcurgand graful de la la .
Fie
Adunand aceste egalitati membru cu membru se obtine:
si cum 
este valoarea minima a
drumurilor intre si , acest drum este
Exemplu. Sa se determine
drumul de valoare minima intre si 
in graful urmator:
Alegem:
lungimea unor drumuri arbitrare.
Consideram tabelul:
|
|
|
|
|
|
|
|
3 |
3 |
3 |
3 |
|
|
2 |
2 |
2 |
2 |
|
|
3 |
3 |
3 |
3 |
|
|
1 |
-1 |
-1 |
-1 |
|
|
3 |
3 |
3 |
3 |
|
|
2 |
2 |
0 |
0 |
|
|
2 |
1 |
1 |
1 |
|
|
1 |
3 |
1 |
(1) |
|
|
4 |
4 |
4 |
4 |
|
|
3 |
3 |
3 |
3 |
|
|
2 |
2 |
1 |
0 |
|
|
5 |
1 |
3 |
|
|
|
3 |
3 |
4 |
3 |
|
|
5 |
0 |
0 |
0 |
|
|
1 |
2 |
1 |
0 |
Drumul minim este
Tema de casa.
Metoda drumului critic
Teoria grafurilor are aplicatii in diverse ramuri de activitate. De exemplu, o lucrare complexa la a carei realizare concura mai multe activitati se poate reprezenta printr-un graf orientat care descrie esalonarea in timp si interconditionarea actiunilor necesare. Intr-un asemenea graf arcele indica etapele sau activitatile elementare ale lucrarii respective. Fiecarui arc i se asociaza o valoare care reprezinta durata realizarii activitatii asociate arcului respectiv, exprimata in unitati de timp sau alte unitati de masura. Extremitatea initiala a unui arc reprezinta momentul inceperii activitatii, iar extremitatea finala momentul terminarii activitatii.
Exemplu.
Inceperea activitatii este marcata de nodul sau varful A, iar terminarea ei de varful H.
Activitatile reprezentate de arcele (BC) si (BD) sau (DE) si (DF), (FG) se desfasoara in acelasi timp.
Un graf de activitati are proprietatea ca nu contine circuite, deoarece o activitate incepe dupa terminarea celei precedente. In cazul circuitelor o activitate incepe dupa terminarea ei insasi.
Drumul critic este acela care se obtine ca insumare a tuturor timpilor si are lungimea maxima.
Drumul critic reuneste activitati de a caror realizare la timpul prevazut depinde realizarea la timp a intregii lucrari.
Se considera un graf de activitati G, ale carui varfuri reprezinta
evenimentele 
.
Presupunem ca 
reprezinta inceputul
lucrarii si 
reprezinta terminarea
ei. Pentru a calcula datele de realizare ale diferitelor evenimente 
, trebuie sa determinam cele mai lungi drumuri in graf de la la celelalte varfuri , pentru a fi siguri ca toate operatiile anterioare
evenimentului au fost terminate.
Lungimea maxima a drumurilor de forma 
din graful de activitati se noteaza cu 
si se numeste data
asteptata a evenimentului .
De exemplu, data asteptata a evenimentului B este 
deoarece exista un
singur drum de 
.
Pentru fiecare eveniment este util sa cunoastem
data sa limita de realizare, notata cu 
, data a carei depasire va determina intarzierea intregii
lucrari.
Data limita a evenimentului se obtine scazand din 
pe .
De exemplu,
, 
, 
Data se numeste data cea
mai apropiata, iar se numeste data cea
mai tarzie a evenimentului .
Intervalul 
se numeste interval de
fluctuatie.
Daca notam cu 
varfurile grafului G,
in care marcheaza inceperea
activitatilor, iar reprezinta terminarea
tuturor activitatilor, atunci vom nota prin 
durata activitatii
reprezentate de arcul al lui G.
Notam cu 
predecesorii lui,
adica multimea varfurilor de la care pleaca arce care au extremitatea finala in
, iar 
succesorii lui , adica multimea varfurilor catre care pleaca arce care au
extremitatea initiala in .
Cu aceste notatii, determinarea momentelor si respectiv corespunzatoare
evenimentului reprezentat de varful 
al grafului G, se
poate obtine astfel:
unde 
reprezinta momentul
inceperii lucrarii, iar 
reprezinta momentul
terminarii lucrarii.
Exemplu. Sa se determine drumul critic in urmatorul graf:
, 
, 
, 
, 
Data terminarii lucrarii
Calculam datele limita:
, 
Evenimentele pentru care 
se numesc evenimente
critice din graful activitatilor.
In exemplul de mai sus toate evenimentele sunt critice, cu exceptia evenimentului 2.
Arcele critice compun drumul sau drumurile critice ale activitatilor.
In exemplul de mai sus, drumul critic este (1,3,4,5,6).
|
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 1733
Importanta: 
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved
