Algoritmul lui Kruskal

Arborele partial de cost minim poate fi construit muchie cu muchie, dupa urmatoarea metoda a lui Kruskal (1956): se alege intai muchia de cost minim, iar apoi se adauga repetat muchia de cost minim nealeasa anterior si care nu formeaza cu precedentele un ciclu. Alegem astfel X–1 muchii. Este usor de dedus ca obtinem in final un arbore. Este insa acesta chiar arborele partial de cost minim cautat?
Inainte de a raspunde la intrebare, sa consideram, de exemplu, graful din Figura 6.1.a. Ordonam crescator (in functie de cost) muchiile grafului: {1, 2}, {2, 3}, {4, 5}, {6, 7}, {1, 4}, {2, 5}, {4, 7}, {3, 5}, {2, 4}, {3, 6}, {5, 7}, {5, 6} si apoi aplicam algoritmul. Structura componentelor conexe este ilustrata, pentru fiecare pas, in Tabelul 1.

Figura 1 Un graf si arborele sau partial de cost minim.






Tabelul 1 Algoritmul lui Kruskal aplicat grafului din Figura1a.

Multimea A este initial vida si se completeaza pe parcurs cu muchii acceptate (care nu formeaza un ciclu cu muchiile deja existente in A). In final, multimea A va contine muchiile {1, 2}, {2, 3}, {4, 5}, {6, 7}, {1, 4}, {4, 7}. La fiecare pas, graful partial formeaza o padure de componente conexe, obtinuta din padurea precedenta unind doua componente. Fiecare componenta conexa este la randul ei un arbore partial de cost minim pentru varfurile pe care le conecteaza. Initial, fiecare varf formeaza o componenta conexa. La sfarsit, vom avea o singura componenta conexa, care este arborele partial de cost minim cautat (Figura 1b).Ceea ce am observat in acest caz particular este valabil si pentru cazul general.
In vectorul V vom sorta in ordine crescatoare numarul muchiilor in ordine crescatoare in functie de costul fiecareia.In vectorul X vom retine pentru fiecare nod numarul componenetei din care face parte acesta si care se schimba o data ce adaugam o noua muchie.Modificarea acestuia se face in functie de apartenenta uneia dintre extremitati la un arbore cu mai mult de un nod.In multimea B se retin numerele de ordine ale muchiilor ce apartin arborelui de cost minim.


procedure sortare; {se face sortarea intr-un vector v a muchiilor in ordine
var i,k,min:integer; crescatoare a costurilor muchiilor}
c:vector;
begin
c:=a;k:=0;
repeat
min:=maxint;
for i:=1 to m do
if (c[i].cost0) then
begin
min:=c[i].cost;
j:=i;
end;
inc(k);
v[k]:=j;
c[j].cost:=0;
until k=m;
end;
procedure kruskal;
var i,k,j:integer;
begin
k:=0;
for i:=1 to m do
begin
if (x[a[v[i]].vf1]=0) and (x[a[v[i]].vf2]=0) then {ambele extremitati
begin formeaza un arbore cu un singur nod}
b:=b+[v[i]];
inc(k);
x[a[v[i]].vf1]:=k;
x[a[v[i]].vf2]:=k;
end
else
if x[a[v[i]].vf1]<>x[a[v[i]].vf2] then {se verifica daca extremitatile
begin muchiei sunt din arbori diferiti}
b:=b+[v[i]];
if (x[a[v[i]].vf1]<>0) and (x[a[v[i]].vf2]<>0) then
begin
for j:=1 to n do
if (x[j]=x[a[v[i]].vf1]) and (a[v[i]].vf1<>j) then
x[j]:=x[a[v[i]].vf2];
x[a[v[i]].vf1]:=x[a[v[i]].vf2];
end;
if (x[a[v[i]].vf1]=0) then
x[a[v[i]].vf1]:=x[a[v[i]].vf2];
if (x[a[v[i]].vf2]=0) then
x[a[v[i]].vf2]:=x[a[v[i]].vf1];
end;
suma:=suma+a[v[i]].cost;
end;
end;
begin {main}
clrscr;
citire;
for i:=1 to m do
v[i]:=0;
sortare;
writeln('Vectorul sortat in ordinea muchiilor este:');
for i:=1 to m do
write(v[i],' ');
writeln;
for i:=1 to n do
x[i]:=0;
b:=[];
kruskal;
writeln('Muchiile arborelui sunt:');
suma:=0;
for i:=1 to m do
if i in b then
begin
writeln('Muchia ',i,':',a[i].vf1,' ',a[i].vf2,' de cost ',a[i].cost);
suma:=suma+a[i].cost;
end;
write('Costul arborelui este:',suma);
readkey;
end.
Category: 0 comentarii

Grafuri. Parcurgerea grafurilor. Sortarea topologica

Scop:

Parcurgerea in latime se foloseste:
- pentru Inteligenta Artificiala (metoda neinformata de cautare... mai multe la cursul de IA);
- intr-o multime de aplicatii din teoria grafurilor (in special legate de drum minim de la un nod dat la un alt nod, componente conexe, grafuri bipartite);
- in jocuri pe calculator, pentru gasirea drumurilor, in special in jocuri Real Time Strategy (un mic exemplu in aplicatie);

Parcurgerea in adancime se foloseste:
- pentru Inteligenta Artificiala (metoda neinformata de cautare... mai multe la cursul de IA), insa combinarea sa cu euristici poate fi mai fructuoasa decat la parcurgerea in latime;
- sortarea topologica si alte aplicatii cu grafuri legate de componente conexe si tare conexe.


1. Parcurgerea in latime (Breadth First Search, BFS):

1.1. Teoria

Parcurgerea in latime foloseste o coada (Q) intr-un mod asemanator celui folosit de algoritmul AC-3. Initial in aceasta coada se gaseste doar nodul sursa. Vizitand pe rand vecinii sai ii adaugam si pe ei in coada. La sfarsit, dupa ce nu mai sunt vecini ai sursei nevizitati, scoatem nodul sursa din coada.


Pentru fiecare din nodurile prezente in coada, aplicam procedura de mai sus. Atentie insa: vizitand vecinii unui nod trebuie sa verificam ca acestia nu au mai fost deja vizitati (adica sunt inca albi).
. . .



In afara de coada q mai sunt necesare sau utile cateva structuri de date.
a) Putem diferentia intre nodurile nevizitate, cele asezate in coada si cele complet prelucrate printr-un vector denumit culoare:
c[nod] = alb, daca nodul nu a fost vizitat
gri, daca nodul a fost vizitat si asezat in q
negru, daca nodul a fost prelucrat si scos din q
b) Un vector d (distanta) care sa retina distanta (in numar de muchii) fata de sursa se poate dovedi util in unele probleme.
c) Vectorul de parinti p este necesar pentru a reface drumul de la sursa la un alt nod dupa parcurgere.


1.2. Algoritmul

Algoritmul conform specificatiilor de mai sus:

// =============== initializari ===================
pentru fiecare nod u
{
c[u] = alb;
d[u] = infinit;
p[u] = null;
}
c[sursa] = gri;
d[s] = 0;
q = {s};
// ================ algoritm ===================
cattimp (q nu este vida)
{
v = extrage nod din coada q;
pentru fiecare u dintre vecinii lui v
if (c[u] == alb)
{
c[u] = gri;
p[u] = v;
d[u] = d[v]+1;
insereaza in coada q (u);
}
c[v] = negru;
}

Obs: Pentru ca muchiile care unesc noduri deja gri nu sunt practic folosite, se intuieste asezarea muchiilor folosite intr-un graf conex si fara cicluri (adica un arbore):
Obs: Daca graful are mai multe componente conexe, algoritmul, in forma data aici, va parcurge doar componenta din care face parte nodul sursa. Pe grafuri alcatuite din mai multe componente conexe se vor obtine astfel mai multi arbori, cate unul pentru fiecare componenta.








2. Parcurgerea in adancime (Depth First Search, DFS):

2.1. Teoria:

DFS poate fi imaginata mai usor sub forma recursiva. Alegem un nod sursa. Dupa ce il marcam ca vizitat, consideram pe rand fiecare dintre vecinii sai ca fiind sursa. Muchiile catre noduri deja vizitate (inclusiv nodul original) practic nu vor conta (desi trebuiesc testate). In desenele de mai jos incerc sa simulez perspectiva nodului din pasul curent (observati cum acesta nu are acces la nodurile incetosate din cauza vecinilor deja vizitati):

Semnificatia culorilor ramane aceeasi ca la BFS:
- alb daca nodul nu a fost vizitat;
- gri daca nodul a fost vizitat dar nu i-am parcurs toti vecinii;
- negru daca am parcurs toti vecinii nodului.
Vom mai introduce doua variabile care se vor dovedi utile in unele aplicatii:
- tDesc (timpul descoperirii): pasul la care se marcheaza nodul cu gri;
- tFin (timpul final): pasul la care se marcheaza nodul cu negru.







2.2. Algoritmul:

Punand cap la cap informatiile de pana acum obtinem urmatorul algoritm:


// ================== initializari ====================
pentru fiecare nod u al grafului
{
culoare[u] = alb;
p[u] = NULL;
tDesc = 0;
tFin = 0;
}
timp = 0;

// === pentru a ne asigura ca se parcurg toate componentele conexe =
pentru fiecare nod al grafului
daca (culoare[nod] == alb)
PARCURGE(u);

// ==================== va parcurge o componenta conexa =======
PARCURGE(u)
{
culoare[u] = gri;
tDesc[u] = ++ timp;
pentru fiecare v vecin al lui u
{
daca (culoare[v] == alb)
{
p[v] = u;
PARCURGE[v];
}
}
culoare[u] = negru;
tFin[u] = ++timp;
}


Obs: Algoritmul este facut pentru a acoperi toate nodurile, chiar daca graful are mai multe componente conexe. Metoda PARCURGE corespunde acoperirii unei componente conexe.

Obs: Ganditi-va la asemanarile cu BKT. Daca am avea un arbore in care fiecare nod ar reprezenta asocierea unei variabile cu o valoare... si de la fiecare nod s-ar porni catre toate atribuirile posibile ale urmatoarei variabile... parca seamana, nu? Mai mult decat atat, si la DFS, ca si la BKT, ne putem intreba in ce ordine sa luam vecinii ca sa ajungem mai repede intr-un nod anume...






Obs.: Si la DFS, ca si la BFS, in urma parcurgerii se obtin arbori. Acestia se numesc arbori de adancime. Spre exemplu:

Evident, pe acest arbore s-ar putea adauga si muchiile pe care nu le-am folosit in parcurgere, dar l-ar face sa nu mai fie arbore. Totusi, in cazul grafurilor orientate, si aceste muchii au o semnificatie speciala.

Am transformat graful din exemplul precedent intr-unul orientat si i-am mai adaugat cateva noduri. Si de data asta i-am figurat toate muchiile. Acestea vor fi:
- muchii inainte: muchia (1,4);
- muchii inapoi: muchia (3,1);
- muchii de traversare: muchia (9,1).






2.3. Sortarea topologica:

Se da un graf orientat. Orientarea muchiilor corespunde unei relatii de ordine de la nodul sursa catre cel destinatie. Ni se cere sa asezam nodurile in asa fel incat pentru orice muchie (u,v), u sa apara inaintea lui v.
Sortarea topologica are sens numai daca este aplicata asupra unui graf orientat si aciclic. De ce? Daca nu ar fi graf orientat, nu am avea despre ce ordine sa discutam. Iar un ciclu ar fi indeajuns pentru a nu putea stabili o ordine intre nodurile care il alcatuiesc.
Sa consideram urmatorul exemplu:

Ei bine, de aici si pana la a obtine o succesiune de noduri ordonate nu este decat un singur pas: avem grija sa asezam nodul radacina al fiecarui subarbore intr-o stiva, iar pentru afisare scoatem pe rand cate un nod din stiva tiparind odata cu el si nodurile din arborele sau in ordinea obtinuta.

Obs: Pentru un graf dat pot exista mai multe insiruiri de noduri care sa respecte cerinta.

Convingeti-va ca solutia obtinuta este intr-adevar corecta si ca toate solutiile care se pot obtine prin aceasta metoda sunt si ele corecte.

Obs: Nu este singurul algoritm pentru sortare topologica.

Optional: Un alt algoritm pentru sortarea topologica:
Algoritmul urmator se aplica recursiv. La fiecare pas se elimina un nod in care nu intra nici o muchie, nod pe care il furnizam catre output. Prin eliminare se intelege implicit ca se elimina si muchiile adiacente nodului respectiv. Din moment ce nu erau muchii care sa intre in el, asta inseamna ca se elimina muchiile care pornesc din el.
Daca la un moment dat mai avem noduri si nu mai putem face eliminare, inseamna ca exista un ciclu in graf si nu exista sortare topologica pentru el.


3. Rezumat:

Parcurgerea in latime (BFS) foloseste o coada pentru a putea vizita toti vecinii unui nod dat inainte de a-l marca drept prelucrat. Se poate folosi inclusiv pentru determinarea drumurilor de lungime minima si returneaza cate un arbore pentru fiecare componenta conexa.
Are complexitatea O(E+V).

Parcurgerea in adancime (DFS) se poate implementa intuitiv in forma recursiva, iar principiul sau de functionare sta la baza BKT. DFS se foloseste in sortarea topologica si furnizeaza unul sau mai multi arbori de adancime. De o utilitate interesanta sunt timpii de descoperire si de finalizare a prelucrarii unui nod in cadrul operatiei de parcurgere.
Are complexitatea Θ(E+V).
Complexitatea spatiala este mai buna decat la BFS.
Category: 0 comentarii

Arbori

Notiuni introductive

     O categorie importanta de grafuri este aceea in care muchiile sun niste legaturi de tip parinte-fiu. Un astfel de graf se va numi ARBORE. 

Definitie 

 -Se numeste arbore un graf conex si fara cicluri.
 -Un arbore cu n varfuri are n-1 muchii.

Proprietati caracteristice unui arbore 

• Exista un nod in care nu intra nici un arc numit radacina arborelui.
• Cu exceptia radacinii, fiecare nod are proprietatea ca in el intra un singur arc.
Acesta leaga nodul respectiv de un alt nod numit numit predecesor sau parinte.
• Dintr-un nod pot iesi unul sau mai multe arce.Fiecare astfel de arc,leaga nodul
Respectivd de un alt nod numit Succesor sau fiu al nodului.
* Nodurile sunt organizate pe nivele primul nivel fiind ocupat de nodul radacina.
Nodurile de pe ultim nivel se caracterizeaza prin faptul ca din ele nu mai iese nici un arc ,si se numesc noduri terminale sau frunze.

• Nodurile pot contine o asa informatie utila ,carte poate fi de orice tip.\

Exemplu

Nodul  1  este radacina arborelui.

Frunzele arborelui sunt:  3,8,9.


     

     Algoritmul Prim (scris în 1957 si implementat în 1961 de catre Dijkstra) elimina acest neajuns. Se opereaza cu datele din acelasi graf. Se porneste initial, ca si în algoritmul lui Kruskal cu “n” vârfuri izolati (adica de la cele “n” varfuri, dar fara a fi trasat între aceste vârfuri vre-o muchie), urmând ca pe parcurs aceste vârfuri sa fie legate între ele de arborele cu lungimea minima.


Category: 0 comentarii

Aplicatii

1.Reprezentarea grafurilor cu ajutorul matricei de adiacenta.

Se citesc n, numarul nodurilor, si m, numarul muchiilor unui graf, de la tastatura. Se citesc, de asemenea, pe rand, m perechi de numere cu valori cuprinse intre 1 si n,reprezentand muchiile grafului.Sa se memoreze graful cu ajutorul matricei de adiacenta si sa se afiseze matricea .

#include

#define max 10

void citire(int &n, int a[max][max]);

void afisare(int n, int a[max][max]);

void initializare(int a[max][max]);

void main()

{int a[max][max], n; //a-matricea de adiacenta,n-nr noduri

initializare(a) ;

citire(n,a) ;

afisare(n,a);

}

void initializare(int a[max][max]) // initializarea matricei

{int i,j;

for(i=0;i

for(j=0;j

a[i][j]=0;

}

void citire(int &n, int a[max][max]) //construirea matricei de adiacenta

{int x,y,i,m;

cout<< ‘‘n=’’ ;cin>>n ;

cout<< ‘‘m=’’ ;cin>>m ; // m-nr muchii

for(i=1;i<=m;i++)

{cout<< “muchia”<

cin>>x>>y;

a[x][y]=1;

a[y][x]=1; //construim matricea simetrica

}

}

void afisare(int n, int a[max][max]) //afisarea matricei de adiacenta

{int i,j ;

cout<<’’Matricea de adiacenta :’’<

for(i=1 ;i<=n ;i++)

{for(j=1 ;j<=n ;j++)

cout<

cout<

}

}

2.Reprezentarea grafului cu ajutorul listelor de adiacenta .

#include

#define max 10

void citire(int &n, int l[max][max]);

void afisare(int n, int l[max][max]);

void initializare(int l[max][max]);

void main()

{int a[max][max], n; //l-matricea de adiacenta,n-nr noduri

initializare(l) ;

citire(n,l) ;

afisare(n,l);

}

void initializare(int l[max][max])

{int i,j;

for(i=0;i

for(j=0;j

a[i][j]=0;

}

void citire(int &n, int l[max][max])

{int x,y,i,m;

cout<< ‘‘n=’’ ;cin>>n ; //n-nr nodurilor

cout<< ‘‘m=’’ ;cin>>m ; // m-nr muchii

for(i=1;i<=m;i++)

{cout<< “muchia”<

cin>>x>>y; //citim doua noduri adiacente

i[x][0]++; //indicele de sfarsit a l listei nodului x

i[y]l[x][0]]=y; //element in lista nodului x

i[y][0]++ ; //indicele de sfarsit al listei nodului y

i[y][1[y][0]]=x ; //element in lista nodului x

}

}

void afisare(int n, int l[max][max])

{int i,j ;

cout<<’’Matricea de adiacenta :’’<

for(i=1 ;i<=n ;i++)

{cout<<’’nodul’’<

for(j=1 ;j<=n ;j++)

cout<

cout<

}

}

3.Reprezentarea grafurilor in memorie folosind lista muchiilor.

#include

#define max 10

Struct muchie //structura pentru memorarea unei muchii

{intx,y;

};

Muchie e[max]; //vectorul de muchii

int n,m ;

void citire() ;

void afisare() ;

void main()

{citire() ;

afisare() ;

}

void citire()

{int x,y,i ;

cout<<’’n=’’;cin>>n;

cout<<’’m=’’ ;cin>>m ; //m-nr muchii

for(j=1;i<=m;j++)

{cout<<’’muchia’’<<<’’:’’;

cin>>x>>y;

e[i].x=x //memoreaza un capat al muchiei

e[i].y=y //memoreaza al doilea capat al muchiei

}

}

void afisare()

{int i,j;

cout<<’’Graful are’’<

cout<<’’Muchiile grafului:”<

for(i=1;i<=m;i++)

cout<

}

Category: 0 comentarii

Grafuri orientate

Definiţie:
Se numeşte graf orientat sau disgraf G= (X, U), o pereche ordonată de mulţimi, unde X este o mulţime finită şi nevidă de elemente numite vârfuri sau noduri, iar U o mulţime de perechi ordonate de elemente din mulţimea X, numite arce.
Două vârfuri sunt adiacente dacă între ele există un arc. Fie arcul (X, Y) X se numeşte extremitate iniţială a arcului şi Y extremitate finală.
Se numesc două arce incidente dacă au o extremitate comună.
Se numesc succesorii unui nod X, toate vârfurile la care se poate ajunge cu un arc care iese din nodul X.
Se numeşte predecesor al nodului X, orice nod de la care porneşte un arc care intră.
Nod sursă al grafului este nodul care are mulţimea succesorilor formatş din toate celălalte noduri mai puţin el, iar mulţimea predecesorilor este mulţimea vidă.
Se numeşte nod terminal, nodul care are suma gradelor egală cu 1.
Se numeşte nod izolat, nodul care are suma gradelor egală cu 0.
Se numeşte grad intern al unui nod X şi se notează d⁻(X), numărul arcelor care intră din nodul X.
Se numeşte grad extern al unui nod X şi se notează d⁺(X), numărul arcelor care ies din nodul X.
Teoreme:
Numărul total de grafuri orientate care se pot forma cu n noduri este .
Pentru un graf orientat cu n noduri, suma gradelor interne a tuturor nodurilor este egală cu suma gradelor externe a tuturor nodurilor şi este egală cu numărul arcelor.
Category: 0 comentarii

Un graf G se numeşte graf bipartit dacă există două mulţimi nevide de noduri A si B care au proprietatea: A ∩ B= Ø iar A U B=X şi orice muchie din mulţimea U are o extremitate în mulţimea A şi o altă extremitate în mulţimea B.


Un graf bipartit se numeşte graf bipartit complet dacă pentru oricare nod X care aparţine mulţimii A şi orice nod Y care aparţine mulţimii B există o muchie care le leagă.

Se numeşte lanţ Hamiltonian,lanţul care conţine toate nodurile grafului şi este elementar.
Un graf care conţine un ciclu Hamiltonian se numeşte graf Hamiltonian.
Un ciclu se numeşte eulerian,ciclul elementar ce conţine toate muchiile grafului.
Se numeşte graf eulerian,graful care conţine un ciclu eulerian.

TEOREME


1) Un graf cu mai mult de 2 noduri este Hamiltonian dacă graful fiecărui nod este mai mare sau egal decât n/2.
2) Un graf ce nu conţine vârfuri izolate este eulerian dacă şi numai dacă este conex iar gradele tuturor noduriilor sunt numere pare.
3) Numărul de cicluri hamiltoniene dintr-un graf complet cu n noduri este (n-1)!/2.

Category: 0 comentarii

Grafuri speciale


DEFINITIE:
Graful G se numeste nul daca multimea U este vida,adica daca nu are nici o muchie.


Un graf G se numeste complet daca are proprietatea ca oricare doua noduri ale sale sunt adiacente.
TEOREMA:


Numarul de muchii intrun graf complet cu n noduri este n(n-1)/2

DEFINITIE:
Se numeste graf partial a lui G=(X,U

) graful Gp =(X,V) undeV<=U(din graful G elimin muchii)






DEFINITIE: Se numeste subgraf al grafului G=(X,U) graful Gs=(Y,V) unde y este inclus sau egal in x si toate muchiile sin multimea V apartin si multimii U care au ambele extremitati in multimea Y(adica se obtin din G prin eliminarea unor noduri si a tuturor muchiilor incidente cu aceasta.)

Se numeste graf complementar a lui G, graful Gc care are proprietatea ca 2 noduri sunt adiacente in graful complementar nu sunt adiacente in G.






TEOREME: Numarul grafurilor partiale ale unui graf cu n muchii este 2 la m. Numarul de subgrafuri ale unui graf cu n noduri este 2 la n -1.

CONEXITATE

Un graf G este conex daca are propritatea ca orice pereche de noduri distincte,exista un lant care le leaga.
Daca un graf G nu e conex se numeste componenta conexa a grafului un subgraf conex al sau maximal in raport cu aceasta proprietate(contine numar maxim de noduri din gr care au proprietatea ca sunt legate de un lant)
TEOREME:
1.numarul minim de muchii necesare ca un graf sa fie conex este n-1(n-nr. De noduri)

2.Un graf conex cu n-1 muchii si n noduri este aciclic si maximal in rap . cu aceastra propietate

3.daca un graf neorientat conex are n noduri si m muchii,nr. de muchii care trebuie eliminate pentru a obtine u graf partial conex acyclic este m-n+1
4.daca un graf are n noduri si m muchii si p componente conexe nr. De muchii care trebuie eliminate pentru a obtine un graf partial acyclic(arbore) este = m-n+p
5.Pentru a obtine dintr-un graf neorientat conex doua componente conexe nr minim de muchii este=cu gradul minim din graf.
6.numarul maxim de muchii dintr-un graf neorientat cu n noduri si p componente conexe este (n-p)(n-p+1)/2.

Category: 1 comentarii