...X,V, unde VX. Altfel spus, un graf G a lui G, este chiar G sau se obtine din G pastrand toate varfurile si suprimand niste muchii.Se numeste subgraf al grafului GX,U ungraf neorientat HY,V, unde YX iar V contine toate muchiile din U care au ambele extremitati in multimea Y. Reprezentarea grafurilor neorientateCele mai cunoscute forme de reprezentare ale unui astfel de graf sunt matricea de adiacenta, listele vecinilor si vectorul muchiilor.Matricea de adiacentaEste o matrice patratica cu n linii si n coloane, in care elementele aii,js se definesc astfel aii,js1 daca exista i,j in U, cu x diferit de y si 0 daca nu exista i,j in U.Pentru graful GX,U din figura de mai jos, matricea de adiacenta este linia 0 1 1 1 1 1 0 1 0 2 A 1 1 0 1 3 1 0 1 0 4 coloana 1 2 3 4aii,jsaij,is oricare ar fi i,j I1,2,..,nSProprietatile matricei de adiacentaEste o matrice simetricaPe diagonala principala are toate elemntele egale cu 0Suma elementelor pe linia sau coloana i este egala cu gradul nodului iDaca elementele pe liniacoloana i sunt toate egale cu 0 atunci nodul este izolatDaca toate elementele din matrice,mai putin cele de pe diagonala principala, sunt 1 inseamna ca graful este complet.Listele vecinilorPentru fiecare nod al grafului se retin nodurile adiacente cu el.Pentru reprezentarea listei de adiacenta se poate folosi alocare dinamica.Exemplu pentru matricea de adiacenta de mai sus nodul lista vecinilor2, 3, 41, 31, 2, 41, 3Vectorul muchiilorFiecare muchie a grafului poate fi privita ca o inregistrare cu doua componente cele doua varfuri care constitue extremitatile muchiei. Notand aceste extremitati cu nod1 si nod2, putem defini tipul de date tmuchie, astfeltype tmuchierecordnod1,nod2integerend Graful in ansamblul sau, este o multime de muchii, adica o multime de elemente de tipul tmuchie.In consecinta definim graful ca un vector de muchii, adica un vector cu elementele de tipul tmuchie var varrayi1..25s of tmuchieGraf complet si graf bipartit.Se numeste graf complet cu n varfuri, notat Kn, un graf GX,U cu proprietatea ca intre oricare doua varfuri exista o muchie.ExempluUn graf complet cu n varfuri are nn-12 muchii.Un graf neorientat GX,U se numeste bipartit daca exista 2 multimi de noduri A si BX astfel incat ABX si AB iar orice muchie din U are o extremitate in multimea A si una in multimea B.Exemplu Fie GX,U unde XI1,2,3,4,5,6,7S, UI15,26,36,47SCu multimile AI1,2,3,4S si BI5,6,7SSe obesrva ca ABX, AB, iar fiecare muchie are o extremitate in A si una in B. Se numeste graf bibartit complet, un graf bipartit cu proprietatea ca pentru orice varf x din A si orice varf y din B, exista muchiax,y unde A si B sunt cele doua submultimi care partitioneaza multimea varfurilorX.ExempluNotiunile de lant si cicluSe numeste lant in graful G, o succesiune de varfuri Lx1,x2,..,xp ,cu xi X, in care 2 noduri consecutive din succesiune sunt adiacente, adica exista muchiile x1,x2,x2,x3,.,xp-1,xpU.Varfurile x1 si xp se numesc extremitatile lantului, iar numarul de muchii care intra in componenta sa reprezinta lungimea lantului.Un lant in care 2 elemente sunt diferite se numeste lant elementar. Altfel lantul este neelementar.Exemplu Lant elementar1,2,3,4,5 6,7,3,9,4,8Lant neelementar 1,2,3,2 Un graf G este conex, daca oricare ar fi doua varfuri ale sale , exista un lant care le leaga.Se numeste ciclu intr-un graf, un lant in care extremitatile coincid si muchiile sunt diferite intre ele.Exemplu c13,4,5,3,7,6,1,2,3, c21,2,3,7,6,1, c33,5,4,9,3Daca intr-un ciclu, toate varfurile cu exceptia primului si a ultimului sunt distincte doua cate doua, atunci ciclul se numeste elementar. In caz contrar el este neelementar.Ciclurile c2 si c3 din exemplul anterior sunt elementare,iar c1 este neelementarin c1, varful 3 apare si ca varf intermediar,adica traseul descris mai trece odata prin varful 3 pe langa faptul ca porneste din el si se intoarce tot in el..Parcurgerea grafurilor neorientatePrin parcurgerea grafurilor neorientate se intelege vizitarea varfurilor intr-o anumita ordine, ordine data de un anumit criteriu.Exista doua metode de parcurgereParcurgerea in latime BFBreadth FirstParcurgerea in adancime DFDepth FirstAlgoritmul de parcurgere in latime BFFiind dat un graf neorientat GX,U si un nod xX, sa se parcurga toate varfurile grafului incepand din varful x.Metoda consta in-se viziteaza varful de pornire, dupa care se viziteaza toate varfurile adiacente cu acesta care nu au fost vizitate inca,in continuare se alege primul varf adiacent cu varful de pornire si se viziteaza toate varfurile adiacente cu acesta nevizitate inca si asa mai departe pentru celelalte varfuri cat timp este posibil.ExempluPresupunem ca varful de pornire este 1,atunci parcurgerea BF este1,2,5,6,3,4,7.Pentu 3 varf de pornire3,2,4,1,5,6,7.Pentru implementare vom folosi un vector care are proprietatile unei cozi, fie cc1,c2,,ck. Capetele de intoducere si extragere vor fi identificate prin pozitiile p si respectiv u.Notam cu n numarul de noduri din graf. Este necesar ca elemntele matricei de adiacenta a cu n liniin coloane sa fie cunoscute.Mai avem nevoie de un vector viz cu n elemente, in care elementele viziks k1,2,.,n au semnificatia viziis0, daca varful i nu a fost vizitat sau viziis0 daca a fost vizitat. Mai intai initializam tot vectorul viz cu 0.Initial in coada se gaseste varful de pornire p1, u1, cipsx, vizixs1.Cat timp mai sunt elemente in coadahile puExtragem din coada varful aflat in capatul de extragere u, si-l memoram intr-o variabila zIzcipsSPe linia z in a cautam vecinii lui z si ii introducem in coada.Algoritmul de parcurgere in adancime DFMetoda consta in-alegem varful de pornire, pentru acesta se alege primul vecin al sau nevizitat inca,pentru acest vecin cautam primul vecin al sau nevizitat si asa in continuare. In cazul in care un varf nu mai are vecini nevizitati atunci ne intoarcem la nodul anterior, iar pentru acel nod cautam urmatorul vecin nevizitat al sau.Pentru graful de mai sus parcurgerea in adancime plecand de la varful 1 este 1,2,3,4,6,7,5.Pentru a implementa vom folosi o stiva si metoda backtracking. Conexitatea in grafurile neorientatePrin parcurgerea in latime acelui graf am subliniat o proprietate importanta a grafuluifaptul ca in urma parcurgerii au fost vizitate toate varfurile.Luand oricare doua varfuri,putem gasi cel putin un traseu care porneste dintr-un varf si ajunge in celalalt.Luand oricare doua varfuri, ele pot fi legate printr-un lant.Dar nu toate grafurile sunt conexe. In schimb putem desprinde din el portiuni care, fiecare luata separat, este un graf conex.ExempluSe n...
Download