1.

2. 3.

4.

5.

6.

7.

8.

9.

10. 11. 12.

Scrieti un program care citeste informatii despre un graf neorientat (de pe prima linie, numarul de noduri, apoi matricea de adiacenta), si care verifica daca este un graf complet. Scrieti un program care citeste informatii despre doua grafuri orientate si care verifica daca cele doua grafuri sunt identice. Intr-un grup de n persoane s-a stabilit o relatie de cunostinta : persoana x este in relatie cu persoana y daca o cunoaste pe aceasta. Relatia de cunostinta nu este reciproca. Scrieti un program care sa citesaca dintr-un fisier matricea de adiacenta a grafului si care sa afiseze care sunt persoanele care se cunosc reciproc. Indicatie : perechile de noduri intre care exista arce duble. Intr-un grup de n persoane s-a stabilit o relatie de cunostinta : persoana x este in relatie cu persoana y daca o cunoaste pe aceasta. Relatia de cunostinta nu este reciproca. O celebritate este o persoana care este cunoscuta de toate persoanele din grup, dar care nu cunoaste nicio persoana. Scrieti un program care sa citeasca dintr-un fisire matricea de adiacenta a grafului si care afiseaza daca exista o celebritate, sa se precizeze persoana, iar daca nu exista, sa se precizeze : persoana care cunoaste cele mai putine persoane si persoana care este cunoscuta de cele mai multe persoane. Trebuie sa se construiasca o retea de autostrazi care sa lege cele mai importante orase din tara. Fiecare tronson de autostrada care leaga doua orase are un cost de construire. Sa se determine reteaua de autostrazi astfel incat toate orasele sa fie legate prin autostrazi si costul cosntruirii ei sa fie minim. Indicatie : algoritm de determinare a arborelui partial de cost minim ; alg. lui Prim sau Kruskal. Intr-un fisier text este scrisa o matrice, astfel : pe primul rand doua numere separate prin spatiu, care reprezinta numarul de linii si numarul de coloane ale matricei, si pe urmatoarele randuri valori numerice despartite prin spatiu, care reprezinta elementele de pe cate o linie a matricei. Scrieti un program care sa verifice daca aceasta matrice poate fi matricea de incidenta a unui graf orientat. In caz afirmativ, sa se determine cate noduri care au gradul intern egal cu gradul extern exista. Indicatie : se verifica urmatoarele conditii : pe fiecare coloana sa nu existe decat o valoare egala cu 1, una egala cu -1 si restul egale cu 0 ; sa nu existe doua coloane identice. Un nod are gradul interne gal cu gradul extern daca suma elementelor de pe linia sa este egala cu 0. Intr-un grup de n persoane s-au stabilit doua tipuri de relatii : de prietenie si de vecinatate. Scrieti un program care sa citeasca matricele de adiacenta ale celor doua grafuri dintr-un fisier text (pe primul rand, numarul de persoane, si pe urmatoarele randuri, in ordine, liniile fiecarei matrice de adiacenta) si care sa afiseze persoanele care sunt si prietene si vecini. Indicatie : se determina muchiile din graful intersectie a celor doua grafuri neorientate. O persoana trebuie sa se deplaseze cu autoturismul cat mai repede intre doua intersectii din oras. Traficul intre doua intersectii nu este intotdeauna in ambele sensuri. Cunoscand timpul mediu de deplasare intre doua intersectii, sa se determine care este traseul pe care trebuie sa-l aleaga pentru a ajunge de la intersectia A la intersectia B cat mai repede. Indicatie : Trebuie sa se determine un drum de cost minim dintre doua noduri ale grafului. Intr-un fisier text este scrisa o matrice, astfel : pe primul rand doua numere separate prin spatiu, care reprezinta numarul de linii si numarul de coloane ale matricei, si pe urmatoarele randuri valori numerice despartite prin spatiu, care reprezinta elementele de pe cate o linie a matricei. Scrieti un program care sa verifice daca aceasta matrice poate fi matricea de adiacenta a unui graf neorientat. In caz afirmativ, sa se afiseze cate noduri izolate are graful. Indicatie : se verifica urmatoarele conditii : sa fie o matrice binara ; suma elementelor de pe fiecare coloana sa fie 2 ; sa nu existe doua coloane identice. Un nod este izolat daca suma elementelor de pe linia sa este egala cu 0. Scrieti un program care citeste matricele de adiacenta a doua grafuri, G_a=(X,U_a) si G_b=(X,U_b), si care determina matricea de adiacenta a grafului reuniune G_r=(X,U_r) unde U_r este reuniunea dintre U_a si U_b. Scrieti un program care citeste matricele de adiacenta a doua grafuri, G_a=(X,U_a) si G_b=(X,U_b), si care determina matricea de adiacenta a grafului intersectie G_i=(X,U_i) unde U_i este intersectia dintre U_a si U_b. Sa se verfice daca un graf orientat este conex. Indicatie : are o singura componenta conexa.

13. Intr-un grup de n persoane s-au stabilit doua tipuri de relatii : de prietenie si de vecinatate. Scrietiun program care sa citeasca matricele de adiacenta ale celor doua grafuri dintr-un fisier text (pe primul rand, numarul de persoane, si pe urmatoarele randuri, in ordine, liniile fiecarei matrice de adiacenta) si care sa afiseze cel mai mare numar de persoane care se gasesc intr-un grup de vecini prieteni. Indicatie : se determina gradul maxim in graful intersectie a celor doua grafuri. 14. Intr-o localitate trebuie construita o retea de canalizare care sa lege n locuinte si sa comunice cu doua puncte de deversare. Fiecare tronson de retea are un cost de construire.Sa se determine reteaua de canalizare astfel incat toate locuintele sa aiba acces la ea si costul construirii ei sa fie minim. Indicatie : algoritm de determinare a arborelui partial de cost minim ; alg. lui Prim sau Kruskal. 15. Se citeste un graf neorientat. Sa se verifice daca graful dat este hamiltonian. Indicatie : se foloseste definitia notiunii de graf hamiltonian. 14. Se citete de la tastatur matricea de adiacen a unui graf orientat cu n noduri. Scriei un program corespunztor care s conin: - un subprogram care returneaz gradul interior al unui nod x dat ca parametru - un subprogram care afieaz mulimea +(x) - un subprogram care afieaz nodurile cu proprietatea c numrul arcelor care intr n nod este minim. 15. Un student vrea sa calatoreasca din localitatea X in localitatea Y. Daca in tara respectiva exista n localitati si stiind timpul necesar pentru a ajunge dintr-o localitate in alta (in cazul in care se poate ajunge direct) se cere sa se determine timpul minim in care elevul poate sa junga din X in Y. 16. Fiind date n orase si costurile tuturor drumurilor directe care exista intre orase, sa se afle costul minim pentru a ajunge dintr-un oras in oricare altul. 17. Fie G=(X,U) un graf conex. se numeste distanta dintre varfurile x si g nr-ul de muchii continute in cel mai scurt drum care uneste pe x cu g si se noteaza d(x,g). Pt un graf dat sa se det distanta intre 2 varfuri date. 18. Sa se verifice daca un graf dat prin matricea sa de adiacenta este sau nu graf bipartit. 19. Cunoscandu-se ca intr-un grup de n persoane codificate prin numere intre 1 si n, fiecare persoana are o lista (data) de alte persoane pe care le va informa deindata ce afla un anumit mesaj, sa se determine daca exista persoane care vor primi de cel putin doua ori acelasi mesaj. 20. Se citesc de la tastatura doua numere intregi, m si n, apoi m perechi de numere intregi reprezentand extremitatile muchiilor unui graf neorientat cu m muchii si n varfuri. Sa se construiasca matricea de adiacenta, apoi sa se scrie gradele varfurilor.

Sau orice alta problema. La examen veti aduce un referat care va fi format din rezolvarea unei probleme din lista de mai sus, sau orice alta problema de grafuri. Referatul va fi redactat la calculator, va contine textul si rezolvarea problemei, sa nu uitati numele vostru. !!!! Nu se accepta mai mult de 3 persoane cu aceeasi problema, rezolvarea fiind diferita.