Algoritmi elementari
1.ALGORITMUL DE INTERSCHIMBARE
Interschimba valorile a doua variabile de memorie. Exemplu: Presupunem ca avem 2 pahare: primul pahar (a) contine apa, al doilea pahar (b) contine lapte. Cum putem interschimba continuturile celor doua pahare? Raspuns: utilizand un alt pahar (aux). Se vor utiliza 3 variabile: a si b (variabilele care isi interschimba valorile) si o variabila aux. |
|
2.ALGORITMUL PENTRU DETERMINAREA MAXIMULUI
Sa se determine cea mai mare valoare dintr-un sir de n numere intregi citite de la tastatura.
Algoritmul: – se vor utiliza variabilele: n ( numarul de valori citite), i (contor), a ( valoarea citita), max (maximul) – se citeste primul numar si se considera ca fiind cel mai mare ( max = a) – se citesc pe rand valorile de la tastatura si se compara cu maximul curent. Daca valoarea citita este mai mare decat maximul atunci se atribuie variabilei max acea valoare. |
|
3.ALGORITMI PENTRU PRELUCRAREA CIFRELOR UNUI NUMAR
a) Extragerea cifrelor unui numar
Ex: Se citeste de la tastatura un numar intreg a. Sa se determine suma cifrelor numarului a.Algoritmul presupune extragerea pe rand a cifrelor numarului a incepand de la ultima cifra si adaugarea cifrei la suma prin operatia s <- s + a mod 10 unde a mod 10 este ultima cifra a numarului, apoi eliminarea cifrei prin operatia a <- a div 10. Algoritmul se incheie atunci cand s-au adunat toate cifrele numarului deci valoarea variabilei a este 0. |
|
b) Inversul unui numar
Pentru determinarea inversului (oglinditului) unui numar se vor utiliza variabilele: n ( numarul citit de la tastatura) si ogl (oglinditul). Initial valoarea variabilei ogl este 0.Oglinditul se va construi pas cu pas prin formula ogl = ogl *10 + n mod 10; |
|
4.Determinarea divizorilor unui numar
Pentru determinarea divizorilor unui numar se vor utiliza variabilele: a (numarul citit de la tastatura), i (contor). Se vor cauta posibilii divizori in intervalul [2, a/2]. Daca a mod i = 0 (a se divide la i) atunci se afiseaza divizorul (i). |
|
5.Determinarea unui numar prim
Un numar este prim daca se divide doar la 1 si la el insusi. Pentru verificarea unui numar prim se vor utiliza variabilele: a (numarul citit de la tastatura), i (contor) si sw. Vom considera ca numarul este prim deci variabila sw se va initializa cu valoarea 1. Se vor cauta posibilii divizori in intervalul [2, a/2]. Daca a mod i = 0 (a se divide la i) atunci rezulta ca numarul nu este prim deci schimbam valoarea variabilei sw=0. |
|
6.Determinarea celui mai mare divizor comun
Algoritmul determina cel mai mare divizor comun pentru doua numere intregi a si b citite de la tastatura. Se vor utiliza variabilele: a,b (numerele citite de la tastatura). |
|
Cel mai mic multiplu comun (cmmmc) C++
ENUNT: Se citesc de la tastatura doua numere a si b. Determinati si afisati cel mai mic multiplu comun al acestora. Codul de mai jos afla cel mai mare divizor comun (cmmdc) al celor doua numere pentru ca mai apoi sa-l foloseasca pentru a determina cel mai mic multiplu comun (cmmmc) folosind formula consacrata, cmmmc = (a*b) / cmmdc. |
|
Descompunerea in factori primi C++
ENUNT: Se citeste de la tastatura un numar n. Determinati si afisati pe ecran descompunerea in factori primi ai acestuia. |
|
Tablouri unidimensionale – Vectori
Vectorii sau tablourile unidimensionale sunt structuri de date bine definite si organizate in memorie. Cu ajutorul acestora, se pot pastra in memorie si accesa ulterior mai multe variabile, fara a fi nevoie de retinerea explicita a fiecareia dintre ele.
Vectorii se folosesc, cel mai adesea, cand numarul de variabile necesare intr-o problema variaza sau este de dimensiune mare. In acest caz, se doreste utilizarea un vector , in care punem cate variabile sunt necesare. In problemele noastre, ne vor interesa vectorii declarati prin numarul maxim posibil de elemente, cu memoria alocata local. Astfel, pentru declararea unui vector se foloseste urmatoarea structura: tip_vector nume_vector[dimensiune maxima vector]; Exemple uzuale : int v[100];
Pentru a atribui un element folosim : v[1] = 3; v[2] = 4, v[6] = 29, etc. Pentru citirea unui vector de n elemente, unde n este citit de la tastatura, se foloseste urmatoarea portiune de program : |
|
Se incepe citirea de la 1, primul element fiind salvat in v[1]. (La siruri de caractere, inceperea se face de la 0.) Elevul poate decide de pe ce pozitie sa inceapa : 1 sau 0.
Pentru a accesa elementul de pe pozitia K vom folosi v[K]. Afisarea se face in mod asemanator, citirii: |
|
Un vector v[6] are urmatoarea structura:
Astfel, cu ajutorul vectorilor, putem face modificari asupra unui sir de numere intregi, salvand fiecare modificare, pentru a afisa rezultatul obtinut. De asemenea, un caz foarte uzual, in care sunt folositi vectori, este atunci cand, se afiseaza elemente citite de la tastatura, intr-o ordine care nu coincide cu ordinea de citire.
Exemplu : afisarea in ordine inversa a unui sir citit de la tastatura( In acest caz, ultimul element afisat, este primul citit, deci, acesta trebuie retinut intr-o variabila. Vectorul ofera aceasta posibilitate, primul element fiind salvat pe prima pozitie din vector).
Problemele cu siruri, in care nu este posibila parcurgerea o singura data a sirului, se reduc si ele la lucrul cu vectori, sirurile fiind salvate in vectori. Memorarea sirurilor in tablouri unidimensionale face posibila parcurgerea sirurilor de mai multe ori.
Exemple de probleme in care s-ar putea folosi vectori :
Astfel, cu ajutorul vectorilor, putem face modificari asupra unui sir de numere intregi, salvand fiecare modificare, pentru a afisa rezultatul obtinut. De asemenea, un caz foarte uzual, in care sunt folositi vectori, este atunci cand, se afiseaza elemente citite de la tastatura, intr-o ordine care nu coincide cu ordinea de citire.
Exemplu : afisarea in ordine inversa a unui sir citit de la tastatura( In acest caz, ultimul element afisat, este primul citit, deci, acesta trebuie retinut intr-o variabila. Vectorul ofera aceasta posibilitate, primul element fiind salvat pe prima pozitie din vector).
Problemele cu siruri, in care nu este posibila parcurgerea o singura data a sirului, se reduc si ele la lucrul cu vectori, sirurile fiind salvate in vectori. Memorarea sirurilor in tablouri unidimensionale face posibila parcurgerea sirurilor de mai multe ori.
Exemple de probleme in care s-ar putea folosi vectori :
- Ordonarea unui sir citit de la tastatura in ordine crescatoare sau descrescatoare.
- Sa se afiseze maximul unui sir citit de la tastatura.
- Sa se afiseze elementele pare ale unui sir citit de la tastatura, dupa care elementele impare ale acestuia separate prin cate un spatiu.
- Sa se gaseasca cel mai mare divizor comun ( cel mai mic multiplu comun) a unui sir citit de la tastatura.
Sortarea unui vector prin interschimbare C++
In continuare, este prezentata sortarea prin interschimbare a unui vector cu N elemente citite de la tastatura. N-ul este, de asemenea, citit de la tastatura. Sortare crescatoare: Pentru a realiza sortarea descrescatoare trebuie doar sa inlocuim if-ul nostru cu if (v[i] < v[j]), singura schimbare necesara fiind schimbarea semnului de comparatie. |
|
Vectorul frecventa – afisarea elementului cu cel mai mare numar de aparitii C++
Se citeste un numar foarte mare de elemente cu doua cifre de la tastatura (retinerea lor intr-un vector devine imposibila din cauza spatiului ocupat). Se doreste afisarea elementului care apare de cele mai multe ori in sir. Stiind ca numerele citite sunt intre 10 si 99, putem folosi vectorul frecventa, pentru a retine numarul de aparitii al fiecarui numar – frecv[a] retine de cate ori apare numarul a in sir. |
|
Eliminarea unui element dintr-un vector C++
Se citesc de la tastatura un numar natural N, un vector de N elemente intregi si pozitia de pe care se doreste a fi sters elementul. Se afiseaza vectorul rezultat in urma eliminarii numarului de pe pozitia citita anterior. Eliminare element de pe o pozitie data: |
|
Tablouri bidimensionale – Matrici
O matrice este o forma de organziare a datelor de acelasi tip. O matrice reprezinta un tablou bidimensional in care sunt stocate date de acelasi tip. Elementele dintr-o matrice pot fi identificate dupa linia si coloana pe care se afla.
Se numeste matrice cu m linii si n coloane, un tablou cu m linii si n coloane.
Pentru m=4 si n=3 se obtine o matrice cu 4 linii si 3 coloane, spre exemplu:
In exemplul dat, numarul 35 se afla pe linia 1, coloana 1, pe cand 13 se afla pe linia 3, coloana 2. Am considerat numerotarea liniilor si coloanelor incepand de la 1. Daca matricea se va citi, luand doi contori ( i si j) cu valori de la 0 la m – 1 (pentru m linii), respectiv de la 0 la n – 1 (pentrul n coloane), atunci 35 se va afla pe linia 0 si coloana 0.
In limbajul C++ declararea unei matrici se realizeaza prin specificarea tipului elementelor din matricii, indentificatorul matricii, urmat apoi de dimensiunea acesteia (numarul de linii si de coloane) intre paranteze drepte.
Spre exemplu:
Se numeste matrice cu m linii si n coloane, un tablou cu m linii si n coloane.
Pentru m=4 si n=3 se obtine o matrice cu 4 linii si 3 coloane, spre exemplu:
In exemplul dat, numarul 35 se afla pe linia 1, coloana 1, pe cand 13 se afla pe linia 3, coloana 2. Am considerat numerotarea liniilor si coloanelor incepand de la 1. Daca matricea se va citi, luand doi contori ( i si j) cu valori de la 0 la m – 1 (pentru m linii), respectiv de la 0 la n – 1 (pentrul n coloane), atunci 35 se va afla pe linia 0 si coloana 0.
In limbajul C++ declararea unei matrici se realizeaza prin specificarea tipului elementelor din matricii, indentificatorul matricii, urmat apoi de dimensiunea acesteia (numarul de linii si de coloane) intre paranteze drepte.
Spre exemplu:
- int A[4][3]; (declara o matrice de 4 linii si 3 coloane continand numere intregi)
- float B[5][10]; (declara o matrice de 5 linii si 10 coloane continand numere reale)
- char C[20][12]; (declara o matrice de 20 de linii si 12 coloane continand caractere alfanumerice)
Observatie: Putem numerota liniile si coloanele de la 1, in acest caz, pentru a nu avea probleme de memorie, declaram matricea cu un numar in plus de linii si coloane. Astfel, daca vrem sa salvam o matrice cu 3 linii si 4 coloane, incepand numerotarea de la 1, vom scrie m[4][5] in loc de m[3][4].
Mai jos putem vedea citirea si afisare unei matrici salvata cu numerotoarea incepand de la 1. |
|
Suma elementelor unei matrice C++
Pentru a realiza produsul elementelor pur si simplu in codul de mai sus initializam s=1 (pentru a nu inmulti cu 0) si, la linia 15, inlocuim semnul “+” cu “*”, astfel variabila s va memora produsul elementelor matricei date. |
|
Eliminarea unei linii si (sau) coloane C++
|
|
Suma elementelor de pe diagonala prinicipala a unei matrice patratice C++
Pentru a realiza produsul elementelor pur si simplu in codul de mai sus initializam s=1 (pentru a nu inmulti cu 0) si, la linia 15, inlocuim semnul “+” cu “*”, astfel variabila s va memora produsul elementelor de pe diagonala principala a matricei date. |
|
Suma elementelor de pe diagonala secundara a unei matrice
patratice C++ Pentru a realiza produsul elementelor pur si simplu in codul de mai sus initializam s=1 (pentru a nu inmulti cu 0) si, la linia 14, inlocuim semnul “+” cu “*”, astfel variabila s va memora produsul elementelor matricei date. |
|
Grafuri neorientate C++
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.
1. Reprezentarea vizuala a grafurilor neorientate:
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.
1. Reprezentarea vizuala a grafurilor neorientate:
- Pentru a usura reprezentarea acestora, pentru fiecare varf al grafului se
- deseneaza un cerc si in interiorul cercului se trece numarul varfului.
- Vom reprezenta fiecare muchie ca fiind o linie dreapta care pleaca de la un varf si ajunge la celalalt.
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).
Teorema: Suma gradelor unui varf neorientat este egala cu dublul numarului de muchii din graf.
Σd(x) = 2n
Se numeste grad al unui varf x numarul de muchii incidente cu varful respectiv.
Graful unui varf x se noteaza cu d(x).
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.
Teoreme:
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.
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.
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.
din graful initial.
Un subgraf al lui G se obtine eliminand un varf si toate muchiile incidente
cu acesta.
Teoreme:Fie G un graf neorientat cu n varfuri si m muchii:
a) Numarul de grafuri partiale ale lui G este 2m-1.
b) Numarul de subgrafuri ale lui G este 2n-1.
a) Numarul de grafuri partiale ale lui G este 2m-1.
b) Numarul de subgrafuri ale lui G este 2n-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 Kn
si contine [n(n-1)]/2 muchii.
Exemplu:
Un graf neorientat se numeste complet daca oricare 2 varfuri ale acestuia sunt adiacente.
Graful neorientat complet cu n varfuri se numeste Kn
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.
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.
Un graf neorientat se numeste regulat daca toate varfurile sale au acelasi grad.
Teorie grafuri orientate C++
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:
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:
- Pentru a usura reprezentarea acestora, pentru fiecare varf al grafului se deseneaza un cerc si in interiorul cercului se trece numarul varfului.
- Fiecare arc se reprezinta vizual ca o sageata care pleaca din extremitatea initiala si ajunge in extremitatea finala.
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:
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 (x1,x2,…,xp), astfel incat pentru oricare doua varfuri consecutive xi si xi+1 exista arcul (xi,xx+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 acelasi varf. De exemplu, pentru graful de mai sus, secventa de varfuri (1,2) este un drum simplu de lungime 2.
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.
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 (x1,x2,…,xp), astfel incat pentru oricare doua varfuri consecutive xi si xi+1 exista arcul (xi,xx+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 acelasi varf. De exemplu, pentru graful de mai sus, secventa de varfuri (1,2) este un drum simplu de lungime 2.
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.
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.
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 2m-1.
b) Numarul de subgrafuri ale lui G este 2n-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 Kn 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.
Fie G un graf orientat cu n varfuri si m muchii:
a) Numarul de grafuri partiale ale lui G este 2m-1.
b) Numarul de subgrafuri ale lui G este 2n-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 Kn 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.
Arbori C++
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:
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 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 :
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.
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
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.