Search:


| Hemorrhoid pain relief


Structuri de date abstracte.

Prezentarea structurii de date abstracte numita graf.

    1. Ce este un tip de date abstracte numit graf? >>>

    Un graf este o colectie de noduri si arce. Nodurile pot fi identificate prin chei, iar arcele reprezinta conexiuni intre noduri.Un graf G poate fi notat G=(N,A), unde N e multimea nodurilor, iar A a arcelor.
    Ordinul |G| unui graf G e dat de numarul nodurilor.
    Arcul a ce leaga nodurile x si y se spune ca este incident cu x si y si se noteaza a~(x,y), iar x si y se spune ca sunt adiacente.
    Gradul unui nod este egal cu numarul arcelor incidente lui. Un graf regulat are acelasi grad pentru toate nodurile.
    Grafurile pentru care orice arc (x,y)=(y,x) sunt neorientate.
    Bucla e un arc de forma a ~ (x,x).
    Un graf simplu ( toate discutiile urmatoare se vor referi la astfel de grafuri ) nu accepta existenta arcelor multiple, deci intre orice doua noduri poate exista cel mult un arc.
    Un graf G'=(N',A') este subgraf al unui graf G=(N,A) daca N' Ě N, A' Ě A si orice arc a' ~ (x,y) din A' conecteaza noduri din N' ( x si y sunt din N' ).
    Un drum de la x la y e o succesiune de noduri conectate prin arce : x, n1, n2, n3,..., y, lungimea drumului fiind data de numarul de arce.
    Un drum este simplu daca nodurile din drum sunt distincte (cu exceptia posibila a primului si ultimului ).

Exemplu de graf neorientat.

    Un ciclu e un drum cu acelasi nod initial si final.
    Doua noduri x si y se numesc conectate daca exista cel putin un drum intre ele.
    Un graf este conex daca toate perechile sale de noduri sunt conectate.
    Orice graf neconex este format din componenete conexe.
    Se observa ca arborii sunt cazuri particulare ale grafurilor.
    Un arbore de acoperire pentru un graf conex, este un subgraf care contine toate nodurile grafului, dar numai atâtea conexiuni câte sunt necesare formarii unui arbore. Pentru orice graf se poate gasi o padure de arbori de acoperire, cate unul pentru fiecare componenta conexa.
    Un graf complet de ordinul n contine arcuri intre toate perechile ce se pot forma cu cele n noduri ( deci contine n (n-1)/2 arce ).
    Un graf e rar daca are relativ putine arce si dens daca e aproape complet.
    Un graf e orientat daca arcele sale au un sens precizat.
    Un graf este ponderat daca arcelor sale li se asociaza cate o valoare.
    Un graf ponderat orientat se numeste retea.

Exemplu de graf orientat.

    2. Ordine şi grade intr-un graf. >>>

    Numim ordinul unui graf, numărul de noduri al grafului, deci cardinalul mulţimii X(G), şi notăm această valoare cu |G| . Numărul de muchii se notează cu ||G||.Graful vid este graful G(Φ,Φ), şi se notează cu Φ. Spunem că un graf G este trivial dacă acesta are ordinul 0 sau 1. Spunem că un nod v este incident cu o muchie r dacă v apartine lui r. Două vârfuri x şi y se numesc adiacente dacă există o muchie e care le uneşte (cu care amândouă vârfurile sunt incidente). Două muchii sunt adiacente dacă există un nod x care să fie incident cu ambele muchii. Numim gradul unui nod particular v, unde v apartine lui X(G), numărul de arce care sunt conectate la acel nod şi se notează de obicei cu ρ(v) sau cu d(v). Faptul că membrul drept al ecuaţiei va fi mereu par, implică aceeaşi proprietate în membrul stâng, pentru ca egalitatea să fie satisfăcută. Suma tuturor termenilor ρ(v) impari trebuie să fie o sumă al unui număr par de termeni, pentru a fi pară. Astfel deducem că orice graf are un număr par de noduri al căror grad este impar.

    3. Drumuri într-un graf. >>>

    Numim drum într-un graf o succesiune de muchii adiacente şi distincte care conectează două vârfuri din graf (numite capetele drumului). Un drum se numeşte simplu dacă muchiile care îl compun sunt distincte. Numim ciclu un drum care are drept capete un acelaşi vârf. Dacă P = x0, ..., xk-1 este un drum în graful G şi xk-1x0 este o muchie în acest graf, atunci P + xk-1x0 este un ciclu din graful G. Un ciclu se numeşte hamiltonian dacă este simplu şi trece prin toate nodurile grafului G, exact o dată, şi se numeşte eulerian dacă trece prin toate muchiile grafului G, exact o dată. Nu orice graf conţine un ciclu hamiltonian (vezi poza cu graful orientat). Spunem că S este un subgraf al lui G, dacă acesta conţine o parte din vârfurile lui G şi numai acele muchii care le conectează.
    Dacă în definiţia unui graf se considera E(G) o multimulţime pe P2(V(G)), adică este dată o funcţie m: Ρ2(V(G))-> Ν, se obţine noţiunea de multigraf. Dacă în definiţia unui graf se considera E(G) o multimulţime pe mulţimea părtilor nevide cu cel mult două elemente ale lui V(G), atunci G se numeşte graf general sau pseudograf.

Multigraf.

    4. Conexiune. >>>

    Spunem că un graf este conex dacă între oricare două vârfuri ale acestuia există cel puţin un drum. De exemplu grafurile din figurile 1 şi 2 nu sunt conexe, în timp ce graful din figura 3 este un graf conex. Graful trivial este considerat conex. Complementul unui graf G este graful /G(X,X2\V), care conţine o muchie între vârfurile x şi y dacă şi numai dacă G nu conţine o astfel de muchie. Complementul unui graf care nu este conex, este un graf conex. Reciproca nu este adevărată, de exemplu pentru un lanţ de lungime 3 (între 4 vârfuri).

    5. Operatorii tipul de date abstracte numit Graf.

    5.1. Setul extins de operatori. >>>
    Se folosesc notatiile: Tip_Element - tipul nodurilor, cu campurile de Tip_Cheie si Tip_Info
    g - graf
    indic_Nod - indicator la nod
    indic_Arc - indicator la arc
    e - variabila de Tip_Element
    k,k1,k2 - variabile de Tip_Cheie
    x - variabila de Tip_Info
    b - variabila booleana.

    Operatorii setului extins sunt:

      * Init_Graf(g) - creaza graful vid.
      * Graf_Vid(g) - verifica daca g e vid.
      * Graf_Plin(g) - verifica daca g e plin, deci nu mai pot fi adaugate alte noduri (depinde de varianta de implementare).
      * Cheie_Elem_Graf(g,e) - returneaza cheia nodului e al grafului g.
      * Cauta_Cheie_Graf(g,k) - returneaza true daca cheia k e gasita in g.
      * Indica_Nod(g,k,indic_Nod) - indic_Nod va lua valoarea indicatorului spre nodul cu cheia k.
      * Indica_Arc(g,k1,k2,indic_Arc) - indic_Arc va indica spre arcul ce conecteaza nodurile cu cheile k1 si k2.
      * Arc_Vid(g,indic_Arc) - verifica daca indic_Arc este vid.
      * Inser_Nod(g,e) - se insereaza in g nodul e ca nod izolat.
      * Inser_Arc(g,k1,k2) - se insereaza arcul ce conecteaza nodurile de chei k1 si k2.
      * Suprim_Nod(g,indic_Nod) - se suprima nodul indicat, cu toate arcele incidente.
      * Suprim_Arc(g,indic_Arc) - suprima arcul precizat.
      * Actualiz_Nod(g,indic_Nod,x) - actualizeaza cu x informatia nodului indicat.
      * Furniz_Nod(g,indic_Nod) - returneaza valoarea nodului (de Tip_Element) indicat.
      * Travers_Graf(g,Vizita(Lista_de_argumente)) - parcurge toate nodurile grafului g, pentru fiecare nod executand prelucrarea Vizita.

    5.2. Setul restrans de operatori. >>>
    Se folosesc notatiile ( Rick Decker ):

    graful contine multimile ATOM si POZITIE
    g=(P,R,f) - unde
    P - subset finit al multimii POZITIE
    f - functie P-> ATOM
    R - relatie simetrica in P ( si ireflexiva daca nu se admit bucle )
    p,q - variabile de tip POZITIE
    e - variabila de tip ARC
    a - variabila de tip ATOM

    Operatorii setului restrans sunt:

      * Creaza(g) - creaza graful vid g.
      * Adiacent(p,q,g) - verifica daca p si q sunt adiacente.
      * Modifica(a,p,g) - se modifica la zona de date a nodului indicat de p.
      * Furnizeaza(p,g) - returneaza zona de date a nodului indicat de p.
      * Suprim_Nod(p,g) - se suprima nodul indicat cu toate arcele adiacente.
      * Suprim_Arc(e,g) - se suprima arcul a.
      * Inser_Nod(p,g) - se adauga nodul indicat, ca nod izolat.
      * Inser_Arc(e,g) - se adauga arcul e.

    6. Tehnici de implementare a TDA graf.

    6.1. Implementarea grafurilor prin matrici de adiacenta. >>>
    Cea mai directa implementare este printr-o matrice de adiacente. Daca graful are N noduri, matricea A de dimensiune N x N , are elementul A[x,y] true daca nodurile x si y sunt adiacente. Matricea e simetrica pentru un graf neorientat.

    Se realizeaza mai intai o corespondenta intre numele nodurilor si multimea indicilor, in una din variantele :

      * numele pot fi chiar indicii sau literele alfabetului
      * corespondenta se mai poate face prin : tablouri, liste, arbore binar, tablouri de dispersie

    Reprezentarea e eficienta pentru grafurile dense. Pentru un graf cu n noduri, crearea grafului necesita O(n) pasi pentru noduri si O(n2) pentru arce. Varianta de implementare cu matrice de adiacente: O varianta de implementare cu matrice de adiacente este data mai jos, graful aparand ca o structura ce contine contorul nodurilor, tabloul nodurilor si matricea de adiacente ( arce ). Tabloul nodurilor nu este ordonat dupa chei. Un nod nou se adauga in continuarea celor existente. Suprimarea unui nod se realizeaza prin copierea ultimei intrari peste cea care se sterge in tabloul Noduri, respectiv a conexiunilor ultimului nod peste cele ale nodului sters in Arce:

    const NumarNoduri = .......;
    type TipCheie = .......;
    TipInfo = .......;
    TipElement = record
      Cheie: TipCheie;
      Info : TipInfo
      end;
    TipContor = 0..NumarNoduri;
    TipIndex = 1..NumarNoduri;
    TipTablouElem = array[TipIndex] of TipElement;
    TipMatrAdj = array[TipIndex,TipIndex] of boolean;
    Graf = record
      Contor : TipContor;
      Noduri : TipTablouElem;
      Arce : TipMatrAdj
      end;
    TipArc = record
      linie,
      coloana: TipIndex
       end;
    var g: Graf;
    procedure InserNod(var g: Graf;e: TipElement);
    { insertia unui nod izolat }
    var i,j: TipIndex;
    begin
      with g do
        begin
          contor := contor + 1; { se plaseaza e
          Noduri[contor] := e; in nodul nou}
          for i := 1 to contor do
            Arce[i,contor] := false { se initializeaza
          for j := 1 to contor do matricea de adiacente
            Arce[contor,j] := false pentru nodul nou }
          end {with}
        end; {InserNod}
    procedure InserArc(var g: Graf; indicArc: TipArc);
    begin
      g.Arc[indicArc.linie,indicArc.coloana] := true;
      g.Arc[indicArc.coloana,indicArc.linie] := true
      end; { InserArc }
    procedure SuprimNod(var g: Graf; indicNod: TipIndex);
    { suprima nodul dat impreuna cu toate arcele incidente }
    var i,j: TipIndex;
    begin
      with g do
      begin
        Noduri[indicNod] := Noduri[contor];
        for j := 1 to contor do
          Arce[indicNod,j] := Arce[contor,j];
        for i := 1 to contor do
          Arce[i,indicNod] := Arce[i,contor];
        contor := contor - 1
        end { with }
        end; { SuprimNod }
    procedure SuprimArc(var g: Graf; indicArc: TipArc);
    begin
      g.Arc[indicArc.linie,indicArc.coloana] := false;
      g.Arc[indicArc.coloana,indicArc.linie] := false
      end; { SuprimArc }

    Construirea unui graf necesita cate un apel la InserNod pentru fiecare nod, respectiv cate un apel la InserArc pentru fiecare arc. Daca nodurile s-ar introduce ordonate dupa cheie in Noduri, localizarea unei chei poate fi facuta folosind cautarea binara.

    6.2. Implementarea grafurilor prin structuri de adiacenta. >>>
    In aceasta implementare fiecarui nod i se asociaza o lista in care sunt inlantuite toate nodurile cu care acesta este conectat. Implementarea este avantajoasa in cazul grafurilor rare. Se vor prezenta trei subvariante.

    Varianta 1. Inceputurile listelor de inlantuiri se pastreaza intr-un tablou Stradj. Listele pot partaja acelasi nod final fictiv. Orice insertie se face la inceputul listei. Trebuie realizata o corespondenta intre numele nodurilor si multimea indicilor, prin functia index. Insertia unui arc implica insertia unui nod in fiecare din cele doua liste corespunzatoare nodurilor conectate.

    const maxN = 100;
    type legatura = ^Nod;
      Nod = record
        nume: integer; { index }
        urm: legatura
        end; { nod }
    var  Stradj: array[1..maxN] of legatura;

    Fiecare element din StrAdj ar putea retine si cheia nodului, astfel nemaifiind necesara o alta asociere:

    StrAdj:array[1..maxN] of record
      cheie:TipCheie;
      adj:legatura
      end;

    Varianta 2. Graful se implementeaza ca multilista: o lista a nodurilor contine, pentru fiecare nod, inceputul listei de adiacente. Nodurile pot fi pastrate ordonat sau nu, in lista nodurilor cat si in cele de adiacente. Se precizeaza ca valorile nodurilor sunt pastrate integral in lista de noduri, in lista de arce apar numai cheile.

    type TipCheie = .....;
    TipInfo = .....;
    TipElement = record
      cheie: TipCheie;
      info : TipInfo
      end;
    PtrAdj = ^Adj;
    Adj = record
      cheieAdj: TipCheie;
      urmAdj : PtrAdj
      end;
    ptrNod = ^Nod;
    graf = ptrNod;
    Nod = record
      elem : TipElement;
      urmNod : ptrNod;
      incepAdj : PtrAdj
      end;
    TipArc = record
      v1,v2 : ptrNod
      end;
    var g : graf;

    Insertia unui arc nou, care conecteaza nodurile de chei k1 si k2, presupune insertia lui k1 in lista de adiacente a lui k2 si reciproc. Cel mai simplu este sa se faca insertiile la inceputul listelor de adiacente. Suprimarea unui arc precizat presupune extragerea celor doua noduri care sunt capetele arcului din doua liste de adiacente diferite. Pentru a suprima arcul care conecteaza nodurile k1 si k2 este necesar ca fiecare nod sa fie suprimat din lista de adiacente a celuilalt.

    Suprimarea unui nod din graf presupune nu numai suprimarea nodului respectiv, ci si a tuturor arcelor incidente acestui nod. Fie k cheia nodului de suprimat. Pentru fiecare nod k2 din lista de adiacente a lui k, se suprima arcul (k,k2) prin stergerea lui k din lista de adiacente a lui k2 si pe k2 din lista de adiacente a lui k.

    Varianta 3. Ceea ce este diferit fata de varianta anterioara este faptul ca in listele de adiacente nu apar cheile nodurilor, ci pointerii spre nodurile adiacente din lista (principala) de noduri ale grafului, algoritmii de prelucrare devenind mai simpli.

    type POZITIE = ^CelulaListNod;
    PointListArc = ^CelulaListArc;
    CelulaListNod = record
      data : ATOM; { informatie apartinind nodului }
      urm : POZITIE; { urmatoarea celula in lista nodurilor }
      incep : PointListArc { pointer la lista de adiacente }
      end;
    CelulaListArc = record
      data : ...; { informatie atasata arcului }
      nod : POZITIE; { destinatia arcului }
      urm : PointListArc { inlantuirea in lista de arce }
      end;
    ARC = record
      nod1,nod2: POZITIE
      end;
    GRAF = POZITIE;

    In figura de mai jos sunt prezentate schematic structurile de adiacente pentru variantele b si c.

Structuri de date abstracte | SDA Arbori | SDA Arbori Binari | SDA Arbori Multicai | SDA Arbori Optimi | SDA Graf | Traversarea grafurilor | SDA Graf Ponderat | SDA Graf Orientat | SDA Lista Inlantuita | SDA Tablou Asociat | Despre algoritmi. | Algoritmi de cautare neinformata, cautarea inforamata,cautarea in liste,in grafuri, in SQL-uri | Algoritmi de cautare liniara, binara, interpolare | Prezentare Algoritmi Sortare | Sortare Insertie cu Pas Variabil (Shellsort) | Sortarea Prin Ansamble (Heapsort) | Sortarea Prin Insertie (Insertionsort) | Sortarea Prin Interclasare (Mergesort) | Sortarea Prin Interschimbare (Bubblesort) | Sortarea Prin Selectie (Selectionsort) | Sortarea Rapida (Quicksort)

Inapoi la pagina principala



©2006-2007 frankeman Software - Timisoara. Toate drepturile sunt rezervate.