Arbori

Un arbore este un graf neorientat,conex și fără cicluri. Arborii reprezintă grafurile cele mai simple ca structură din clasa grafurilor conexe, ei fiind și cei mai frecvent utilizați în practică.
Un arbore cu n varfuri are cel mult n-1 muchii.
Rădăcină = Nod special care generează aşezarea unui arbore pe niveluri; Această operaţie se efectuează în funcţie de lungimea lanţurilor prin care celelalte noduri sunt legate de rădăcină.
Descendent = într-un arbore cu rădăcină nodul y este descendentul nodului x dacă este situat pe un nivel mai mare decât nivelul lui x şi există un lanţ care le uneşte şi nu trece prin rădăcină.
Descendent direct / fiu = într-un arbore cu rădăcină nodul y este fiul (descendentul direct) nodului x dacă este situat pe nivelul imediat următor nivelului lui x şi există muchie între x şi y.
Ascendent = într-un arbore cu rădăcină nodul x este ascendentul nodului y dacă este situat pe un nivel mai mic decât nivelul lui y şi există un lanţ care le uneşte şi nu trece prin rădăcină.
Ascendent direct / părinte = într-un arbore cu rădăcină nodul x este părintele (ascendentul direct) nodului y dacă este situat pe nivelul imediat superior (cu număr de ordine mai mic) nivelului lui y şi există muchie între x şi y.
Fraţi = într-un arbore cu rădăcină nodul x este fratele nodului y dacă au acelaşi părinte.
Frunză = într-un arbore cu rădăcină nodul x este frunză dacă nu are nici un descendent direct.

ARBORE PARȚIAL

Dat fiind un graf neorientat conex, se numeste arbore parțial al grafului un graf parțial cu proprietatea că este arbore. Intuitiv, un arbore parțial este un arbore obținut prin eliminarea unor muchii din graf.
Un arbore parțial al unui graf neorientat conex poate fi definit ca un graf parțial conex cu număr minim de muchii, sau un graf parțial aciclic cu număr maxim de muchii.

ARBORE BINAR

În informatică, un arbore binar este un arbore în care fiecare nod are cel mult doi succesori (fii). De obicei, succesorii se numesc „nodul stânga” și „nodul dreapta”. Arborii binari sunt folosiți mai ales drept arbori binari de căutare sau și la structurile de date de tip heap.

Parcurgerea grafurilor neorientate în lățime-BF

        Traversarea grafurilor în lăţime sau Breadth-First este numită astfel pentru că lărgeşte, uniform, frontiera dintre nodurile descoperite şi cele nedescoperite, pe lăţimea frontierei. Aceasta înseamnă că algoritmul descoperă toate vârfurile aflate la distanţa k faţă de ns înainte de a descoperi vreun vârf la distanţa k+1. Cu alte cuvinte traversarea în lăţime a grafurilor presupune faptul că după vizitarea unui anumit nod v, sunt parcurşi toţi vecinii nevizitaţi ai acestuia, apoi toţi vecinii nevizitaţi ai acestora din urmă până la vizitarea tuturor nodurilor grafului(spunem că două noduri sunt vecine dacă sunt adiacente).
        Implementarea acestei metode se face folosind o structură de date de tip coadă. Cozile sunt structuri de date în care elementele sunt inserate la un capăt (sfârşitul cozii) şi sunt suprimate de la celălalt capăt (începutul cozii). Ele implementează politica "primul venit - primul servit". Asupra unei cozi acţionează operatori specifici cum ar fi: iniţializare coadă, test de coadă vidă, adăugă un element la sfârşitul cozii, scoate un element de la începutul cozii. Cozile pot fi implementate static(cu variabile de tip tablou unidimensional) sau dinamic.
         În acest caz coada este iniţializată cu un nod oarecare al grafului. La fiecare pas, pentru nodul aflat în vârful cozii, se adaugă la coadă toţi vecinii nevizitaţi ai nodului respectiv după care se şterge din coadă primul nod.Fie graful din figura următoare care are n = 8 noduri.

Algoritmul lui Dijkstra

        Algoritmul lui Dijkstra determină câte un drum de cost minim de la vârful sursă x0, la fiecare dintre celelalte vârfuri ale grafului.
Iniţial, singurul vârf pentru care drumul de cost minim este deja cunoscut este numai vârful sursă x0.
        La fiecare pas se va selecta un vârf, care nu a mai fost selectat şi care se află la distanţă minimă de mulţimea vârfurilor selectate (cele pentru care drumul de cost minim este deja determinat).
Distanţa de la mulţimea vârfurilor deja selectate (să o notăm M) la un vârf oarecare yeste egală cu costul drumului de cost minim de la vârful sursă x0 la y, drum care trece numai prin vârfuri din mulţimea M.
        După selectarea vârfului situat la distanţă minimă de M (fie acesta y), toate distanţele de la M la vârfurile neselectate trebuie actualizate.
Mai exact, să notăm d[z] distanţa de la vârful neselectat z la mulţimea M, înainte de selectarea vârfului y.
        Prin includerea vârfului y în mulţimea M este posibil să obţinem un drum de cost mai mic, dacă distanţa d[z] este mai mare decât distanţa până la vârful y (d[y]) +costul arcului (y, z), adică d[z]>d[y]+c[y][z]. În acest caz, distanţa de la mulţimea M la vârful z trebuie actualizată.
Pentru a putea reconstitui şi drumurile de cost minim, vom reţine pentru fiecare vârf ydin graf (exceptând vârful x0) vârful care îl precedă pe drumul de cost minim de la x0la y.
        În animaţie, observaţi că vârfurile incidente cu arcele roşii aparţin mulţimii M (au fost selectate) iar extremităţile finale ale arcelor verzi sunt vârfurile către care s-a făcut actualizarea şi care sunt luate în calcul pentru selectare la următorul pas.

void dijkstra(int x0)
{
    int i, j, min, k, ok;
    int viz[NMAX], d[NMAX], tata[NMAX];
    for (i = 1; i<=n; i++) {
        d[i] = C[x0][i];
        tata[i] = x0;
        viz[i] = 0;
    }
    tata[x0] = 0;
    viz[x0] = 1; ok = 1;
    while (ok) {
        min = INFINIT;
        for (i = 1; i<=n; i++)
            if (!viz[i] && min>d[i]) {
                min = d[i];
                k = i;
            }
        if (min != INFINIT) {
            viz[k] = 1;
            for (i = 1; i<=n; i++)
               if (!viz[i] && d[i]>d[k]+C[k][i]) {
                   d[i] = d[k]+C[k][i];
                   tata[i] = k;
               }
        }
        else ok = 0;
    }
}

Tipuri de Grafuri

        1.Graful complet

        Se numeşte graf complet cu n vârfuri un graf cu proprietatea că oricare două noduri distincte sunt adiacente. Un graf complet cu n vârfuri se notează Kn.

        Exemplu: Graful definit mai jos este complet şi se notează cu K5. 

        Într-un graf complet, gradul oricărui nod este n - 1, pentru că din/în fiecare nod pleacă/sosesc n - 1 muchii. Într-un graf complet, avem relaţia: m = n(n - 1)/2 = 2 Cn (numărul de submulţimi cu 2 elemente ale mulţimii celor n noduri), unde m este numărul de muchii, iar n numărul de noduri. Avem ( 1) / 2 2 n n− grafuri neorientate cu n noduri.

         2.Graful bipartit

       Un graf G = (X, U) se numeşte bipartit dacă există 2 mulţimi nevide A şi B a.î. X = A ∪ B, A ∩ B = ∅ şi orice muchie u a lui G are o extremitate în A iar cealaltă în B. Mulţimile A şi B formează o partiţie a lui X. Un graf este bipartit dacă şi numai dacă nu conţine cicluri de lungime impară.                    Exemplu: A = {1, 3, 4} şi B = { 2, 5, 6, 7}.

         

        3.Graful eulerian

Fie G=(V, M) un graf neorientat. Graful G, fără vârfuri izolate, este eulerian dacă si numai daca este conex si gradele tuturor vârfurilor sale sunt numere pare.
Fie G=(V, M) un graf neorientat. Se numeste lant eulerian, in graful G, un lant care contine toate muchiile grafului G, fiecare muchie apărând în lant o singură dată.
Fie G= (V,M) un graf neorientat. Se numeste ciclu eulerian, în graful G, un ciclu care contine toate muchiile grafului G, fiecare muchie apărând în ciclu o singură data.
Graful G=(V,M) este un graf eulerian, deoarece graful este conex si gradul fiecarui varf este un numar par .

  

Pentru acest graf exista: Ciclu Eulerian: 1,2,6,3,2,5,3,4,5,6,1.

        4.Graful hamiltonian

   Se numeste graf hamiltonian, un graf care contine un ciclu hamiltonian.

Exemplu: Graful din figura este hamiltonian, deoarece ciclul c=[1,2,3,5,4,1] este elementar (pleaca din vârful 1, iar muchiile [1,2], [2,3], [3,5], [5,4] si [4,1] sunt distincte doua câte doua ) si în plus contine toate vârfurile.
Se numeste lant hamiltonian într-un graf, un lant elementar care contine toate vârfurile grafului.
Se numeste ciclu hamiltonian într-un graf, un ciclu elementar care contine toate vârfurile grafului.

Elemente de teoria grafurilor

        Grafurile pot fi aplicate cu succes pentru a modela probleme specifice analizei circuitelor electrice, găsirea celui mai scurt drum, analiza planificării proiectelor, critica textelor literare, rețele sociale, aplicații din domeniul chimiei și economiei.

        Definiţii: Se numeşte graf neorientat o pereche ordonată de mulţimi G=(X, U), unde: X = {x1, x2, x3, …, xn}este o mulţime finită şi nevidă de elemente numite noduri sau vârfuri, iar U o mulţime finită de perechi neordonate de forma (xi, xj), unde i≠j şi xi, xj∈X, numite muchii. O muchie uneşte două noduri. X = mulţimea nodurilor sau vârfurilor, iar U = mulţimea muchiilor grafului G. Un vecin al unui vârf este orice vârf care este adiacent lui în graf. O muchie u∈U este deci o submulţime {x, y} de vârfuri distincte din X şi se notează u = [x, y]. x şi y sunt adiacente în G, iar u şi x sunt incidente la fel ca u şi y. x şi y se numesc extremităţile muchiei u. Dacă u1 şi u2 sunt 2 muchii care au o extremitate comună, ele se numesc incidente. Mulţimea muchiilor are proprietatea de simetrie, deoarece [x, y]∈U dacă şi numai dacă [y,x]∈U.

        Un vârf care are gradul 0 (deci pentru care nu există vreo muchie incidentă cu el) se numeşte vârf izolat. Un vârf care are gradul 1 (deci care este incident cu o singură muchie) se numeşte vârf terminal.

       Exemplu: Pentru graful G definit anterior, d (11) = 0, deci vârful 11 este izolat. Fie un graf neorientat cu n noduri şi m muchii. Dacă notăm cu d1, d2, d3, …, dn gradele celor n noduri, atunci avem relaţia: d1 + d2 + d3 + … + dn = 2m 

        Definiţii: Se numeşte lanţ L = [x0, x1, …, xn]o succesiune de vârfuri cu proprietatea că oricare două vârfuri consecutive sunt adiacente. Vârfurile x0 şi xn se numesc extremităţile lanţului. Numărul n se numeşte lungimea lanţului şi este numărul de muchii din care este format. Lanţul care conţine numai vârfuri distincte, două câte două, este lanţ elementar. Lanţul care conţine numai muchii distincte este lanţ simplu. Dacă muchiile unui lanţ nu sunt distincte se numeşte lanţ compus. O matrice pătratică de ordin n se numeşte matricea lanţurilor, dacă: