Elemente de Teoria Grafelor

Cuprins proiect Cum descarc?

INTRODUCERE 3
I. NOTIUNI DE BAZA IN TEORIA GRAFELOR 3
1. ELEMENTE INTRODUCTIVE 3
2. MATRICE ASOCIATE UNUI GRAF 6
3. DRUM, CIRCUIT, LANT, CICLU 8
4. GRAF TARE CONEX. GRAF CONEX. 
COMPONENTA CONEXA A GRAFULUI. 
ARBOBI INTR-UN GRAF 10
II. DRUMURI INTR-UN GRAF 12
1. ELEMENTE INTRODUCTIVE 12
2. DRUMUL DE LUNGIME MINIMA INTRE
DOUA VIRFURI ALE UNUI GRAF 13
3. ALGORITMI PENTRU GASIREA DRUMULUI
DE LUNGIME MINIMA SI MAXIMA DINTRE 
DOUA VIRFURI ALE UNUI GRAF 14
III. MODELE DE RETELE APLICATE IN ECONOMIE 15
1. RETELE DE TRANSPORT 15
2. FLUX INTR-O RETEA DE TRANSPORT 16
3. ALGORITMUL PENTRU DETERMINAREA 
FLUXULUI MAXIM INTR-O RETEA DE TRANSPORT 17
PROBLEME CARE CONDUC LA DETERMINAREA 
FLUXULUI MAXIM IN RETEA 18
IV. CUPLAJUL MAXIM IN RETEA 21
1. ELEMENTE INTRODUCTIVE 21
2. CUPLAJUL MAXIM 21
CONCLUZIE 23
BIBLIOGRAFIE 23


Extras din proiect Cum descarc?

INTRODUCERE
Lumea contemporana este produsul unui continuu progres, astfel creandu-se noi tehnologii si metode de modelare. In acelasi timp, insa, apar si o varietate de probleme unde se cere sa se construiasca sisteme complexe cu ajutorul unei anumite ordonari ale elementelor. Acestea sunt planificarea calendaristica a productiei, probleme logice, probleme de construire a sistemelor de comunicatii si cercetarea procesului de transmitere a informatiei, probleme de alegere a structurii grupurilor sociale, probleme din teoria jocurilor etc.
Complexitatea proceselor economice, cerintele mereu crescande ale conducerii si planificarii stiintifice a economiei intr-un avant fara precedent, impun cunoasterea solutiilor optime din punct de vedere economic, cu maximum de precizie. In solutionarea unor astfel de probleme complexe nu mai pot fi utilizate metodele empirice care pot conduce la pagube materiale considerabile, ci trebuie folosite metode matematice moderne. Se poate afirma ca in momentul de fata actiunea de folosire a matematicilor moderne se extinde cu maximum de eficienta la toate nivelele de decizie.
Grafele se intalnesc in cele mai diverse domenii de activitate, care pot fi concretizate prin scheme orientate, cum sint probleme de repartitie, probleme de planificare, conducere si control, probleme de psihologie si altele tot atat de importante.
Varietatea de situati in care apare graful a impus abstractizarea acestei notiuni, ajungindu-se in cele din urma la o disciplina de sine statatoare.
Asa se explica faptul ca astazi grafele sint folosite cu succes in discipline matematice ca algebra, calculul probabilitatilor, teoria functiilor etc.
Metodele folosite de teoria grafelor permit o solutionare intuitiva si, ca atare, usoara si rapida, a unor probleme complexe care, altfel, ar necesita operatii multiple si abstracte. Se poate spune pe drept cuvant, ca teoria grafelor poate fi folosita totdeauna in probleme in care se cere optimizarea unei actiuni.
Ca disciplina de sine statatoare, teoria grafelor s-a constituit destul de recent si cu toate acestea, datorita vastului camp de aplicabilitate, precum si datorita procedeelor eficace de investitie ce ajuta intuitia, ea aluat o mare amploare, constituind la ora actuala un instrument de lucru util pentru economisti, ingineri, tehnicieni etc.
Una primele lucrari cu referire la teoria grafelor a fost cea a lui L. Euler in vestitul rationament despre podurile din Kooenegsperg. Insa acest articol al anului 1736 al lui L. Euler a fost unicul in decursul a aproximativ o suta de ani. Interesul pentru problemele de teoria grafelor a reaparut la mijlocul secolului XIX si a fost intr-o mare parte concentrat in Anglia. Unele stiinte au influentat asupra acestui fapt datorita cercetarilor retelelor electrice, modelului cristalelor si structura moleculelor. 
Bazele teoriei grafelor ca disciplina matematica insa au fost puse de matematicianul ungar D. Kenig, autorul primei monografii in 1936, in care grafele sint redate ca obiecte matematice abstracte si in care sint depuse bazele teoriei grafelor generale. 
Primul ciclu de lectii despre relatiile binare si grafe a fost propus societatii americane matematice in decursul sesiunii de vara in Cicago in 1942. In acea perioada manuscrisele acestor lectii nu a fost pregatita pentru tiparire din cauza unor lucrari mai urgente, acestea aparand mai tarziu ca surse accesibile.
I. NOTIUNI DE BAZA IN TEORIA GRAFELOR
1. ELEMENTE INTRODUCTIVE
Grafele pot fi privite ca obiecte abstracte; studiate cu un aparat matematic propriu. Pe de alta parte; ele sunt utilizate in modelarea si studiul unor sisteme sau pentru rezolvarea de probleme din diverse domenii ale activitatii umane: informatica; economie; armata; fizica; chimie; transporturi; geografie; proiectare; etc. Teoria grafelor este atat un obiect de cercetare teoretica; cat si un furnizor de algoritmi si metode generale pentru rezolvarea unor probleme concrete (practice).Succesul depinde de capacitatea utilizatorului de a asocia problemei sale un graf si de a-si formula in termenii teoriei grafelor.
Teoria grafelor este o ramura a teoriei multimilor, destul de recenta care s-a dovedit foarte utila si cu aplicatii in domenii variate: economie, chimie organica, organizare, psihologie, anumite domenii ale artei etc. 
Exemplul 1. Sa presupunem ca se pune problema construirii unei sosele intre doua centre industriale, notate cu x0 si x11, care ar putea sa treaca prin localitatile x1, x2, x3, x4, x5, x6, x7, x8, x9, x10. Cunoscand costul lucrarii pentru portiunile de sosea care leaga intre ele diverse localitati (xi), sa se determine traseul soselei dintre localitatile x0 si x11 astfel incat cheltuielile totale pentru efectuarea lucrarii sa fie minime.
Fig. I.1.1
Daca reprezentam localitatile prin puncte, iar portiunile de sosea prin arce, atunci obtinem schema din figura I.1.1. Putem presupune ca ar fi vorba de o regiune muntoasa cu sosele inguste pe care sensul de circulatie este unic, de unde rezulta orientarea in sens unic a arcelor de pe figura.
Exemplul dat a permis asocierea unor figuri constituite din puncte si arce orientate (sageti) care unesc perechi din aceste puncte.
In sens matematic, aceste sageti pot simboliza o aplicatie F pentru care extremitatea initiala a arcului reprezinta argumentul sau variabila, iar extremitatea finala a aceluiasi arc reprezinta imaginea sau valoarea aplicatiei.
Tot din figuri reiese ca oricarui punct (sau varf) al multimii X = {xi} ii corespunde, prin aplicatia F, o submultime a aceleiasi multimi X.
Astfel, daca consideram figura I.1.2, distingem corespondentele urmatoare
Fig. I.1.2
Uneori, in aplicatii, este util sa se cunoasca semnificatia notatiei . Din exemplul de mai inainte s-a vazut ca
Prin vom intelege
Analog,
In general
Daca in figura I.1.2 se schimba sensul tuturor sagetilor, atunci se obtine imaginea reciproca F-1.
Pentru figura I.1.2 avem :
=? ; ={x1, x3}; ={x2}; ={x3}; ={x6, x7, x3}; ={x1, x5}; ={x1, x2, x7}
In general, o multime X, de puncte sau varfuri, si o aplicatie F, a multimii X in ea insasi, definesc un graf pe care-l vom nota G=(X, F). Aceasta notatie pune in evidenta atat multimea X a varfurilor cit si aplicatia F.


Fisiere in arhiva (1):

  • Elemente de Teoria Grafelor.doc

Imagini din acest proiect Cum descarc?

Banii inapoi garantat!

Plateste in siguranta cu cardul bancar si beneficiezi de garantia 200% din partea Proiecte.ro.


Descarca aceast proiect cu doar 5 €

Simplu si rapid in doar 2 pasi: completezi adresa de email si platesti.

1. Numele, Prenumele si adresa de email:

Pe adresa de email specificata vei primi link-ul de descarcare, nr. comenzii si factura (la plata cu cardul). Daca nu gasesti email-ul, verifica si directoarele spam, junk sau toate mesajele.

2. Alege modalitatea de plata preferata:



* Pretul este fara TVA.


Hopa sus!