Pagina documente » Informatica, Matematica » Aplicatii cu privire la tehnicile de parcurgere a unui graf finit

Despre lucrare

lucrare-licenta-aplicatii-cu-privire-la-tehnicile-de-parcurgere-a-unui-graf-finit
Aceasta lucrare poate fi descarcata doar daca ai statut PREMIUM si are scop consultativ. Pentru a descarca aceasta lucrare trebuie sa fii utilizator inregistrat.
lucrare-licenta-aplicatii-cu-privire-la-tehnicile-de-parcurgere-a-unui-graf-finit


Cuprins

Cuprins
Cuprins 2
Prefata 3
1 Structura de graf finit 5
1.1 Notiuni introductive 5
1.2 Implementarea pe calculator a unui graf finit 14
1.3 Conexitate 20
2 Tehnici de parcurgere a grafurilor 27
2.1 Operatii cu grafuri 27
2.2 Tehnici de parcurgere a grafurilor 31
3 Tare conexitate intr-un graf finit 38
3.1 Conexitate intr-un graf orientat 38
3.2 Tare conexitate 42
3.3 Drumuri minime in grafuri orientate 46
4 Algoritmi pentru prelucrarea grafurilor finite 47

EXTRAS DIN DOCUMENT

?Prefata

Originile teoriei grafurilor se gasesc in rezolvarea unor probleme de jocuri si amuzamente matematice, care au atras atentia unor matematicieni de seama, cum ar fi :Euler , Hamilton , Cayley , Sylvester , Birkoff .

Data nasterii teoriei grafurilor este considerata a fi anul 1736 , cand matematicianul Leonhard Euler a publicat un articol a clarificat problema celor 7 poduri si a prezentat o metoda pentru rezolvarea altor probleme de acelasi tip.Articolul, in limba latina , avea titlul :Solutio problematis ad geometriam situs pertinentis ( Solutia unei probleme legate de geometria pozitiei ) si a aparut in revista Commentarii Academiae Scietiarum Imperialis Petropolitanae.

Cu 200 sute de ani mai tarziu , in 1936 , aparea la Leipzig prima carte de teoria grafurilor , al carui autor este matematicianul maghiar Dénes König. În amintirea contributiei lui Euler , unele notiuni si tipuri de grafuri de care acesta s-a ocupat sunt denumite de catre König lant ( ciclu ) eulerian , graf eulerian , etc.

Un alt matematician care s-a ocupat de aceleasi probleme ca si Euler ( se pare , fara a cunoaste articolul ) dar care si-a publicat rezultatele cercetarilor sale in anul 1873 , a fost Carl Hierholzer .Acesta a demonstrat in plus unele rezultate care lui Euler i se parusera evidente .

În 1851 articolul lui Euler a fost tradus si publicat in revista Nuvelles Annales de Mathematiques , iar rezultatele sale au fost imbogatite , fiind studiate in clase speciale de grafuri .

Alte izvoare ale teoriei grafurilor sunt :studiul retelelor electrice , problema celor 4 culori , aplicatiile teoriei grafurilor in chimie ( intiate de Cayley ) , probleme hamiltoniene , grafuri planare , etc.

Fizicianul Kirchoff a studiat la mijlocul secolului trecut retelele electrice cu metode care apartin astazi teoriei grafurilor , contribuind la dezvoltarea acestei teorii ( in anul 1845 a formulat legile care guverneaza circulatia curentului curentului intr-o retea electrica iar in 1847 tot el a aratat cum poate fi construita intr-un graf o multime fundamentala de cicluri demonstrand ca , pentru orice graf conex cu n varfuri si m muchii , o multime fundamentala de cicluri contine intotdeauna m()n+1 cicluri ).

Termenul de graf a fost folosit pentru prima data in sensul sau actual ( fiind derivat din termenul ‘notatie grafica’ din chimie ) intr-un articol publicat in 1878 de matematicianul J.Sylvester ( prieten al lui Cayley ) , articol ce a aparut in primul numar al revistei American Journal of Mathematics.Teoria grafurilor are numeroase aplicatii in chimie , cercetari privind determinarea numarului de izomeri ai compusilor organici contribuind in mare masura la rezolvarea problemelor de numarare a grafurilor apartinand unor clase speciale .

Azi teoria grafurilor a devenit o disciplina majora , desi nu-si gaseste locul intr-o clasificare dogmatica a capitolelor matematicii .

Folosirea teoriei grafurilor in domenii variate , de la chimie la economie , de la studiul retelelor electrice la critica textelor si la politica , ii dau azi un prestigiu de care cel ce clasifica stiintele trebuie sa tina seama.

CAPITOLUL 1

Structura de graf finit

1.1 Notiuni introductive

Conceptul de graf are multe surse si puternice motivatii .El este util matematicianului , inginerului , chimistului , psihologului , economistului , informaticianului , in reprezentarea diferitelor obiecte concrete intalnite in sfera lor de activitate . Astazi , grafurile isi gasesc o utilizare curenta in rationamente de natura combinatorie in conexiune cu diferite domenii ale matematicii (teoria grupurilor , teoria numerelor , topologie, logica etc.).

Definitie : Se numeste graf neorientat o pereche ordonata (V,U) unde V este o multime finita si nevida de elemente numite varfuri ( noduri ) , iar U este o multime de perechi de elemente din V , numite muchii .

Fie G=(V,U) un graf neorientat .O muchie u?U reprezinta o submultime {x,y} de varfuri (distincte) din V si se noteaza u=[x,y] .În acest caz se spune ca :

(1) varfurile x,y sunt extremitatile muchiei u ;

(2) varfurile x,y sunt adiacente in graful G ;

(3) muchia u este incidenta varfului x respectiv y ;

(4) varful x este extremitatea initiala , iar varful y este extremitatea finala a muchiei u ;

(5) doua muchii care au o extremitate comuna se numesc incidente .

Graful neorientat reprezinta o relatie simetrica intre obiecte . Ca atare , notatiile [x,y] si [x,y] reprezinta aceeasi muchie .Daca in multimea U exista mai multe perechi identice (muchii multiple) , atunci G se numeste multigraf . Daca numarul unor astfel de perechi identice nu depaseste un numar natural p ,G se numeste p-graf.

Exemplu : În figura 1.1.1 , G=(V,U) este un multigraf , mai exact un 2-graf.

x1 x2 x3

x4 x5 x6

Fig. 1.1.1

Daca extremitatea initiala a unei muchii coincide cu cea finala , atunci se spune ca este o bucla .

Fig. 1.1.2

x

Exemplu : Iata reprezentarea in plan a grafului simplu (graf fara bucle si muchii mulltiple ) G=(V,U) , unde V={x1,x2,x3,x4,x5} , iar U={[x1,x2];[x2,x3];[x3,x4];[x4,x2];[x3,x1];[x1,x5];[x5,x4],[x3,x5]}.