Codificarea arborilor

Codificarea arborilor

Definitie: Un graf G = (V, E) este arbore daca si numai daca G este conex si aciclic.

Sa se realizeze un program pentru codificarea Neville a arborilor.

Codificarea Neville

Fie T = (V, E) un arbore. V - multimea varfurilor care apartin arborelui T, E - multimea muchiilor arborelui T.

V =

Codificare Neville: se da un arbore T si in urma codificarii Neville obtinem un vector cod.

Algoritm:

1. Se determina varfurile de grad 1 si se noteaza in vectorul cod varfurile de care acestea sunt adiacente, cu varfurile de grad 1 parcurse in ordine crescatoare.
2. Se sterg din arbore varfurile de grad 1 si se repeta 1.
3. Algoritmul se termina dupa ce vectorul cod are n-2 componente. Ultimele 2 componente ale vectorului cod se completeaza cu ultimele 2 noduri ramase in arbore(acestea formand de fapt o singura muchie) .

Exemplu:

Implementarea algoritmului:

#include<stdlib.h>

#include<stdio.h>

#include<iostream>

#include<conio.h>

using namespace std;

int m[100][100],c[100];

int codificare_neville(int n)

if( s == 1 )//daca am gasit un nod de gradul 1 adaugam in vectorul cod

for(i = 0;i < p; i++)//stergem nodul de grad 1(facand 0 pe linia si coloana respectiva)

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

}

return k;

void afisare(int k)

int main()

afisare( codificare_neville(n) );

system('pause');

getch();

return 0;

Exemplu:

Input:

Output: 2 1 1 2 4 5 2 4

Sa se realizeze un program pentru decodificarea Neville a arborilor.

Decodificarea Neville

Inainte de prezenta algoritmul de decodificare trebuie precizate cateva observatii.

Observatii:

1. In vectorul cod singurele varfuri care nu apar sunt varfurile de grad 1.
2. in general, un varf al arborelui apare in vectorul cod de un numar de ori egal cu gradul sau minus 1.

Avem V = - multimea varfurilor arborelui care trebuie construit in urma vectorului cod.

Decodificare Neville: se da un vector cod si in urma aplicarii algoritmului de decodificare rezulta un arbore.

Algoritm:

1. Se determina varfurile care nu apar in vectorul cod, acestea fiind varfurile de gradul 1 din arbore.
2. Se parcurg crescator si se genereaza muchiile care conecteaza aceste varfuri de varfurile corespunzatoare din vectorul cod, incepand cu prima componenta.
3. Se sterg varfurile de gradul 1 determinate anterior si se sterg componentele corespunzatoare din vectorul cod, se reia pasul 2.
4. Algoritmul se opreste cand se epuizeaza elementele din vectorul cod, adica pana cand sunt generate n-2 muchii. Ultima muchie este determinata de ultimele 2 noduri ramase in multimea varfurilor.

Exemplu:

Etapa I:

V =

Muchiile obtinute: (2,3) ; (1,6) ; (1,7) ; (2,8) ; (4,9) ; (5,10).

Etapa a II-a:

Muchiile obtinute: (1,2) ; (4,5).

Etapa a III-a:

V = V - S =

C = Ø.

Ultima muchie: (2,4)

Implementarea algoritmului:

#include<stdio.h>

#include<stdlib.h>

#include<iostream>

using namespace std;

int m[100][100],c[100],v[100];

int decodificare_neville(int l,int n)

}

for( i = 0;i < p;i++ )

for(i = 0;i < p; i++)

k += p; //ca sa stim unde am ramas in c(cod) si sa nu mai parcurgem odata

p = 0;//p=nr de elemente ale lui s.inainte de a-l creea din nou trebuie ca p sa fie 0

}

m[ v[0]-1 ][ v[1]-1 ] = 1; //creez muchia n-1 cu ultimele doua noduri ramase in v

m[ v[1]-1 ][ v[0]-1 ] = 1;

//afisarea matricei de adiacenta corespunzatoare arborelui creat

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

return 0;

int main()

Exemplu:

Input: 2 1 1 2 4 5 2 4

Output:

Sa se realizeze un program pentru codificarea Pruffer a arborilor.

Codificarea Pruffer

Fie T = (V, E) un arbore. V - multimea varfurilor care apartin arborelui T, E - multimea muchiilor arborelui T.

V =

Codificare Pruffer: se da un arbore T si in urma codificarii Neville obtinem un vector cod.

Algoritmul are n-2 pasi:

1. Se determina varfurile de gradul 1 care are eticheta minima.
2. Se noteaza in vectorul cod varful de care este adiacent.
3. Se sterg varfurile de grad 1.
4. Se repeta incepand cu pasul 1.

Observatie: In ultimele 2 varfuri ramase exista varful cu eticheta maxima.

In continuare prezentam pasii care trebuiesc facuti pentru a obtine vectorul cod in urma aplicarii algoritmului lui Pruffer:

X₁ = 3; C₁ = 2; T = T - ;

X₂ = 6; C₂ = 1; T = T - ;

X₃ = 7; C₃ = 1; T = T - ;

X₄ = 1; C₄ = 2; T = T - ;

X₅ = 8; C₅ = 2; T = T - ;

X₆ = 2; C₆ = 4; T = T - ;

X₇ = 9; C₇ = 4; T = T - ;

X₈ = 4; C₈ = 5; T = T - ;

COD = 2 1 1 2 2 4 4 5.

Implementarea algoritmului:

#include<stdlib.h>

#include<stdio.h>

#include<conio.h>

#include<iostream>

using namespace std;

int m[100][100],c[100];

int codificare_pruffer(int n)

if( s == 1 )

return k;

void afisare(int k)//afisam vectorul cod

int main()

afisare( codificare_pruffer(n) );

system('pause');

getch();

return 0;

Exemplu:

Input:

Output: 2 1 1 2 2 4 4 5

Sa se realizeze un program pentru decodificarea Pruffer a arborilor.

Decodificarea Pruffer

Inainte de prezenta algoritmul de decodificare trebuie precizate cateva observatii.

Observatii:

1. In vectorul cod singurele varfuri care nu apar sunt varfurile de grad 1.
2. In general, un varf al arborelui apare in vectorul cod de un numar de ori egal cu gradul sau minus 1.

Avem V = - multimea varfurilor arborelui care trebuie construit in urma vectorului cod.

Decodificare Pruffer: se da un vector cod si in urma aplicarii algoritmului de decodificare rezulta un arbore.

Algoritmul are n-2 pasi si inca o operatie:

1. Se determina varfurile care nu apar in vectorul cod.
2. Se determina intre acestea varful de eticheta minima.
3. Se genereaza muchia care conecteaza acest varf de prima componenta din vectorul cod.
4. Se sterge varful cu eticheta minima determinat anterior si se sterge prima componenta din vectorul cod.
5. Se repeta reia pasul 1 de n-2 ori si se genereaza n-2 muchii.
6. A n-1 muchie este generata de ultimele componente ale lui V.

Implementarea algoritmului:

#include<stdio.h>

#include<stdlib.h>

#include<iostream>

#include<conio.h>

using namespace std;

int m[100][100],c[100],v[100];

int decodificare_pruffer(int l,int n)

m[ c[k]-1 ][ s ] = 1;//creem muchia cu primul element din cod si varful gasit anterior

m[ s ][ c[k]-1 ] = 1;

o++;//crestem numarul de muchii create.

for(i = 0;i < nr; i++) if(v[i] == s+1)//cautam pozitia pe care se afla s

for(i = s;i < nr-1; i++) v[i] = v[i+1];// calculam v=v-s

nr--;//scadem nr de elemente ale lui v

k+=1; //memoram pozitia din cod

m[ v[0]-1 ][ v[1]-1 ]=1;//cream muchia n-1 cu ultimele doua noduri ramase in v

m[ v[1]-1 ][ v[0]-1 ]=1;

//afisarea matricei de adiacenta corespunzatoare arborelui creat

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

return 0;

int main()

for( i = 0;i < n; i++ ) v[i] = i+1;//cream V

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

for(j = 0;j < n; j++) m[i][j] = 0;//initializam matricea de adiacenta cu 0

decodificare_pruffer(l,n);

system('pause');

getch();

return 0;

Exemplu:

Input:

Output: