Îmbunătățește-ți Cunoștințele de Informatică, Dezvoltă-ți Abilitățile de Programare și Design Web!
#441 Se dă lista muchiilor unui graf neorientat. Să se determine numărul minim de muchii care trebuie adăugate pentru ca graful să devină conex, precum și un set de asemenea muchii. Date de intrare Fişierul de intrare componenteconexe1.in conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține … Read more
#438 Se dă lista muchiilor unui graf neorientat. Să se afișeze componentele conexe ale acestui graf. Date de intrare Fişierul de intrare componenteconexe.in conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și … Read more
#437 Se dă lista muchiilor unui graf neorientat. Să se verifice dacă graful este sau nu conex. Date de intrare Fişierul de intrare conex.in conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i … Read more
#19 Se consideră un graf neorientat cu n vârfuri și m muchii și de asemenea un vârf X. Cerinţa Să se afișeze vârfurile vizitate în urma parcurgerii în lățime (Breadth First Search) a grafului, pornind din vârful X. Date de intrare Fişierul de intrare BFS.in conţine pe prima linie trei numere naturale n m X, … Read more
#539 Se consideră un graf neorientat cu n vârfuri și m muchii și de asemenea un vârf X. Cerinţa Să se afișeze vârfurile vizitate în urma parcurgerii în adâncime (Depth First Search) a grafului, pornind din vârful X. Date de intrare Fişierul de intrare dfs.in conţine pe prima linie trei numere naturale n, m, X, … Read more
on este un lingvist pasionat. Recent el a descoperit un text scris într-o limbă necunoscută. Textul este scris pe mai multe linii şi este format din cuvinte scrise cu litere mici din alfabetul latin, separate prin spaţii sau/şi semne de punctuaţie (,:;.!?-). Ion a fost frapat că există multe similitudini între cuvintele din text. Fiind … Read more
Se dă un graf orientat ponderat cu n noduri și m arce – în care fiecare arc are asociat un cost, număr natural strict pozitiv. Folosind algoritmul Roy-Floyd, construiți matricea costurilor minime, a[i][j] fiind costul minim al unui drum de la i la j, dacă există un asemenea drum, sau -1 în caz contrar. Date … Read more
Se dă un graf neorientat ponderat conex cu n vârfuri și m muchii – în care fiecare muchie are asociat un cost, număr natural strict pozitiv. Folosind algoritmul lui Kruskal, determinați un arbore parțial de cost minim. Date de intrare Fișierul de intrare kruskal.in conține pe prima linie numerele n m, iar următoarele linii câte … Read more
Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n, precum si o mulțime A de vârfuri ale grafului. Considerăm mulțimea B formată din vărfurile grafului care nu aparțin lui A. Să se verifice dacă graful este bipartit peste partiția formată din mulțimile A și B. Date de intrare … Read more
Definitie:Fie G =(V, M) un graf bipartit. Graful G se numeşte graf bipartit complet, dacă pentru orice x din V1 şi orice y din V2 exista in G muchia [x,y]. Exemplu de graf neorientat bipartit:G=(V, M) unde: V={ 1,2,3,4} si M={[1,3], [1,4], [2,3], [2,4]}Reprezentarea sa grafică este: Observatie 1:A demonstra că un graf este bipartit … Read more