Grafuri neorientateCOLEGIUL NAIONAL TEFAN CEL MARE, TRGU NEAM

Grafuri neorientateLucrare pentru atestarea competenelor profesionale la informatic

Profesor coordonator, Elev,Savescu Andrei - Sergiu Clasa a XII-a RD

2015CUPRINS

1.Introducere. Elemente de teorie32.Componente conexe53.Tipuri de grafuri6a)Grafuri Hamiltoniene6b)Grafuri euleriene6c)Graf partial si subgraf7d)Graf complet si graf bipartit74.Parcurgerea grafurilor8a)Parcurgerea in latime (BF-Breath First)8b)Parcurgerea in adancime (DF-Depth First)145.Conexitate15

Grafuri neorientate

1. Introducere. Elemente de teorieInformaticaestestiinta procesarii sistematice a informatiei.inspecial a procesarii cu ajutorul calculatoarelor. Istoric, informatica s-a dezvoltat ca stiinta din matematica, in timpce dezvoltarea primelor calulatoare isi are originea in electrotehnica si telecomunicatii.De aceea, calculatorul reprezinta doar dispozitivul pe care sunt implementate conceptele teoretice.Informaticianul olandez Edsger Dijkstra afirma: In Informatica ai de-a face cu calculatorul, cum ai in astronomie cu telescopul.Termenul de informatica provine din alaturarea cuvintelor informatie si matematica.Alte surse sustin ca provine din combinatia informatie si automatica.Istoria stiintei calculatoarelor precede momentul aparitiei computerului digital. Inainte de anul 1920, termenul de computer sereferea ,inlimbaengleza, la un o persoana care efectua calcule (un functionar). Primii cercetatori in ceea ce avea sa se numeasca stiinta calculatoarelor, cum sunt Kurt Gdel, Alonzo Church si Alan Turing, au fost interesati de problema computationala: ce informatii ar putea un functionar uman sa calculeze avand hartie si creion, prin urmarirea pur si simplu a unei liste de instructiuni, atat timp cat este necesar, fara sa fie nevoie ca el sa fie inteligent sau sa presupuna capacitati intuitive. Una din motivatiile acestui proiect a fost dorinta de a proiecta si realiza masini computationale care sa automatizeze munca, deseori plictisitoare si nu lipsita de erori, a unui computer uman.In perioada anilor 1940, cand masinile computationale au cunoscut o evolutie accelerata, termenul de computer si-a modificat semnificatia, referindu-se de acum mai degraba la masini, decat la predecesorii sai umani.

Informatica se divide in urmatoarele domenii fundamentale: informatica practica informatica teoretica tehnicaPe langa cele trei domenii mai exista si inteligenta artificiala considerata o interdisciplina de sine statatoare.Informatica teoretica se ocupa cu studiul teoriei limbajelor formale, respectiv automatica, teoria computationala si complexitatii,criptologie, logica,teoria grafurilor s.a.m.d punand bazele pentru construirea compilatoarelor pentru limbajele de programare si pentru formalizarea problemelor din matematica. Eaeste, prin urmare, coloana vertebrala a informaticii.In matematica si informatica, teoria grafurilor studiaza proprietatile grafurilor.Grafurile:Definitie: Numim graf o pereche ordonata de multimi, notata G=(X,U), unde X este o multime finita si nevida de elemente numite noduri sau varfuri, iar U este o multime de perechi (ordonate sau neordonate) de elemente din X numite muchii (daca sunt perechi neordonate) sau arce (daca sunt perechi ordonate). In primul caz, graful se numeste neorientat, altfel acestaesteorientat.

Asadarungraf poate fi reprezentat sub forma unei figuri geometrice alcatuite din puncte (care corespund varfurilor) si din linii drepte sau curbe care unesc aceste puncte (care corespund muchiilor sau arcelor).

Grafurile au o importanta imensa in informatica, de exemplu: inunele problemele de sortare si cautare elementele multimii pe care se face sortarea sau cautarea se pot reprezenta prin noduri intr-un graf; schema logica a unui program se poate reprezenta printr-un graf orientat in care o instructiune sauunbloc de instructiuni este reprezentat printr-un nod, iar muchiile directionate reprezinta calea de executie; in programarea orientata pe obiecte, ierarhia obiectelor (claselor) unui program poate fi reprezentata printr-un graf in care fiecare nod reprezinta o clasa, iar muchiile reprezinta relatii intre acestea (derivari, agregari).

2. Componente conexe:FieG=(V, E)un graf neorientat, unde V are n elemente (n noduri) si E are m elemente (m muchii).Definitie: G1=(V1, E1) este o componenta conexa daca: pentru orice pereche x,y de noduri din V1exista un lant de la x la y (implicit si de la y la x) nu exista alt subgraf al lui G, G2=(V2, E2)care sa indeplineasca prima conditie si care sa-l contina peG1

Observatie: subgraful 1, 2, 3, 4 nu este componenta conexa ( chiar daca pentru orice pereche x,y de noduri exista un lant de la x la y) deoarece exista subgraful 1, 2, 3, 4, 5 care il contine si indeplineste aceeasi conditie.Definitie: Un graf G=(V, E) este conex daca pentru orice pereche x,y de noduri din V exista un lant de la x la y (implicit si de la y la x).Observatii: Un graf este conex daca admite o singura componenta conexa. Graful anterior nu este conex pentru ca admite doua componente conexe. Graful urmator este conex:

3. Tipuri de grafuri:a) Grafuri HamiltonieneDefinitie: Se numesteciclu hamiltonianun ciclu elementar care contine toate varfurile grafului.Definitie: Un graf se numestehamiltoniandaca are cel putin un ciclu hamiltonian.Teorema: Fie G=(X,U) ungraf.Dacagradul fiecarui varf este >=n/2 atunci graful este hamiltonian.Observatie: Conditia din teorema este necesara,dar nu si suficienta.Aplicatie: Ciclurile hamiltoniene sunt legate de problema comis-voiajorului care pleaca dintr-un oras si trebuie sa treaca o singura data prin celelalte orase si sa se intoarca de unde a plecat.b) Grafuri eulerieneDefinitie: Un ciclu se numeste eulerian daca trece o singura data prin toate muchiile.Observatie: Un graf se numeste eulerian daca are un ciclu eulerian.Teorema: Un graf fara varfuri izolate se numeste eulerian daca si numai daca este conex si gradul fiecarui varf este par.Observatie: Dintre grafurile complete sunt euleriene cele cu numar impar de varfuri.c) Graf partial si subgrafDefinitie: Fie graful G=(X,U).Ungraf partialal lui G,este un graf G1=(X,V) ,cu VU(inclus).Altfel spus ,un graf partial se obtine pastrand toate varfurile si eliminand niste muchii.Definitie: Fie graful G=(X,U).Unsubgrafal lui G,este un graf S=(Y,T),unde YX si TV,iar T va contine numai acele muchii care au ambele extremitati in Y.Altfel spus,un subgraf S al lui G se obtine din G eliminand niste varfuri si odata cu acestea acele muchii care au cel putin o extremitate in submultimea eliminata.

d) Graf complet si graf bipartitDefinitie: Se numestegraf completcu n varfuri,notat K indice n (Kn),un graf G=(X,U) cu proprietatea ca oricare doua varfuri sunt adiacente,adica oricare cuplu x,y X,esista muchia [x,y] U.Teorema: Un graf complet cu n varfuri are n(n-1)/2 muchii.Definitie: Se numestegraf bipartit,un graf G=(X,U) cu proprietatea ca exista doua multimi distincte A si B incluse in X,astefel incat: AB=multime vida,A+B=X.(+ este reunit); toate muchiile grafului au o extremitate in A si cealalta in B.Definitie: Se numestegraf bipartit complet,un graf bipartit cu proprietatea ca pentru orice varf x din A si orice varf y din B , exista muchia [x,y].(A+B=X).

4. Parcurgerea grafurilor:Parcurgerea grafurilor se realizeaza cu scopul vizitarii varfurilor acestora.Fiecare varf se va vizita o singura data,cu scopul prelucrarii informatiei.Parcurgerea grafurilor poate fi: in latime in adancimea) Parcurgerea in latime (BF-Breath First)La explorarea in latime, dupa vizitarea nodului initial, se exploreaza toate nodurile adiacente lui, se trece apoi la primul nod adiacent si se exploreaza toate nodurile adiacente acestuia si neparcurse inca, s.a.m.d. Fiecare nod se parcurge cel mult odata (daca graful nu este conex nu se vor putea parcurge toate nodurile)

Algoritmul de parcurgere in latime:Se va folosi o coada in care se inscriu nodurile in forma in care sunt parcurse: nodul initial varf (de la care se porneste), apoi nodurile a,b,, adiacente lui varf, apoi cele adiacente lui a, cele adiacente lui b, ,s.a.m.d.Coada este folosita astfel: Se pune primul nod in coada; Se afla toate varfurile adiacente cu primul nod si se introduc dupa primul nod Se ia urmatorul nod si i se afla nodurile adiacente Procesul se repeta pana cand se ajunge la sfarsitul coziiGraful se va memora utilizand matricea de adiacenta a[10][10]Pentru memorarea succesiunii nodurilor parcurse se va folosi un vector c[20] care va functiona ca o coadaPentru a nu parcurge un nod de doua ori se va folosi un vector boolean viz[20] care va retine: viz[k]=0 daca nodul k nu a fost vizitat inca viz[k]=1 daca nodul k a fost vizitatDoua variabile: prim si ultim vor retine doua pozitii din vectorul c si anume: prim este indicele componentei pentru care se parcurg vecinii (indexul componentelor marcate cu rosu in sirurile parcurse anterior ). Prin urmare Varf=c[prim], este elementul pentru care se determina vecinii (nodurile adiacente) ultim este pozitia in vector pe care se va face o noua inserare in vectorul c (evident, de fiecare data cand se realizeaza o noua inserare se mareste vectorul) Vecinii nodului varf se cauta pe linia acestui varf: daca a[varf][k]=1 inseamna ca nodurile varf si k sunt adiacente. Pentru ca nodul k sa fie adaugat in coada trebuie ca nodul sa nu fi fost vizitat: viz[k]=0#include#includeint a[10][10],c[20],viz[10];int n,m,prim,ultim,varf;void bf_iterativ()//parcurgerea in latime{int k;while(primn>>m;for(int i=1;i>x>>y;a[x][y]=a[y][x]=1;}cout