Considerăm un graf neorientat ponderat (cu costuri) conex G. Se numește arbore parțial un graf parțial al lui G care este arbore. Se numește arbore parțial de cost minim un arbore parțial pentru care suma costurilor muchiilor este minimă.
Dacă graful nu este conex, vorbim despre o pădure parțială de cost minim.
Algoritmul lui Kruskal permite determinarea unui arbore parțial de cost minim (APM) într-un graf ponderat cu N noduri.
Pentru a determina APM-ul se pleacă de la o pădure formată din N subarbori. Fiecare nod al grafului reprezintă inițial un subarbore. Aceștia vor fi reuniți succesiv prin muchii, până când se obține un singur arbore (dacă graful este conex) sau până când acest lucru nu mai este posibil (dacă graful nu este conex).
Algoritmul este:
Principala dificultate în algoritmul descris mai sus este stabilirea faptului că extremitățile muchiei curente fac sau nu parte din același subarbore. În acest scop vom stabili pentru fiecare subarbore un nod special, numit reprezentant al (sub)arborelui și pentru fiecare nod din graf vom memora reprezentantul său (de fapt al subarborelui din care face parte) într-un tablou unidimensional.
Pentru a stabili dacă două noduri fac sau nu parte din același subarbore vom verifica dacă ele au același reprezentant. Pentru a reuni doi subarbori vom înlocui pentru toate nodurile din subarborele B cu reprezentantul subarborelui A.
Înlocuirile descrise mai sus sunt simple dar lente. Pentru o implementare mai eficientă a algoritmului se poate folosi conceptul de Padure de mulțimi disjuncte, descris în acest articol.
Vom determina, folosind Algoritmul lui Kruskal, arborele parțial de cost minim pentru graful de mai jos.

Muchiile se vor analiza în ordinea crescătoare a costului.

Se adaugă muchia (7,8) de cost 1

Se adaugă muchia (3,9) de cost 2

Se adaugă muchia (6,7) de cost 2

Se adaugă muchia (1,2) de cost 4

Se adaugă muchia (3,6) de cost 1
Se ignoră muchia (7,9) de cost 6

Se adaugă muchia (3,4) de cost 7

Se ignoră muchia (8,9) de cost 7

Se adaugă muchia (1,8) de cost 8

Se ignoră muchia (2,3) de cost 8

Se adaugă muchia (4,5) de cost 9

Se ignoră muchia (5,6) de cost 10

Se ignoră muchia (2,8) de cost 11

Se ignoră muchia (4,6) de cost 14
Vom determina, folosind Algoritmul lui Kruskal, arborele parțial de cost minim pentru graful de mai jos:

Muchiile se vor analiza în ordinea următoare:
| 1. | |
Se adaugă muchia (7,8) de cost 1 |
| 2. | |
Se adaugă muchia (3,9) de cost 2 |
| 3. | |
Se adaugă muchia (6,7) de cost 2 |
| 4. | |
Se adaugă muchia (1,2) de cost 4 |
| 5. | |
Se adaugă muchia (3,6) de cost 1 |
| 6. | |
Se ignoră muchia (7,9) de cost 6 |
| 7. | |
Se adaugă muchia (3,4) de cost 7 |
| 8. | |
Se ignoră muchia (8,9) de cost 7 |
| 9. | |
Se adaugă muchia (1,8) de cost 8 |
| 10. | |
Se ignoră muchia (2,3) de cost 8 |
| 11. | |
Se adaugă muchia (4,5) de cost 9 |
| 12. | |
Se ignoră muchia (5,6) de cost 10 |
| 13. | |
Se ignoră muchia (2,8) de cost 11 |
| 14. | |
Se ignoră muchia (4,6) de cost 14 |
Următoarea secvență determină costul total al APM-ului, folosind algoritmul lui Kruskal. Presupunem că graful are cel mult 100 de noduri.
struct muchie{
int i,j,cost;
};
int n , m , t[101];
muchie x[5000];
int main()
{
cin >> n >> m;
for(int i = 0 ; i < m ; ++i)
cin >> x[i].i >> x[i].j >> x[i].cost;
//sortare tablou x[] după campul cost
// ... de completat
//initializare reprezentanti
for(int i =1 ; i <= n ; ++i)
t[i] = i;
//determinare APM
int S = 0;
for(int i = 0 ; i < m ; i ++)
if(t[x[i].i] != t[x[i].j]) // extremitatile fac parte din subrabori diferiti
{
S += x[i].cost;
//reunim subarborii
int ai = t[x[i].i], aj = t[x[i].j];
for(int j =1 ; j <= n ; ++j)
if(t[j] == aj)
t[j] = ai;
}
cout << S << "\n";
return 0;
}
Algoritmul lui Dijkstra determină pentru un nod dat într-un graf orientat cu costuri costurile minime ale drumurilor care au acel nod ca extremitate inițială.
Mai precis, pentru un nod s – sursă, algoritmul determină pentru orice nod x costul minim al unui drum de la s la x.
Strategia algoritmului lui Dijkstra este una de tip Greedy:
d[], în care d[x] reprezintă costul minim curent (eventual infinit) al unui drum de la s la x;F de noduri k pentru care s-a determinat costul minim final d[k]F se adaugă doar nodul s, pentru care d[s]=0; pentru nodurile x adiacente cu s, d[x]=c[s,x], unde c[x,y] este costul arcului (x,y), iar pentru celelalte noduri costul d[] se inițializează cu INFINIT;F, nodul k pentru care costul drumului d[k] este minim și finit;k în F;(k,x) cu x din afara mulțimii F stabilim dacă acest arc îmbunătățește costul d[x] (arcul relaxează drumul);
F (s-au determinat costurile drumurilor de la s la fiecare nod al grafului) sau când nu mai există noduri x din afara mulțimii F pentru care d[x] este finit;Aplicați algoritmul lui Dijkstra pentru graful de mai jos și s=1:

În secvența de mai jos, considerăm un graf orientat cu n noduri, reprezentat prin matricea de adiacență a[][], în care a[i][j]=INFINIT dacă nu există arcul (i,j).
#define INFINIT 1000000000
...
//nodul sursa este s
...
for(i =1 ; i <= n ; i ++ )
{
f[i] = 0;
d[i] = a[s][i];
}
f[s] = 1, d[s] = 0;
d[0] = INFINIT; // pentru determinarea nodului cu costul minim
for(int k = 1 ; k < n ; ++k)
{
int pmax = 0;
for(i = 1 ; i <= n ; ++i)
if(f[i] == 0 && d[i] < d[pmax])
pmax = i;
if(pmax > -1)
{
f[pmax] = 1;
for(i = 1; i <= n ; ++i)
if(f[i] == 0 && d[i] > d[pmax] + a[pmax][i])
d[i] = d[pmax] + a[pmax][i];
}
} Un graf orientat G=(V,E) este tare conex dacă pentru orice pereche de noduri distincte (x,y) există cel puțin un drum de la x la y și există cel puțin un drum de la y la x.
Pentru un graf orientat, se numește componentă tare conexă un subgraf tare conex maximal – prin adăugarea a încă unui nod, subgraful obținut nu mai este tare conex.
Exemplu

Graful de mai sus nu este tare conex. El are trei componente tare conexe.
Verificare tare conexității unui graf orientat poate fi privită ca un caz particular al determinării componentelor tare conexe, deoarece, dacă graful are o singură componentă tare conexă atunci el este tare conex. În continuare vom vedea două metode de determinare a componentelor tare conexe. Ambele folosesc noțiunea de graf transpus, pe care o definim în continuare:
Definiție: Fie G=(V,E) un graf orientat. Se numește graf transpus al lui G graful orientat GT=(V,ET), cu aceeași mulțimea a nodurilor și pentru orice pereche de noduri are loc: (x,y) este arc în G dacă și numai dacă (y,x) este arc în GT.
Exemplu
| Graf orientat inițial | Graful orientat transpus |
|
|
Să observăm că pentru două noduri oarecare x, y:
x la y poate fi determinată cu o parcurgere (de exemplu în adâncime) în graful G, pornind din nodul x;y la x poate fi determinată cu o parcurgere în graful GT, pornind tot din nodul x.Folosind observații de mai sus, pentru a determina componentele tare conexe folosim următorul algoritm, numit Plus-Minus:
x al grafului care încă nu a fost plasat într-o componentă tare conexă:
x, folosind graful G și le marcăm într-un tablou cu plus;x, folosind graful GT și le marcăm într-un tablou cu minus;x formează o componentă tare conexă;Exemplu:
Fie graful de mai sus. Să determinăm componenta tare conexă din care face parte nodul 6:
| Graful inițial | Graful transpus |
|
|
S-au marcat cu plus nodurile: 5 7 8 |
S-au marcat cu minus nodurile: 1 2 3 4 5 7 8 |
Nodurile marcate de două ori, 5 7 8, împreună cu nodul inițial, 6, formează o componentă tare conexă.
Secvență C++:
n, a[][] – numărul de noduri și matricea de adiacențănrc – numărul de componente tare conexectc[] – tablou pentru memorarea componentelor tare conexe: ctc[i] = numărul de ordine al componentei din care face parte nodul is[], p[] – tablouri pentru marcarea nodurilor vizitate în timpul parcurgerilorvoid df1(int x)
{
s[x] = 1;
for(int i =1 ; i <= n ; i ++)
if(s[i] == 0 && a[x][i] == 1)
df1(i);
}
void df2(int x)
{
p[x] = 1;
for(int i =1 ; i <= n ; i ++)
if(p[i] == 0 && a[i][x] == 1)
df2(i);
}
int main()
{
.....
for(int i = 1 ; i <= n ; ++i)
if(ctc[i] == 0)
{
for(int j = 1; j <= n ; ++j)
s[j] = p[j] = 0;
nrc ++;
df1(i); df2(i);
for(int j = 1; j <= n ; ++j)
if(s[j] == 1 && p[j] == 1)
ctc[j] = nrc;
}
....
}
Alt algoritm, mai eficient, pentru determinarea componentelor tare conexe este Algoritmul lui Kosaraju.
Să ne amintim că la parcurgerea în adâncime se pot asocia nodurilor două momente de timp:
d[x] – momentul când nodul x este descoperit și adăugat pe stivă: timpul de descoperire a noduluif[x] – momentul când se termină de vizitat succesorii lui x, iar nodul x se elimină de pe stivă: timpul de finalizare a noduluiAceste momente de timp vor fi numere naturale între 1 și 2*n, unde n este numărul de noduri din graf.
Algoritmul lui Kosaraju este:
GTx timpul de finalizare f[x]GT, dar considerăm nodurile în ordinea descrescătoarea timpilor de finalizareExemplu:
| Graf orientat inițial | Graful orientat transpus |
|
|
În urma parcurgerii în adâncime a grafului inițial G nodurile în ordinea finalizării sunt: 
Parcurgem graful transpus GT analizând nodurile în ordinea inversă a timpilor de finalizare:
1; se vizitează nodurile 3 4; se determină componenta tare conexă {1,3,4};2 (nodurile 1, 3 și 4 au fost vizitate mai devreme); nu se vizitează alte noduri; se determină componenta tare conexă {2};5; se vizitează nodurile 6 8 7; se determină componenta tare conexă {5, 6, 7, 8}.
Secvență C++:
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector<vector<int> > G, GT;
int n , m , contor , nrs;
vector<bool> V;
vector<int> S;
void read()
{
cin >> n >> m;
G = GT = vector<vector<int>>(n + 1);
for(int i = 1 ; i <= m ; i++)
{
int a , b;
cin >> a >> b;
G[a].push_back(b);
GT[b].push_back(a);
}
}
void dfs(int k)
{
V[k] = true;
for(auto x : G[k])
if(!V[x])
dfs(x);
S.push_back(k);
}
void dfsGT(int k)
{
V[k]=1;
for(auto x: GT[k])
if(! V[x])
dfsGT(x);
}
int main()
{
read();
V = vector<bool> (n + 1, false);
for(int i = 1 ; i <= n ; i ++)
if(! V[i])
dfs(i);
V = vector<bool> (n + 1, false);
for(vector<int>::reverse_iterator it = S.rbegin() ; it != S.rend() ; it ++)
if(!V[*it]) {
contor ++;
dfsGT(*it);
}
cout<<contor;
return 0;
}
Complexitatea acestui algoritm este aceea a parcurgerii în adâncime: O(n2) dacă memorăm graful prin matricea de adiacență, O(n+m) dacă memorăm graful prin liste de adiacență.
În unele situații se cere gruparea elementelor unei mulțimi date într-o colecție de submulțimi disjuncte. Pentru o astfel de colecție sunt importante următoarele operații:
Pentru fiecare submulțime se stabilește un reprezentant – unul dintre elementele submulțimii. Fiecare element al submulțimii este asociat într-un anumit mod cu reprezentantul acesteia. În acest fel, operația de stabilire a submulțimii din care face parte un anumit element constă în simpla identificare a reprezentantului, iar operația de reuniune a două submulțimii constă în asocierea elementelor unei submulțimii cu reprezentantul celeilalte. Două elemente fac parte din aceeași submulțime dacă sunt asociate cu același reprezentant.
Operațiile cu mulțimi disjuncte pot fi folosite pentru determinarea componentelor conexe ale unui graf, astfel:
(x,y) stabilim dacă x și y fac parte din submulțimi diferite, caz în care reunim cele două submulțimi;O altă aplicație a acestor structuri de date este Algoritmul lui Kruskal pentru determinarea arborelui parțial de cost minim a unui graf neorientat cu costuri.
O modalitate eficientă de gestionare a submulțimilor și a operațiilor cu acestea este utilizarea unor structuri arborescente (a unei păduri), numite pădure de mulțimi disjuncte, în care:
Gestionarea arborilor se poate face prin intermediul unui vector de tați:
T[k] = 0, dacă k este rădăcină a unui arbore (și reprezentant al submulțimii corespunzătoare)T[k] = tatăl lui k în arborele din care face parteExemplu
Fie mulțimea {1,2,3,4,5,6,7, 8} cu submulțimile disjuncte {1,3,4}, {2,5,7} și {6,8}. O reprezentare prin păduri de mulțimi disjuncte poate fi:

Ei îi corespunde următorul vector de tați:
k |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
T[k] |
0 |
5 |
4 |
1 |
0 |
0 |
5 |
6 |
Dacă reunim submulțimile {2,5,7} și {6,8}, pădurea devine:

și îi corespunde următorul vector de tați:
k |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
T[k] |
0 |
5 |
4 |
1 |
0 |
5 |
5 |
6 |
Ambele operații (stabilirea submulțimii din care face parte un anumit element și reuniunea a două submulțimi) presupun identificarea reprezentantului unei submulțimii, adică a rădăcinii arborelui asociat submulțimii, operație ce presupune parcurgerea arborelui de la un nod spre rădăcină.
Următoarea secvență C++ gestionează vectorul de tați T[], declarat global, prin intermediul a două funcții: int Radacina(int k), care determină rădăcina arborelui din care face parte nodul k (reprezentantul lui k) și void Unire(int k, int p), care realizează operația de reuniune a submulțimilor din care face parte k și p.
int T[...];
int Radacina(int k){
if(T[k] == 0)
return k;
else
return Radacina(T[k]);
}
void Unire(int k, int p)
{
int rk = Radacina(k), rp = Radacina(p);
if(rk != rp)
T[rk] = rp;
}
Această implementare a operațiilor poate conduce la arbori cu înălțime mare. Acest fapt are efect asupra operației de determinare a rădăcinii arborelui din care face parte un nod dat, care este cu atât mai rapidă cu cât lungimea lanțului de la nod la rădăcină este mai mică. În gestionarea pădurilor de mulțimi disjuncte se pot folosi două euristici care duc la complexitate aproape liniară în raport cu numărul total de operații:
Următoarea secvență C++ îmbunătățește operațiile de mai sus cu ajutorul celor două euristici. Pentru determinarea rangurilor folosim un vector suplimentar, Rang[]:
int t[...];
int Radacina(int k){
if(T[k] == 0)
return k;
else
{
int x = Radacina(T[k]);
T[k] = x;
return x;
}
}
void Unire(int k, int p)
{
int rk = Radacina(k), rp = Radacina(p);
if(rk != rp)
{
if(Rang[rk] > Rang[rp])
T[rp] = rk;
else
{
T[rk] = rp;
if(Rang[rk] == Rang[rp])
Rang[rp] ++;
}
}
}
Fie G=(V,E) un graf neorientat conex:
Exemplu:
| Graful inițial | Puncte de articulație | Punți | Componente biconexe |
| |
|
|
|
Câteva observații:
Pentru a determina punctele de articulație și punțile se poate folosi un algoritm naiv, bazat pe eliminarea succesivă a câte unui nod (muchie) și verificarea conexității. Complexitatea acestor algoritmi este O(n*C), respectiv O(m*C), unde O(C) este complexitatea algoritmului de verificarea a conexității (O(n*n) dacă reprezentăm graful prin matrice de adiacență, O(n+m) dacă reprezentăm graful prin liste de adiacențe).
În cele ce urmează vom prezentat un algoritm bazat pe parcurgerea în adâncime a grafului. Complexitatea sa este aceeași cu a parcurgerii în adâncime.
Considerăm G=(V,E) graful dat și A arborele de parcurgere în adâncime. Reamintim că muchiile graful pot fi doar:
(k,x) este de întoarcere dacă x este ascendent al lui k în arborele A – nodul x a fost descoperit anterior nodului kPentru graful de mai sus, arborele de parcurgere este următorul – muchiile de parcurgere sunt desenate cu linii continue, cele de întoarcere cu linii întrerupte.
![]()
Observăm următoarele:
k al grafului, diferit de rădăcina arborelui DFS, este punct de articulație dacă și numai dacă are un descendent direct x în arborele A cu proprietatea că de la niciun descendent al lui x sau de la x nu există muchie de întoarcere la niciun ascendent al lui k;Pentru a determina punctele de articulație, punțile și componentele biconexe vom determina pentru fiecare nod k următoarele informații:
nivel[k] – nivelul pe care se află nodul k în arborele DFS;
nivel[rădăcină] = 1;nivel[k] = nivel[tata[k]] + 1;nma[k] – nivelul minim la care se poate ajunge din k, mergând numai pe muchii de arbore și folosind ca ultimă muchie o muchie de întoarcere. Îl vom numi nivelul minim accesibil și este egal cu minimul dintre următoarele 3 valori :
Pentru graful de mai sus aceste valori sunt următoarele:
![]()
k |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
nivel[k] |
1 |
2 |
3 |
4 |
3 |
5 |
4 |
6 |
nma[k] |
1 |
1 |
3 |
1 |
1 |
4 |
4 |
4 |
Cu ajutorul acestor valori, un nod k care nu este rădăcina arborelui este punct de articulație dacă și numai dacă are cel puțin un fiu x pentru care nivelul minim accesibil este mai mare sau egal cu nivelul nodului (nivel[k] <= nma[x]). Să analizăm nodurile:
1 nu este punct de articulație, deoarece este rădăcina arborelui și are un singur descendent direct2 este punct de articulație, deoarece 3 este fiu al lui 2 și nivel[2] <= nma[3]3 nu este punct de articulație, deoarece nu are niciun fiu4 nu este punct de articulație, deoarece nu are niciun fiu5 este punct de articulație deoarece 7 este fiu al lui 5 și nivel[5] <= nma[7]6 nu este punct de articulație; pentru singurul fiu al lui 6, 8 relația este nivel[6] > nma[8]7 este punct de articulație deoarece 6 este fiu al lui 7 și nivel[7] <= nma[6]8 nu este punct de articulație deoarece nu are fiiFie (k,x) o muchie de arbore, în care k este tatăl lui x. Această muchie este critică dacă și numai dacă (nivel[k] < nma[x]). Muchiile de întoarcere nu sunt niciodată muchii critice, deoarece aparțin întotdeauna unor cicluri.
Cele două șiruri de valori se construiesc în timpul parcurgerii DFS. Fie k nodul curent în parcurgerea DFS:
nivel[k] = nivel[tata[k]] + 1 – această valoare va rămâne neschimbată până la final;nma[k] = nivel[k]k. Fie x un asemenea nod:
x a fost deja parcurs și nu este tatăl lui k, muchia (k,x) este muchie de întoarcere. Dacă este cazul actualizăm nma[k] la valoarea nivel[x] (dacă nivel[x] este mai mic decât valoarea actuală a lui nma[k]);x nu a fost încă parcurs, continuăm parcurgerea din x – îl adăugăm pe stivă/apel recursiv. La eliminarea de pe stivă/ revenirea din autoapel, actualizăm valoarea nma[k] la valoarea nma[x] (dacă nma[k] este mai mare decât nma[x], acesta din urmă este calculat deja)Următorul pseudocod descrie cum se calculează pentru fiecare nod al grafului nivelul și nivelul minim accesibil, folosind parcurgerea în adâncime:
subprogram DFS(k, tata)
V[k] ← true
nivel[k] ← nivel[tata] + 1
nma[k] ← nivel[k]
pentru x - nod adiacent cu k
dacă x ≠ tata
dacă V[x] = true atunci
dacă nma[k] > nivel[x] atunci
nma[k] ← nivel[x]
sf_dacă
altfel
DFS(x,k)
dacă nma[k] > nma[x] atunci
nma[k] ← nma[x]
sf_dacă
// determinare puncte de articulație
// determinare punți
// determinare componente biconexe
sf_dacă
sf_dacă
sf_pentru
sf_subprogram
Pentru a determina punctele de articulație:
x (revenirea din autoapel) verificăm dacă acest și nodul părinte k verifică relația nivel[k] <= nma[x]; în caz afirmativ, decidem că nodul k este critic;//determinare puncte de articulație
dacă nivel[k] ≤ nma[x] și nod ≠ rădăcină atunci
//nodul k este punct de articulație
sf_dacă
Pentru a determina punțile:
x/revenirea din autoapel vom determina muchiile de parcurgere (k,x) pentru care nivelul lui k este mai mic decât nivelul minim accesibil al lui x: nivel[k] < nma[x].//determinare punți
dacă nivel[k] < nma[x] atunci
//muchia (k,x) este punte
sf_dacă
Pentru a determina componentele biconexe:
S, pe care adaugăm noduri la vizitarea lor conform parcurgerii și le eliminăm la determinarea unei componente biconexe;
S este cea a parcurgerii în adâncime;k avem un descendent direct x pentru care nivel[k] <= nma[x], vom elimina de pe stivă nodurile până la nodul x, inclusiv acesta;
k reprezintă o componentă biconexă;x, nu până la k, deoarece între acestea, pe stivă, pot fi noduri din altă componentă biconexă.nivel[k] <= nma[x] are loc întotdeauna pentru rădăcina arborelui DFS, chiar dacă acesta nu este punct de articulație. În acest caz se determină o componentă biconexă din care face rădăcina. Acest lucru se întâmplă și când graful dat este biconex: determinarea componentei biconexe se face la revenirea în rădăcină....
V[k] ← true
Adaugă(S,k)
....
//determinare componente biconexe
dacă nivel[x] ≤ nma[k] atunci
câttimp Vârf(S) ≠ x execută
Vârf(S) se adugă la componenta curentă
Elimină(S)
sf_câttimp
x se adaugă la componenta curentă
Elimină(S)
k se adaugă la componenta curentă
sf_dacă Un arbore este un graf conex și aciclic. Se mai numește și arbore liber.
Următoarele propoziții sunt adevărate:
n vârfuri are n-1 muchii.
Pentru un arbore se poate stabili un nod special, numit rădăcină. Putem spune că “agățăm” arborele în rădăcină, iar restul nodurilor cad.
Mai jos avem trei arbori cu rădăcină. Toți pornesc de la arborele de mai sus, dar diferă prin alegerea rădăcinii.
|
|
|
Fie un arbore cu rădăcina r și x un nod în acest arbore. Atunci:
x orice nod y, diferit de x, aflat pe lanțul de la rădăcină la x;
y este ascendent al lui x și există muchia (y,x), atunci y se numește ascendent direct al lui x sau tatăl lui x;
y este descendent al nodului x, diferit de y, dacă x aparține lanțului de la r la y;
(x,y), atunci y este descendent direct sau fiu al lui x;x reprezintă nivelul sau adâncimea nodului x;Fie arborele următor:

3;4 sunt 5, 2 și 3. Ascendentul direct (tatăl) al nodului 4 este nodul 5;2 sunt 1 7 10 5 4 6. Descendenții direcți ai nodului 2 sunt 1 5;1 și 5 sunt frați;6 7 8 10 12 sunt frunze;0 conține doar rădăcina: 3;1 conține nodurile 2 9;2 conține nodurile 1 5 8 11;3 conține nodurile 7 10 4 12;4 conține nodul 6;4;9 8 11 12 formează un subarbore;Pentru fiecare nod al arborelui se memorează informații despre descendenții săi direcți. Este similară cu reprezentarea prin liste de adiacențe a grafurilor. Pentru arborele de mai sus avem:
F[1]={7,10}F[2]={1,5}F[3]={2,9}F[4]={6}F[5]={4}F[6]={}F[7]={}F[8]={}F[9]={8,11}F[10]={}F[11]={12}F[12]={}Pentru fiecare nod se memorează informații despre ascendenții direcți. Vom obține un vector de tați, în care:
t[r] = 0, unde r este rădăcina arboreluit[k] = tatăl nodului kPentru arborele de mai sus avem:
k |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
t[k] |
2 |
3 |
0 |
5 |
2 |
4 |
1 |
9 |
3 |
1 |
9 |
11 |
Observații
0, corespunzătoare rădăcinii;xx, y = t[x];y, t[y]z pentru care t[z]=0. acesta va fi rădăcina și ne oprim.În jurul anului 1960 a fost descoperit un algoritm pentru drumuri în grafuri orientate. Descoperirea a fost făcută independent de către trei oameni de stiință în domeniul algoritmilor: Robert Floyd, Bernard Roy și Stephen Warshall.

Algoritmul se regăsește sub diferite denumiri care conțin numele descoperitorilor, este bazat pe programarea dinamică și poate fi utilizat în următoarele două moduri:
x y dacă există drum de la x la y – este de regulă cunoscut sub numele Roy-WarshalAmbele variante permit și reconstituirea unor drumuri între două noduri date.
În 1736, matematicianul elvețian Leonard Euler a rezolvat o problemă cunoscută astăzi ca “Problema celor șapte poduri din Königsberg”. Prin orașul Königsberg, azi Kaliningrad trece un râu pe care sunt două insule, acestea și malurile fiind unite prin poduri ca în imaginea de mai jos.

Leonard Euler a demonstrat că nu este posibil ca o persoană să traverseze fiecare pod o singură dată. În onoarea sa, o categorie specială de grafuri se numesc grafuri euleriene.

În graful de mai sus ciclul (1 2 4 5 3 6 5 2 3 1) este eulerian.
Un graf neorientat fără vârfuri izolate este eulerian dacă și numai dacă este conex și toate vârfurile au grad par.
Un graf neorientat fără vârfuri izolate conține un lanț eulerian, dacă și numai dacă este conex și toate vârfurile au grad par, mai puțin două. Aceste vârfuri vor fi extremitățile lanțului eulerian.
Pentru determinarea unui ciclu eulerian se pot folosi mai mulți algoritmi. Unul dintre aceștia este asemănător cu parcurgerea în adâncime. Vom folosi o stivă (eventual memoria STACK prin intermediul recursivității):
1;k – nodul din vârful stiveix adiacente cu k. Eliminăm muchia [k,x] și adăugăm nodul x pe stivă (apel recursiv)
k într-o listăk din stivăImportant:
Secvență C++:
Considerăm un graf cu n vârfuri, memorat prin intermediul matricei de adiacență, A[][]. Tabloul L[] reprezintă lista în care se memorează ciclul eulerian. Toate variabilele sunt globale:
void Euler(int k)
{
for(int i = 1 ; i <= n ; i ++)
if(A[k][i] == 1)
{
A[k][i] = A[i][k] = 0;
Euler(i);
}
L[++p] = k;
}
...
Euler(1);
...
Algoritmul de mai sus poate fi utilizat și pentru determinarea unui lanț eulerian. Parcurgerea trebuie să înceapă însă din unul dintre vârfurile cu grad impar.
Există numeroase puzzle-uri care constau în desenarea unei figuri fără a lua creionul de pe foaie și fără a trece de mai multe ori pe aceiași linie. Probabil cel mai cunoscut este “plicul”:

Care dintre următoarele figuri se pot desena în cest mod? Cum?





Problema comis voiajorului este o problemă celebră de informatică: Un comis-voiajor (agent comercial) trebuie să viziteze n orașe. Cunoscându-se șoselele existente între orașe, să se determine o modalitate (toate modalitățile) prin care comis-voiajorul poate parcurge fiecare oraș o singură dată și se întoarce în orașul de plecare.
Dacă asociem problemei un graf neorientat, constatăm că trebuie să determinăm un ciclu elementar (toate ciclurile elementare) care trece prin toate vârfurile grafului. Un astfel de ciclu se numește ciclu hamiltonian.
Definiții:
Pentru un graf orientat se pot definii noțiuni similare, de drum hamiltonian și circuit hamiltonian
Exemplu:

În graful de mai sus sunt evidențiate muchiile care fac parte dintr-un ciclu hamiltonian: (1, 2, 5, 4, 6, 3).
În anumite condiții se poate stabili că un graf dat este hamiltonian. Dar aceste condiții sunt “de suficiență”. Dacă nu sunt îndeplinite, nu înseamnă că graful nu este hamiltonian!
Teoreme:
G=(X,U) un graf neorientat cu \( n \) vârfuri și un lanț hamiltonian \( v_1, v_2, \cdots, v_n \). Dacă \( d(v_1) + d(v_n) \geq n\), atunci graful este hamiltonian, unde \( d(x) \) este gradul vârfului \(x \).G=(X,U) un graf neorientat cu \( n \) vârfuri. Dacă pentru orice pereche de vârfuri neadiacente distincte \( v_i, v_j \) avem relația \( d(v_i) + d(v_j) \geq n\), atunci graful este hamiltonian.Considerăm un graf neorientat ponderat (cu costuri) conex G. Se numește arbore parțial un graf parțial al lui G care este arbore. Se numește arbore parțial de cost minim un arbore parțial pentru care suma costurilor muchiilor este minimă.
Dacă graful nu este conex, vorbim despre o pădure parțială de cost minim.
Algoritmul lui Prim permite determinarea unui arbore parțial de cost minim (APM) într-un graf ponderat cu N noduri.
Determinarea APM-ului se face astfel:
Observație: arborele parțial de cost minim al unui graf neorientat nu este unic, însă toate APM-urile vor avea același cost.
Mai jos este descris modul în care se aleg nodurile care se adaugă în arbore pentru un graf ponderat cu N=9 noduri:
Nodul ințial este 1. Costul curent al APM este 0
Se adaugă nodul 2. Muchia folosită este (1,2). Costul curent al APM este 40
Se adaugă nodul 3. Muchia folosită este (2,3). Costul curent al APM este 120
Se adaugă nodul 9. Muchia folosită este (3,9). Costul curent al APM este 140
Se adaugă nodul 6. Muchia folosită este (3,6). Costul curent al APM este 180
Se adaugă nodul 7. Muchia folosită este (6,7). Costul curent al APM este 200
Se adaugă nodul 8. Muchia folosită este (7,8). Costul curent al APM este 210

Se adaugă nodul 4. Muchia folosită este (3,4). Costul curent al APM este 280

Se adaugă nodul 5. Muchia folosită este (4,5). Costul curent al APM este 370
Algoritmul poate fi implementat în mai multe moduri, cu complexități diferite.
N-1 ori):
Față de varianta anterioară se evită căutarea propriu zisă a nodului din arbore, căutându-se efectiv numai nodul din afara acestuia. Pentru aceasta se păstrează un șir d[] cu următoarea semnificație: pentru un nod k încă neadăugat în arbore, d[k] reprezintă costul minim al unei muchii având o extremitate k și o extremitate în arbore; dacă o asemenea muchie nu există d[k] = INFINIT.
Dacă determinarea succesivă a nodurilor din afara arborelui se face prin parcurgerea șirului d[], complexitatea devine O(N2).
Se poate evita parcurgerea șirului d[] prin memorarea nodurilor din arbore într-o structură de date de tip heap, în vârful heap-ului fiind nodul k pentru care d[k] are valoare minimă. În acest fel complexitatea algoritmului devine O(N logN).