Recapitulare pentru teza
Clasa a XI-a

---

1.Grafuri  orientate
-notiuni :
-arc, varf, graf partial, subgraf, grad varf, grad exterior, grad interior
-drum, lungime drum, drum elementar
-circuit, circuit elementar

Exercitii propuse:
a) Dandu-se un graf orientat identificati notiunile anterioare.
b) Desenati un graf in care sa evidentiati notiunile anterioare

-metode de memorare:
-matricea de adiacenta
-lista de adiacenta

Exercitii propuse:
a) Dandu-se un graf orientat identificati notiunile anterioare.
b) Desenati un graf in care sa evidentiati notiunile anterioare
c) Sa se memoreze un graf orientat utilizand matricea de adiacente sau lista de adiacente (citire de la tst sau din fisier). Program.
d) Din matricea de adiacente sa se determine: gradul interior, exterior, gradul total, varfurile izolate

-metode de parcurgere:
-parcurgere in latime
-parcurgere in adancime

Exercitii propuse:
a) Dandu-se un graf orientat sa se parcuga bf sau df (succesiune de varfuri parcuse)
b) Parcurgere bf sau df ( recursiv, graful memorat prin matrice). Program.

-componente tare conexe
-componenta tare conexa careia ii apartine un varf
-numarul de componente tare conexe
-graf tare conex

Exercitii propuse:
a) Dandu-se un graf orientat sa se determine componenta tare conexa careia ii apartine un varf. Program. Exemplificare
            b) Dandu-se un graf orientat sa se determine daca este tare conex. Program. Exemplificare

2.Grafuri  neorientate
-notiuni :
-muchie, nod, graf partial, subgraf, grad nod
-lant, lungime lant, lant elementar
-ciclu, ciclu elementar
-circuit hamiltonian, graf hamiltonian
-graf eulerian

Exercitii propuse:
a) Dandu-se un graf neorientat identificati notiunile anterioare.
b) Desenati un graf in care sa evidentiati notiunile anterioare

-metode de memorare:
-matricea de adiacenta
-lista de adiacenta

Exercitii propuse:
a) Dandu-se un graf neorientat identificati notiunile anterioare.
b) Desenati un graf in care sa evidentiati notiunile anterioare
c) Sa se memoreze un graf neorientat utilizand matricea de adiacente sau lista de adiacente (citire de la tst sau din fisier). Program.
d) Din matricea de adiacente sa se determine: gradul unui nod, nodurile izolate

-metode de parcurgere:
-parcurgere in latime
-parcurgere in adancime

Exercitii propuse:
a) Dandu-se un graf neorientat sa se parcuga bf sau df (succesiune de varfuri parcuse)
b) Parcurgere bf sau df ( recursiv, graful memorat prin matrice). Program.

-componente  conexe
-componenta conexa careia ii apartine un nod
-numarul de componente  conexe
-graf  conex

Exercitii propuse:
a) Dandu-se un graf neorientat sa se determine componenta  conexa careia ii apartine un nod. Program. Exemplificare
            b) Dandu-se un graf neorientat sa se determine daca este  conex. Program. Exemplificare

3.Arbori si arborescente

Arbori

-notiuni:
-radacina
-ascendent, descendent, frunze
-adancimea unui arbore
-conditia ca un graf neorientat sa fie arbore

-metode de memorare:
-matrice de adiacente
-liste
-vector de tip tata

-metode de parcurgere:
-parcurgere in latime
-parcurgere in adancime
-parcurgere utilizand vectorul tata si functia drum( )

Exercitii propuse:
Exemplificari pe un arbore a notiunilor precedente
Prelucrari pe niveluri utilizand functia drum( ). Program
Prelucrari incepand de la un nod pana la radacina utilizand functia drum( ). Program

Arborescente

-notiuni:
-radacina
-ascendent, descendent, frunze
-adancimea unei arborescente
-conditia ca un graf orientat sa fie arborescenta

-metode de memorare:
-matrice de adiacente
-liste
-vector de tip tata

-metode de parcurgere:
-parcurgere in latime
-parcurgere in adancime
-parcurgere utilizand vectorul tata si functia drum( )

Exercitii propuse:
Exemplificari pe o arborescenta a notiunilor precedente
Prelucrari pe niveluri utilizand functia drum( ). Program
Prelucrari incepand de la un nod pana la radacina utilizand functia drum( ). Program

Arbori binari

-notiuni:
-notiunea de arbore binar
-descendenti: stang, drept
-subarbori: stang, drept

-metode de memorare:
-matrice de adiacente
-liste
-vector de tip tata
-memorare cu ajutorul a 2 vectori (stang si drept)
-memorare in heap

-metode de parcurgere:
-parcurgere in latime
-parcurgere in adancime
-parcurgere utilizand vectorul tata si functia drum( )
-parcurgeri specifice: in inordine, in postordine, in preordine

Exercitii propuse:
Exemplificari pe un arbore binar a notiunilor precedente

Probleme propuse:

1. Dintr-un fisier se citesc n denumirile a n localitati. Din fisier se citesc perechile de localitati intre care exista drum direct. Sa se detrmine daca exista drum (direct sau nu)  intre doua localitati citite de la tastatura.

Ex. Date de intrare:
5
loco1 loco2 loco3 loco4 loco5 loco6
1 2
2 3
1 3
4 5

Pentru: loco1 loco5 se afiseaza  "nu exista drum"
Pentru loco1 loco3 se afiseaza "exista drum"

2. Un graf neorientat este bipartit daca exista o partitie a multimii nodurilor in doua multimi A si B astfel incat oricare doua varfuri din aceeasi multime sa nu fie adiacente. Sa se scrie un program care verifica daca un graf este bipartit si in caz afirmativ sa se tipareasca multimile A si B

3. Intr-un fisier sunt memorate  numele a n persoane. Intre cele n persoane se stabileste o relatie de ierarhie (in varful ierarhiei exista o singura persoana) . In fisier sunt scrie pe prima linie n, pe linia a doua cele n nume iar pe linia a treia vectorul de tip tata asociat.
a) sa se afiseze persoanele care nu au subordonati
b)sa se afiseze persoana din varful ierarhiei
c) sa se afiseze toti sefii (directi sau indirecti ai unei personei)
d) pe cate niveluri este organizata ierarhia

4.  Intr-un fisier sunt memorate n numere naturale. Intre cele n numere se stabileste o relatie de tip arbore oarecare. In fisier sunt scrie pe prima linie n, pe linia a doua cele n valori iar pe linia a treia vectorul de tip tata asociat.
a) sa se determine adancimea arborelui (se considera radacina pe nivelul 0)
b) sa sa afiseze nodurile de pe nivelul x si numerele asociate
c) sa se determine suma cifrelor numerelor asociate de pe nivelul y
d) sa se determine pe ce nivel se gaseste numarul z
e) Sa se se afiseze numerele prime  asociate arborelui pe linie ascendenta  incepand de la un nod pana la radacina. Numarul de ordine al nodului de pornire se citeste de la tastatura. 

Exemplu:

7

12 14 13 25 43 82 21 cele 7 numere

0 1 1 3 3 1 5

se citeste nodul 7

Se afiseaza 43 13

5.Sa se reprezinte un arbore binar utilizand heap-ul si sa se parcurga  (inordine, preordine, postordine).

6.Sa se reprezinte un arbore binar utilizand heap-ul si sa se parcurga  (inordine, preordine, postordine). Fiecare nod are asociat un numar de ordine si informatia utila un numar intreg.
a) sa se determine suma cheilor (numerelor asociate)
b) sa se caute o valoare. Sa se afiseze un mesaj daca valoarea se gaseste
c) sa se determine valoarea minima a  cheilor asociate
d)sa se afiseze cheile impare ale unui arbore binar. Cate sunt?
e) se calculeze produsul cheilor pozitive ale unui arbore binar
f) sa se afiseze subordonatii stangi
h) sa se afiseze subordonatii lui x

7. Determinati si afisati frunzele unui arbore binar. Cate sunt? Care este suma numerelor de ordine?

8. Fie doi arbori binari memorati static (se utilizeaza doi vectori: stang si drept). Sa se determine daca cei doi arbori binari sunt egali.

9. Sa se afiseze nodurile dintr-un arbore binar care au exact un succesor.

10. Sa se determine daca un arbore binar este echilibrat (nodurile neterminale au exact 2 succesori).

11. Sa se afiseze toti descendentii stanga ai unui arbore binar.

12. Sa se inlocuiasca intr-un arbore binar cheia x cu cheia y.

13. Fie un graf orientat memorat prin m.a. Se stie ca graful reprezinta o arborescenta. Sa se determine daca arborescenta este arbore binar. In caz afirmativ sa se determine radacina.

14. Sa se determine numarul cromatic al unui graf neorientat (numarul minim de culori cu care poate fi colorat graful astfel incat oricare doua noduri adiacente sa nu aiba aceeasi culoare). Sa se genereze toate posibilitatile de colorare a grafului