Category: Info

Arborii sunt un caz particular al grafurilor. Acestia sunt compusi dintr-o serie de noduri interconectate in care se gasesc informatii.

Definitie: Arborele este un graf neorientat conex fără cicluri în care unul din noduri este desemnat ca rădăcină. Nodurile pot fi aşezate pe niveluri începând cu rădăcina care este plasată pe nivelul 1.

Radacina unui arbore este un nod special care ajuta la delimitarea arborelui pe nivele. Acest nod se afla pe cel mai inalt nivel din arbore.

Astfel, arborele devine mai usor de parcurs, deoarece plasarea nodurilor pe nivele duce la o structurare mai eficienta a informatiilor. De asemenea, algoritmii ce folosesc arbori sunt foarte usor de implementat recursiv, caci la fiecare pas, putem separa arborele in mai multi arbori mai mici.

Exemplu de arbore:

Arborele de mai sus are ca radacina nodul F.

In arborele de mai sus, putem privi nodul B ca radacina, a unui nou arbore, mai mic (sub-arbore).

In continuare vom prezenta cateva notiuni utile in intelegerea arborilor. Vom folosi ca exemplu arborele de mai sus cu radacina F.

Arborele poate fi impartit in nivele astfel :

• F(nodul radacina) – Nivelul 1
• B si G – Nivelul 2
• A, D si I – Nivelul 3
• C, E si H – Nivelul 4

Un nod A este descendent al unui alt nod B, daca este situat pe un nivel mai mare decât B şi există un lanţ care le uneşte şi nu trece prin rădăcină.Mai multe despre lanturi gasiti aici.

Exemplu: In arborele de mai sus E este descendentul lui B, si al lui A.

Un nod A este fiu/descendent direct al unui alt nod B, daca este situat pe nivelul imediat urmator nodului B si exista muchie intre A si B.

Exemplu: In arborele de mai sus B si G sunt fii lui F(nodul radacina), A e fiul lui B, H e fiul lui I etc.

Un nod A este ascendent al unui alt nod B, daca este situat pe un nivel mai mic decat B si exista lant care le uneste si nu trece prin radacina.

Exemplu : In arborele de mai sus G este ascendentul lui H,B este ascendentul lui C.

Un nod A este parinte al unui alt nod B, daca este situat pe nivelui imediat superior nodului B si exista muchie intre A si B.

Exemplu: In arborele de mai sus F este parintele lui B,D este parintele lui E, I este parintele lui H etc.

Doua noduri sunt frati daca au acelasi parinte.

Exemplu : B si G sunt frati, A si D sunt frati.

Un nod este frunza daca nu are niciun fiu, adica se afla pe ultimul nivel.

Exemplu : In arborele nostru frunzele sunt C,E si H.

Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂

Citirea normala, cu ajutorul functiei cin, necesita ca datele de intrare sa fie introduse prin intermediul tastaturii, la rularea programului. Unele probleme, insa, doresc implementarea citirii cu ajutorul unui fisier extern. Pentru a realiza acest lucru trebuie folosita o variabila care va functiona similar cu functia cin, pe parcursul programului. Astfel, inainte de inceperea citirii trebuie deschis fisierul din care vrem sa citim si atribuit unei variabile de citire. Acest lucru se realizeaza cu structura ifstream.

Observatie!! Pentru a citi/afisa cu ajutorul fisierelor la inceputul programului trebuie inclusa biblioteca fstream. (#include <fstream>).

Structura operatiei de deschidere: ifstream numeVariabilaCitire(“numeFisier”);

Deschidere fisier de citire:

Dupa ce a fost deschis fisierul, putem folosi variabila prin care l-am deschis pentru a citi din acesta.

Structura operatie de citire : numeVariabilaCitire>> (similara functiei cin)

Exemplu de citire din fisier:

Afisarea intr-un fisier se face in mod asemanator functiei cout printr-o variabila de afisare. Inainte de efectuarea afisarii, trebuie mai intai deschis fisierul in care vrem sa afisam si atribuit unei variabile de afisare. Acest lucru se realizeaza cu structura ofstream.

Structura operatiei de afisare : ofstream numeVariabilaAfisare(“numeFisier”);

Deschidere fisier de afisare:

Dupa ce a fost deschis fisierul, putem folosi variabila prin care l-am deschis pentru a afisa in acesta.

Structura operatiei de afisare:  numeVariabilaAfisare<< (similara functiei cout)

Exemplu afisare in fisier:

Intr-un program se pot combina cele doua procese si putem citi dintr-un fisier si sa afisam in altul.

Exemplu de problema in care folosim citirea si afisarea din fisiere:

Sa se afiseze in fiserul ‘paritate.txt’, toate numerele pare din fisierul ‘input.txt’.Fisierul ‘input.txt’ contine numere intregi separate prin spatiu. Numerele trebuie afisate pe linii diferite.

Am deschis cele doua fisiere externe necesare(ifstream si ofstream). Dupa care, am citit din fisier (f>>a) numere, pana cand am ajuns la sfarsitul acestuia (while (f>>a) se opreste cand ajungem la sfarsitul fiserului retinut in f).Daca numarul citit este par il afisam in fisierul retinut in g (g<<a).

Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂

Sa se afiseze numarul de aparitii ale unui cuvant dat, intr-un sir citit de la tastatura. Am folosit functia strtok pentru a desparti textul in cuvinte si functia strcmp pentru a verifica daca 2 cuvinte sunt identice.

Exemplu:

Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂

Un graf orientat este o pereche ordonată de mulţimi G = ( V , E ).

Multimea V este o multime nevida si finita de elemente denumite varfurile grafului.

Multimea E este o multime de perechi formate cu ajutorul varfurilor din graf.

In cazul grafurilor orientate, perechile de varfuri din multimea E sunt ordonate si se numesc arce. Ele au o directie spre care merg. Arcul format de varfurile x si y se noteaza cu (x,y), varful x se numeste extremitate initiala a arcului (x,y), iar varful y se numeste extremitate finala a arcului (x,y).

Daca exista un arc determinat de varfurile x si y atunci, varfurile x si y se numesc adiacente. De asemenea, varfurile x si y sunt considerate incidente cu arcul pe care il formeaza. Fiecare extremitate a unui arc este considerata incidenta arcului respectiv.

1. Reprezentarea vizuala a grafurilor orientate:

1. Pentru a usura reprezentarea acestora, pentru fiecare varf al grafului se deseneaza un cerc si in interiorul cercului se trece numarul varfului.
2. Fiecare arc se reprezinta vizual ca o sageata care pleaca din extremitatea initiala si ajunge in extremitatea finala.

Exemplu:

2. Gradul unui varf

In cazul grafurilor orientate exista 2 tipuri de grade pe care un varf le poate avea: gradul exterior si gradul interior.

Gradul exterior al varfului x se noteaza cu d⁺(x) si este egal cu numarul de arce care au ca extremitate initiala pe x. In alte cuvinte, gradul exterior al varfului x reprezinta numarul de arce care pleaca din acel varf.

Gradul interior al varfului x se noteaza d^– si este egal cu numarul de arce care au ca extremitate finala pe x. In alte cuvinte, gradul interior al unui varf x este egal cu numarul de arce care ajung in acel varf.

Spre exemplu, pentru graful de mai sus avem:

Teorema:

Suma gradelor interioare ale varfurilor unui graf orientat este egala cu suma gradelor exterioare ale varfurilor grafului si este egala cu numarul de arce din graf.

 Σd⁺(x) = Σd^–(x) = m

3. Notiunile de drum si circuit

Se numeste drum intr-un graf orientat o secventa de varfuri (x₁,x₂,…,x_p), astfel incat pentru oricare doua varfuri consecutive x_i si x_i+1 exista arcul (x_i,x_x+1). De exemplu, pentru graful de mai sus, secventa de varfuri (1,2,5,1,3) este un drum de lungime 4.

Se numeste lungime a unui drum numarul de arce continute de acesta.

Un drum este elementar daca nu contine de mai multe ori acelasi varf. De exemplu, pentru graful de mai sus, secventa de varfuri (1,2,5,4) este un drum elementar de lungime 3.

Un drum este simplu daca nu contine de mai multe ori aceeasi muchie De exemplu, pentru graful de mai sus, secventa de varfuri (1,2) este un drum simplu de lungime 1.

Un circuit este un drum simplu pentru care extremitatea initiala coincide cu extremitatea finala. In alte cuvinte, drumul pleaca dintr-un varf si ajunge in acelasi varf. De exemplu, pentru graful de mai sus, secventa de varfuri (5,4,5,4,5) este un circuit, intrucat el pleaca din varful 1 si ajunge tot in varful 1.

Un circuit se numeste elementar daca nu contine de mai multe ori acelasi varf (exceptie facand extremitatile sale). De exemplu, pentru graful de mai sus, secventa de varfuri (1,2,5,1) este un circuit elementar.

Teoreme:

Un drum/circuit elementar se numeste hamiltonian daca el trece prin toate varfurile grafului.

Un drum/circuit elementar se numeste eulerian daca el trece prin fiecare arc al grafului o singura data.

4. Grafuri asociate unui graf dat

Fie G = (V,E) un graf orientat.

Graful G’ = (V,E’) se numeste graf partial al lui G daca E’ ⊂ E.

Un graf partial al lui G se obtine eliminand arce din graful G.

Graful partial de mai sus a fost obtinut prin eliminarea arcelor (1,2), (5,4) din graful initial de la inceputul postarii.

Un subgraf al lui G se obtine eliminand varfuri din graful G impreuna cu toate arcele incidente cu acestea.

Subgraful de mai sus a fost obtinut prin eliminare varfurilor 1,3 si 6 si a arcelor incidente cu acestea: (1,2), (1,3), (5,1) din graful initial.

Un subgraf partial al lui G se obtine eliminand varfuri din graful G, toate arcele incidente cu varfurile eliminate, precum si alte arce din graf.

Teoreme:

Fie G un graf orientat cu n varfuri si m muchii:

a) Numarul de grafuri partiale ale lui G este 2^m-1.

b) Numarul de subgrafuri ale lui G este 2ⁿ-1.

5. Tipuri speciale de grafuri orientate:

Un graf orientat se numeste complet daca oricare 2 varfuri ale acestuia sunt adiacente.

Graful orientat complet cu n varfuri se numeste K_n si contine [n(n-1)]/2 muchii.

Exemplu:

Grafurile de mai sus sunt grafuri orientate complete cu 4 varfuri.

In cazul grafurilor orientate, pentru un numar fixat de varfuri pot exista mai multe grafuri complete.

 Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂

Un graf neorientat este o pereche ordonată de mulţimi G = ( V , E ).

Multimea V este o multime nevida si finita de elemente denumite varfurile grafului.

Multimea E este o multime de perechi formate cu ajutorul varfurilor din graf.

In cazul grafurilor neorientate, perechile de varfuri din multimea E sunt neordonate si se numesc muchii. Ele nu au directie. Muchia formata de varfurile x si y se noteaza cu [x,y], varfurile x si y fiind denumite extremitatile muchiei.

Daca exista o muchie determinata de varfurile x si y atunci, varfurile x si y se numesc adiacente. De asemenea, varfurile x si y sunt considerate incidente cu muchia pe care o formeaza. Fiecare extremitate a unei muchii este considerata incidenta cu muchia respectiva.

Intre varfurile oricarui graf neorientat poate exista cel mult o muchie.

1. Reprezentarea vizuala a grafurilor neorientate:

1. Pentru a usura reprezentarea acestora, pentru fiecare varf al grafului se deseneaza un cerc si in interiorul cercului se trece numarul varfului.
2. Vom reprezenta fiecare muchie ca fiind o linie dreapta care pleaca de la un varf si ajunge la celalalt.

Exemplu:

2.Gradul unui varf

Se numeste grad al unui varf x numarul de muchii incidente cu varful respectiv. Graful unui varf x se noteaza cu d(x).

Astfel apar 2 notiuni noi:

Varful izolat = un varf care are gradul 0.

Varful terminal = un varf care are gradul 1.

Observam din tabelul de mai sus faptul ca varful 6 este un varf izolat si ca varfurile 3 si 4 sunt varfuri terminale.

Teorema: Suma gradelor unui varf neorientat este egala cu dublul numarului de muchii din graf.

Σd(x) = 2n

3. Notiunile de lant si ciclu

Intr-un graf neorientat, se numeste lant o secventa de varfuri cu proprietatea ca oricare doua varfuri consecutive din secventa sunt adiacente. De exemplu, pentru graful dat, [3,1,2,5,1,3,1] este un lant cu lungimea 6.

Lungimea unui lant = numarul de muchii pe care acesta le are in componenta.

Un lant este elementar atunci cand nu contine acelasi varf de mai multe ori. De exemplu, pentru graful dat, [1,2,5] este un lant elementar cu lungimea 2.

Un lant este simplu daca nu contine de mai multe ori aceeasi muchie. De exemplu, pentru graful dat, [3,1,2,5,4] este un lant simplu cu lungimea 4.

Se numeste ciclu, un lant simplu in care varful initial coincide cu varful final. In alte cuvinte lantul pleaca din varful x si ajunge tot in varful x. De exemplu, pentru graful dat, [1,2,5,1,2,5,1] este un ciclu.

Un ciclu este elementar daca nu contine de mai multe ori acelasi varf (cu exceptia extremitatilor). De exemplu, pentru graful dat [5,1,2,5], este un ciclu elementar.

Teoreme:

Un lant/ciclu elementar se numeste hamiltonian daca el trece prin toate varfurile grafului.

Un lant/ciclu elementar se numeste eulerian daca el trece prin fiecare muchie al grafului o singura data.

4. Grafuri asociate unui graf dat

Fie G = (V,E) un graf orientat.

Graful G’=(V,E’) se numeste un graf partial al lui G daca E’ ⊂ E.

Un graf partial al lui G se obtine eliminand muchii din graful G.

Graful partial de mai sus a fost obtinut prin eliminarea muchiilor [1,3], [1,5] din graful initial.

Un subgraf al lui G se obtine eliminand un varf si toate muchiile incidente cu acesta.

Subgraful de mai sus a fost obtinut prin eliminare din graful initial a varfului 5 si a tuturor muchiilor incidente cu acesta: [1,5], [2,5], [4,5].

Un subgraf partial al lui G se obtine eliminand varfuri din graful G, muchiile incidente cu varfurile eliminate, precum si alte muchii din graful G.

Subgraful partial de mai sus a fost obtinut prin eliminare din graful initial a varfului 5 si a muchiilor [1,3], [1,5], [2,5], [4,5].

Teoreme:

Fie G un graf neorientat cu n varfuri si m muchii:

a) Numarul de grafuri partiale ale lui G este 2^m-1.

b) Numarul de subgrafuri ale lui G este 2ⁿ-1.

5. Tipuri speciale de grafuri

Un graf neorientat se numeste complet daca oricare 2 varfuri ale acestuia sunt adiacente.

Graful neorientat complet cu n varfuri se numeste K_n si contine [n(n-1)]/2 muchii.

Exemplu:

Un graf neorientat G = (V,E) se numeste bipartit daca multimea varfurilor sale poate fi partitionata in doua submultimi A si B nevid ( A ∪ B = V ; A ∩ B = Ø) astfel incat orice muchie sa aia o extremitate in A si una in B.

In graful de mai sus, multimea A = {1,2,3} si multimea B = {4,5,6,7}.

Un graf neorientat se numeste regulat daca toate varfurile sale au acelasi grad.

 Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂

Se citesc de la tastatura un numar natural N si un vector de N elemente intregi. Dupa care, utilizatorul trebuie sa introduca valoarea pe care doreste sa o adauge in vector, cat si pozitia pe care vrea sa fie introdusa acea valoare. Se afiseaza vectorul rezultat in urma inserarii.

Inserare element pe o pozitie data:

Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂