×

Teoria grafurilor 1. Aplicații ale teoriei grafurilor 2. Noțiuni de bază 3. Grafuri orientate și neorientate 4. Reprezentarea grafurilor 4.1. Matricea de incidență 4.2. Lista de muchii 4.3. Matricea de adiacență 4.4. Liste de adiacență 5. Transformări între diferite reprezentări 5.1. Matricea de adiacență → Matricea de incidență 5.2. Matricea de adiacență → Lista de muchii 5.3. Matricea de adiacență → Liste de adiacență 5.4. Lista de muchii → Liste de adiacență 5.5. Matricea de incidență → Lista de muchii 5.6. Liste de adiacență → Matricea de adiacență 5.7. Matricea de incidență → Liste de adiacență 5.8. Liste de adiacență → Lista de muchii 5.9. Liste de adiacență → Matricea de incidență 6. Parcurgerea grafurilor 6.1. Parcurgerea în lățime 6.2. Parcurgerea în adâncime 7. Drumuri în grafuri 7.1. Algoritmul lui Dijkstra 7.2. Matricea drumurilor 8. Arborele parţial de cost minim 8.1. Algoritmul lui Kruskal 8.2. Algoritmul lui Prim 9. Verificarea cunoștințelor Arbori 10. Tipuri de arbori 11. Reprezentarea arborilor cu rădăcină 12. Reprezentarea arborilor binari 13. Parcurgerea arborilor binari 14. Arbore binar de căutare 15. Verificarea cunoștințelor
Cuprins

La ce se folosesc grafurile?

Cu ajutorul grafurilor se pot modela cu succes numeroase aplicații ale matematicii. Poate părea surprinzător faptul că, pe lângă matematică, grafurile sunt utilizate și în industrie, economie, transporturi, în diverse servicii.

Una dintre cele mai cunoscute probleme este cel al comis-voiajorului, care dorește să ajungă în diferite locații prin cel mai scurt (cel mai rentabil) drum posibil. Grafurile sunt perfect potrivite pentru vizualizarea și modelarea diferitelor rute.

Alte aplicații ale grafurilor:

  1. Facebook

    2. Conceptele de bază ale teoriei grafurilor pot fi ilustrate foarte bine printr-un exemplu legat de comunitatea Facebook.

    Utilizatorii Facebook sunt vârfurile grafului. Atunci când o persoană lansează o cerere de prietenie, către o altă persoană, intenția de a devenii prieteni, în acel moment nu este reciprocă ci doar unidirecțională, iar această situație se poate ilustra printr-un arc iar graful utilizat pentru reprezentare este un graf orientat.

    Dacă cererea de prietenie este acceptată, putem considera, că există arc în ambele direcții între cele două persoane, deci se poate ilustra printr-o muchie. Astfel de relații se pot reprezenta prin grafuri neorientate.

    sursă: https://hirmagazin.sulinet.hu/hu/tudomany/grafok-mindenhol

  2. rețele de apă
  3. rețele de căi ferate
  4. rețele de drumuri
  5. arbori genealogici
  6. colorarea hărților

Terminologie

Un graf este o pereche ordonată de mulțimi, notată G =(N, M), unde N este o mulțime finită și nevidă de elemente numite noduri sau vârfuri, iar M este o mulțime de perechi (ordonate sau neordonate) de elemente din N numite muchii (dacă sunt perechi neordonate) sau arce (dacă sunt perechi ordonate). În primul caz, graful se numește neorientat, iar în al doilea se numește orientat.
  1. Adiacență: două vârfuri se numesc adiacente, dacă sunt legate printr-o muchie/printr-un arc.
  2. Incidenţă: o muchie este incidentă cu un nod dacă îl are pe acesta ca extremitate.
  3. Incidenţă spre interior: un arc este incident spre interior cu un nod, dacă îl are pe acesta ca vârf terminal (arcul converge spre nod).
  4. Incidenţă spre exterior: un arc este incident spre exterior cu un nod dacă îl are pe acesta ca vârf inițial (arcul pleacă din nod).
  5. Buclă: un arc pentru care vârful inițial este identic cu cel terminal.
  6. Grad: gradul unui nod, dintr-un graf neorientat, este numărul de noduri adiacente cu acesta.
  7. Grad interior: gradul interior al unui nod în cazul unui graf orientat, este egal cu numărul de arce incidente spre interior.
  8. Grad exterior: gradul exterior al unui nod, în cazul unui graf orientat, este egal cu numărul de arce incidente spre exterior.
  9. Nod izolat: un nod cu gradul 0.
  10. Lanţ: este o secvenţă de noduri ale unui graf neorientat cu proprietatea că oricare două noduri consecutive sunt adiacente.
  11. Lungimea unui lanţ: numărul de muchii din care este format.
  12. Lanţ simplu: lanţul care conţine numai muchii distincte.
  13. Lanţ elementar: lanţul care conţine numai noduri distincte.
  14. Ciclu: un lanţ în care primul nod coincide cu ultimul.
  15. Ciclu elementar: ciclul format doar din noduri distincte, excepţie făcând primul şi ultimul.
  16. Drum: este o secvenţă de vârfuri ale unui graf orientat, cu proprietatea că oricare două vârfuri consecutive sunt adiacente.
  17. Lungimea unui drum: numărul de arce din care este format.
  18. Drum simplu: drumul care conţine numai arce distincte.
  19. Drum elementar: drumul care conţine numai vârfuri distincte.
  20. Circuit: un drum în care primul vârf coincide cu ultimul.
  21. Circuit elementar: circuitul format doar din vârfuri distincte, excepţie făcând primul şi ultimul.
  22. Graf parţial: un graf G1=(N, M1) reprezintă graf parţial al grafului G=(N, M) dacă M1 este inclus în M. Cu alte cuvinte G1 este graf parţial al lui G, dacă este identic, sau se obţine prin suprimarea unor muchii (respectiv arce) din G.
  23. Subgraf: un subgraf al lui G=(N, M) este un graf G1=(N1, M1) în care M1 este inclus în M, iar M1 conţine toate muchiile/arcele din M care au ambele extremităţi în N1. Cu alte cuvinte G1 este subgraf al lui G, dacă este identic, sau se obţine prin suprimarea unor noduri împreună cu muchiile/arcele incidente cu acestea.
  24. Graf complet: graf neorientat G=(N, M) în care există muchie între oricare două noduri. Numărul de muchii ale unui graf complet este |N |*|N-1|/2.
  25. Graf conex: un graf neorientat în care, pentru orice pereche de noduri există un lanţ care le uneşte.
  26. Graf tare conex: un graf orientat în care, pentru orice pereche de vârfuri (v1, v2) ,există drum de la v1 la v2 şi un drum de la v2 la v1.
  27. Componentă conexă: subgraf al grafului de referinţă, maximal în raport cu proprietatea de conexitate (între oricare două vârfuri există lanţ).
  28. Lanţ hamiltonian: un lanţ elementar care conţine toate nodurile unui graf.
  29. Ciclu hamiltonian: un ciclu elementar care conţine toate nodurile grafului.
  30. Graf hamiltonian: un graf, care conţine un ciclu hamiltonian.
  31. Lanţ eulerian: un lanţ simplu care conţine toate muchiile unui graf.
  32. Ciclu eulerian: un ciclu simplu care conţine toate muchiile grafului.
  33. Graf eulerian: un graf care conţine un ciclu eulerian.
  34. Graf ponderat: un graf în care fiecărei muchii/arc îi este asociată o valoare.

Reprezentarea grafurilor

Matricea de incidență

Pentru un graf cu n noduri și m muchii, matricea de incidență este o matrice de ordin n x m și elemente din {0, 1}, cu semnificația:

, unde
15432e1e2e3e4e5e6e7e8
1 2 3 4 5 6 7 8
1 1 0 0 0 0 1 0 1
2 1 1 0 1 0 0 1 0
3 0 1 1 0 0 0 0 0
4 0 0 1 1 1 1 0 0
5 0 0 0 0 1 0 1 1
152436e1e2e3e4e5e6e7e8e9e10e11
1 2 3 4 5 6 7 8 9 10 11
1 1 0 0 0 1 0 0 0 0 0 0
2 0 0 1 1 0 1 1 0 0 0 0
3 0 1 0 1 0 0 0 1 1 0 0
4 0 0 0 0 0 0 1 1 1 1 0
5 0 0 0 0 1 1 0 0 0 1 1
6 1 1 1 0 0 0 0 0 0 0 0

Observații

Într-un graf neorientat:

Într-un graf orientat:

Lista de muchii

Pentru un graf cu n noduri și m muchii, lista de muchii este o matrice de ordin m x 2 și elemente din mulțimea nodurilor. Fiecare linie din matrice conține extremitățile unei muchii.

1 1 2
2 2 3
3 3 4
4 2 4
5 4 5
6 1 4
7 2 5
8 1 5
1 1 6
2 3 6
3 6 2
4 2 3
5 1 5
6 2 5
7 4 2
8 3 4
9 4 3
10 5 4
11 5 5

Matricea de adiacență

Pentru un graf cu n noduri și m muchii, matricea de adiacență este o matrice pătratică de ordin n și elemente din {0, 1}, cu semnificația:

,
1 2 3 4 5
1 0 1 0 1 1
2 1 0 1 1 1
3 0 1 0 1 0
4 1 1 1 0 1
5 1 1 0 1 0
1 2 3 4 5 6
1 0 0 0 0 1 1
2 0 0 1 0 1 0
3 0 0 0 1 0 1
4 0 1 1 0 0 0
5 0 0 0 1 1 0
6 0 1 0 0 0 0

Observații

Într-un graf neorientat:

Într-un graf orientat:

Lista de adiacențe

Pentru un graf cu n noduri și m muchii, lista de adiacențe este o matrice de ordin n x m și pentru fiecare nod i, i fiind numărul de ordine a liniei din matrice, linia i conține vârfurile adiacente cu nodul i (lista vecinilor lui i).

1 2 4 5
2 1 3 4 5
3 2 4
4 1 2 3 5
5 1 2 4
1 5 6
2 3 5
3 4 6
4 2 3
5 4 5
6 2

În anumite cazuri este bine să memorăm pentru fiecare nod numărul de noduri adiacente cu el. În acest scop putem folosi coloana 0 din matrice pentru a reține aceste valori pentru fiecare nod (linie) în parte.

0 1 2 3
1 2 4 6
2 2 3 5
3 3 2 4 7
4 3 1 3 5

Transformări între diferite reprezentări

Matricea de adiacență → Matricea de incidență

Matricea de adiacență → Lista de muchii

Matricea de adiacență → Liste de adiacență

Lista de muchii → Liste de adiacență

Matricea de incidență → Lista de muchii

Liste de adiacență → Matricea de adiacență

Matricea de incidență → Liste de adiacență

Liste de adiacență → Lista de muchii

Liste de adiacență → Matricea de incidență

Parcurgerea grafurilor

Parcurgerea în lățime

drum: 1 4 6 3 5 7 2

  • Selectăm nodul de pornire și îl plasăm în vectorul coadă drum (și marcăm în vectorul freq).
  • Pentru fiecare element plasat în vectorul drum, căutăm vecini săi nevizitați încă (care nu au fost incluși în vectorul drum) și le introducem în coadă.

Structuri de date folosite

  • pentru stocarea grafului de exemplu, lista de adiacențe
  • variabila drum un vector de tip coadă
  • vectorul de frecvență freq care indică dacă un nod a fost vizitat sau nu
  • e - indică poziția elementului prelucrat în vectorul drum
  • u - indică poziția ultimului element din vectorul drum
1345762
0 1 2 3
1 2 4 6
2 2 3 5
3 3 2 4 7
4 3 1 3 5

Parcurgerea în adâncime

drum: 1 4 3 2 7 6 5

  • Selectăm nodul de pornire și îl plasăm în vectorul drum și în vârful stivei st (marcăm și în vectorul freq).
  • Pentru fiecare element aflat în vârful stivei st, căutăm primul său vecin nevizitat încă (și care nu au fost inclus în vectorul drum) și îl introducem în stivă (și în vectorul drum).

Structuri de date folosite

  • pentru stocarea grafului de exemplu, lista de adiacențe
  • variabila drum un vector
  • variabila st un vector de tip coadă
  • vectorul de frecvență freq care indică dacă un nod a fost vizitat sau nu
  • e – indică poziția elementului prelucrat din stivă
1345762
0 1 2 3
1 2 4 6
2 1 3
3 3 2 4 7
4 2 1 3
5 1 6
6 2 1 5
7 1 3

Drumuri în grafuri

Algoritmul lui Dijkstra

Pentru un graf orientat și ponderat cu n noduri și m muchii, să se determine costurile minime ale drumurilor care au acel nod ca extremitate inițială.

  • Selectăm nodul de pornire.
  • Vectorul ldrum se inițializează cu lungimile muchiilor incidente cu nodul de pornire, 0 pentru nodul de pornire și o valoare foarte mare pentru nodurile care nu sunt adiacente cu nodul de pornire.
  • Căutăm acea valoare minimă din vectorul ldrum pentru care prin nodul corespunzător încă nu am încercat să determinăm drum. Dacă prin acest nod se poate obține un drum mai scurt (cu un cost mai mic), actualizăm elementul corespunzător din vectorul ldrum.

Structuri de date folosite

  • matricea costurilor, utilizat pentru memorarea grafului
  • vectorul ldrum va conține lungimile drumurilor de la nodul de pornire la celelalte noduri
  • vectorul freq care indică dacă un nod s-a folosit pentru determinarea drumurilor minime
1345623 8 1 1 5 3 2 2
inițial:
ldrum: 8 0 ∞ ∞ 1 ∞
freq: 0 0 0 0 0 0
final:
ldrum: 6 0 3 3 1 9
freq: 1 1 1 1 1 1

Matricea drumurilor

Pentru un graf cu n noduri și m muchii, matricea drumurilor este o matrice pătratică de ordin n și elemente din {0, 1}, cu semnificația:

,
1 2 3 4 5 6 7
1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1
3 1 1 1 1 1 1 1
4 0 0 0 1 0 1 1
5 1 1 1 1 1 1 1
6 0 0 0 1 0 1 1
7 0 0 0 1 0 1 1
1436725

Algoritmul lui Roy-Floyd pornește de la matricea costurilor și printr-o deducție asemănătoare algoritmului lui Roy-Warshall, determină costul minim al drumurilor între oricare două noduri din graf.

Arborele parţial de cost minim

Pentru un graf neorientat, conex și ponderat cu n noduri și m muchii, se numește arbore parțial un graf parțial al grafului, care este arbore. Se numește arbore parțial de cost minim un arbore parțial pentru care suma costurilor muchiilor este minimă.

Pentru determinarea arborelui parțial de cost minim al unui graf neorientat, conex și ponderat se poate utiliza algoritmul lui Kruskal sau algoritmul lui Prim.

Algoritmul lui Kruskal

  • Se ordonează muchiile grafului crescător după cost.
  • Considerăm, că inițial fiecare nod face parte dintr-o componentă conexă de sine stătătoare.
  • Se analizează pe rând muchiile grafului, în ordinea crescătoare a costurilor. Dacă extremitățile muchiei leagă două noduri, care fac parte din componente conexe diferite, muchia respectivă face parte din arbore iar cele două componente conexe se unifică.

Structuri de date folosite

  • pentru stocarea grafului de exemplu, lista de muchii
  • vectorul comp cu n elemente și cu semnificația ca nodul i aparține componentei comp[i]
1345624 5 3 3 3 2 2 2 3 4 2
1 2 3
1 1 4 2
2 3 5 2
3 4 6 2
4 5 6 2
5 2 5 3
6 3 4 3
7 3 6 3
8 1 6 4
9 2 3 4
10 1 2 5

Algoritmul lui Prim

arborele parţial de cost minim: 3 5 6 4 1 2

  • Se stabilește nodul de plecare și se adaugă la arbore.
  • Se determină muchia cu ponderea minimă pentru care o extremitate este printre nodurile care au fost adăugate la arbore iar cealaltă extremitate nu aparține arborelui.
  • Muchia determinată și extremitatea care nu aparținea arborelui se adaugă la arbore.
  • Algoritmul se termină atunci când toate nodurile au fost adăugate la arbore.

Structuri de date folosite

  • pentru stocarea grafului de exemplu, lista de muchii
  • vectorul freq cu n elemente, freq[i]=1 înseamnă că nodul i aparține arborelui respectiv în caz contrar freq[i]=0
1345624 5 3 3 3 2 2 2 3 4 2
  • 1/10

    Dacă n este un număr natural impar mai mare decât 2, atunci un graf neorientat cu n noduri, în care fiecare nod este adiacent cu exact n-1 noduri, este întotdeauna:

    Verifică-ți cunoștințele!
    Start
  • 2/10

    Care din următoarele proprietăţi este adevărată pentru un graf orientat cu n vârfuri şi n arce (n>3) care are un circuit de lungime n:

  • 3/10

    Care dintre următoarele propoziţii NU este adevărată pentru graful orientat cu 6 vârfuri, numerotate de la 1 la 6 şi ale cărui arce sunt: (2,1), (3,6), (4,1), (4,3), (4,5), (5,2), (6,4)?

  • 4/10

    Se consideră un graf neorientat G cu 101 noduri şi 101 muchii. Numărul maxim de vârfuri izolate ale grafului poate fi:

  • 5/10

    Care dintre următoarele afirmaţii este adevărată pentru orice graf neorientat G cu 5 noduri şi 6 muchii?

  • 6/10

    Dacă G este un graf neorientat cu 8 noduri şi 2 componente conexe, atunci graful are cel mult:

  • 7/10

    Fie n un număr natural, n>4. Orice graf neorientat cu n noduri şi n muchii:

  • 8/10

    Care dintre următoarele afirmaţii este adevărată pentru graful neorientat având mulţimea nodurilor X={1,2,3,4,5} şi mulţimea muchiilor U={[1,2], [1,5], [2,3], [2,4], [3,4], [4,5]}?

  • 9/10

    Se consideră un graf neorientat 5 noduri şi 3 muchii. Care este numărul maxim de noduri cu grad 1 care pot exista în graf?

  • 10/10

    Care este numărul minim de muchii care trebuie eliminate dintr-un graf neorientat complet cu 100 de noduri astfel încât graful parţial obţinut să fie eulerian?

Arbori

  1. Arbori liberi

    2. Un graf neorientat, conex și aciclic se numește arbore (arbore liber).

    Un graf neorientat și aciclic se numește pădure.

  1. Arbori cu rădăcină

Dacă într-un arbore există un nod special numit rădăcină, iar celelalte noduri sunt ”agățate” de acest nod, graful se numește arbore cu rădăcină.

Caracteristici:

  • nivelul: este lungimea unui lanț de la rădăcina la un nod al arborelui (rădăcina se află la nivelul 0);
  • înălțime: este lungimea maximă a unui lanț de la rădăcină la un nod al arborelui → în exemplu este 4;
  • ascendent, descendent, frați: relația dintre două noduri în funcție de nivelul la care se află două noduri care se află la același nivel sunt frați, un nod aflat pe un nivel cu număr de ordine mai mic este ascendentul nodurilor la care este lanț din acel nod și se află pe nivele cu număr de ordine mai mare iar nodurile respective sunt descendenții nodului; dacă lungimea lanțului este 1, nodul respectiv este descendent direct → în exemplu ascendentul nodului 3 este nodul 1 iar nodul 1 este descendentul lui 3;
  • frunză: nodul care nu are niciun descendent → în exemplu nodurile: 4 5 8 9 11 12 13;
  • rădăcină: nodul care nu are niciun ascendent → în exemplu nodul 1;
  • subarbore: un nod al arborelui împreună cu toți descendenții săi formează un subarbore.
1 2 8 1 1 5 4 3 10 6 7 9 11 13 12 nivelul 0nivelul 1nivelul 2nivelul 3nivelul 4rădăcinăfrunză
figura a.
  1. Arbori binari

    2. Un arbore în care fiecare nod are cel mult doi descendenți se numește arbore binar.

    Descendenții se numesc descendentul stânga respectiv descendentul dreapta.

6 4 7 9 11 13 12 10 2 1 5 3 8
figura b.

Reprezentarea arborilor cu rădăcină

  1. Vector de tați

    2. Ascendentul direct al fiecărui nod este dat cu ajutorul unui tablou unidimensional. Indicele din vector reprezintă nodul, iar conținutul elementului indică nodul ascendent.

    exemplu: figura a.

    0 1 1 1 2 3 3 6 7 7 7 7 10 NOD TATĂ
    1 2 3 4 5 6 7 8 9 10 11 12 13 NOD
  2. Scrierea parantezată

    3. Pornind de la rădăcină, descendenții fiecărui nod se scriu între paranteze. În cazul nodurilor frunză, între paranteze se scrie caracterul *.

    exemplu: figura a. 1 ( 2( 5(*) ), 3( 6(8(*) ), 7(9(*), 10(13(*)), 11(*), 12(*))), 4(*) )

Reprezentarea arborilor binari

  1. Vector de tați

    2. Ascendentul direct al fiecărui nod este dat cu ajutorul unui tablou unidimensional.

    exemplu: figura b.

    0 1 1 2 2 3 3 4 6 6 10 10 7 NOD TATĂ
    1 2 3 4 5 6 7 8 9 10 11 12 13 NOD
  2. Scrierea parantezată

    3. Pornind de la rădăcină, descendenții fiecărui nod se scriu între paranteze. Dacă un nod are un singur descendent, în locul descendentului lipsă se scrie caracterul *.

    exemplu: figura b. 1 ( 2(4(8,*), 5), 3(6(9,10(11,12)), 7(*,13)) )

  3. Reprezentarea standard

    4. Se specifică nodul rădăcină, apoi pentru fiecare nod se memorează descendentul stânga și descendentul dreapta cu ajutorul a doi vectori sau folosind o matrice de 2 linii și n coloane (n fiind numărul de noduri). Nodul este indicat prin indicele din vector (indicele coloanei din matrice). Dacă nodul nu are descendenți se trece valoarea 0.

    exemplu: figura b.

    2 4 6 8 0 9 0 0 0 11 0 0 0 STÂNG
    3 5 7 0 0 10 13 0 0 12 0 0 0 DREPT
    1 2 3 4 5 6 7 8 9 10 11 12 13
  4. Forma binară

    5. Nodurile arborelui binar le specifică printr-un șir de cifre 0 și 1. Rădăcina se notează cu 1. Pentru un nod prezența cifrei 0 în șir semnifică apartenența la subarborele stâng respectiv cifra 1, apartenența la subarborele din dreapta.

    exemplu: (1,1) (2,10) (3,11) (4,100) (5,101) (6,110) (7,111) (8,1000) (9,1100) (10,1101) (11,11010) (12,11011) (13,1111)

6 4 7 9 11 13 12 10 2 1 5 3 8 1100101110001111111101110110011011101011011

Parcurgerea arborilor binari

  1. Traversarea în preordine (RSD): se vizitează rădăcina, se traversează subarborele stâng, se traversează subarborele drept

    2. exemplu: D A C K G P L B F O M I H

  2. Traversarea în inordine (SRD): se traversează subarborele stâng, se vizitează rădăcina, se traversează subarborele drept

    3. exemplu: C A G K P L D F O B I M H

  3. Traversarea în postordine (SDR): se traversează subarborele stâng, se traversează subarborele drept, se vizitează rădăcina

    4. exemplu: C G L P K A O F I H M B D

DAG BC MF P K HOIL

Arborele binar de căutare

Fiecare nod din oricare subarbore din stânga este mai mic decât rădăcina subarborelui respectiv.

Fiecare nod din oricare subarbore din dreapta este mai mare decât rădăcina subarborelui respectiv.

8 10 6 4 7 9 11 13 12 15 16 14 2 1 5 3
  • 1/10

    Se consideră vectorul de ”taţi” al unui arbore cu rădăcină T=(3,4,0,3,3,5) ale cărui noduri sunt numerotate de la 1 la 6. Alegeţi afirmatia corectă:

    Verifică-ți cunoștințele!
    Start
  • 2/10

    Se consideră un arbore G, cu rădăcină, memorat cu ajutorul vectorului de „taţi” următor: T=(2,0,4,2,4,7,2). Care dintre următoarele afirmaţii este adevărată?

  • 3/10

    Un arbore cu 11 noduri, numerotate de la 1 la 11, este memorat cu ajutorul vectorului de „taţi” T=(2,5,5,3,0,2,4,6,6,2,3). Mulţimea tuturor ascendenţilor nodului 8 este:

  • 4/10

    Un arbore cu rădăcină are nodurile numerotate de la 1 la 18 şi este reprezentat prin vectorul de „taţi” t=(8,8,0,3,4,3,4,7,1,2,3,3,7,8,3,5,6,8). Numărul tuturor descendenţilor nodului 3 este egal cu:

  • 5/10

    Dacă T este un arbore cu rădăcină, cu 100 de noduri, care este numărul minim de frunze pe care le poate avea T?

  • 6/10

    Se consideră un arbore cu rădăcină în care doar 13 dintre nodurile arborelui au exact 2 descendenţi direcţi (fii), restul nodurilor având cel mult un descendent direct (fiu). Care este numărul frunzelor arborelui?

  • 7/10

    Care este gradul maxim posibil si care este gradul minim posibil pentru un nod dintr-un graf cu n noduri, care este arbore?

  • 8/10

    Într-un arbore cu rădăcină nivelul unui nod este egal cu lungimea lanţului format din noduri distincte care uneşte rădăcina cu acel nod. Rădăcina se află pe nivelul 0. Dacă toate frunzele se află pe nivelul 3 şi oricare nod neterminal aflat pe un nivel k are exact k+1 descendenţi direcţi (fii), care este numărul de noduri din acest arbore?

  • 9/10

    Într-un arbore cu rădăcină, cu 10 noduri, numerotate de la 1 la 10, nodul 10 este rădăcină, iar între celelalte noduri există relaţia: nodul cu numărul i+1 este tatăl celui cu numărul i, pentru i∈{1,2,3,4,5,6,7,8,9}. Vectorul de „taţi” al arborelui astfel definit, este:

  • 10/10

    Un arbore cu rădăcină, cu 9 noduri, numerotate de la 1 la 9, este memorat cu ajutorul vectorului „de taţi” T=(9,3,4,7,3,9,0,7,2). Care este numărul minim de noduri ce trebuie eliminate pentru ca lungimea celui mai lung lanţ elementar, cu o extremitate în rădăcină, să fie 3 şi subgraful obţinut să fie tot arbore?