Testeaza-ti cunostintele la grafuri


  1. varianta
    1. Definiti: graf simetric, drum elementar, graf linie, multime interior stabile, fata a unui graf plan.
    2. Parcugerea grafurilor in adancime : exemplu, algoritm.
    3. Algoritmul lui belman kalaba exemplu si implementare.
    4. Speologii au cercetat n grote subterane pentru a stabili daca apartin aceleiasi pesteri. Prin tehnici specifice a fost demonstrate existenta unor canale de legatura intre mai multe grote. Precizandu-se perechile de grote intre care u fost stabilite legaturi sa se afle daca sistemul de grote apartine unei singure pesteri. Rezolvare problema speologii:
      problema speologi
  2. varianta
    1. Definiti: graf simplu, graf tare conex, graf aciclic, punct de articulatie, indice cromatic.
    2. Reprezentarea grafurilor sub forma de lista a succesorilor.
    3. Algoritmul lui Floyd-Warshall hu. Exemplu si implementare.
    4. O companie petroliera dispune intr-un oras de n benzinarii. Unele din aceste statii de benzina sunt legate intre ele prin drumuri directe (pe care se poate circula in ambele sensuri sau intr-un singur sens), iar altele nu. Pentru fiecare drum direct intre doua benzinarii se cunoaste lungimea acestui in kilometri. Domnul X se afla in masina la marginea orasului. Indicatorul de benzina se apropie de 0, ceea ce ii arata domnului X ca trebuie sa alimenteze urgent. Realizati un program prin care se indica drumul cel mai scurt de a ajunge la una din cele mai apropiate benzinarii, aflata pe un drum direct. Rezolvare problema benzinarii:
      problema benzinarii
  3. varianta
    1. Definiti: graf partial, graf hamiltonian, cocircuit, numar de stabilitate interna, istm.
    2. Reprezentarea grafurilor sub forma de matrice de incidenta.
    3. Algoritmul pentru determinarea componentelor conexe. Exemplu si implementare.
    4. La un turneu de tenis participă n jucători cu numerele de ordine de la 1 la n. Fiecare dintre ei joacă cu toți ceilați câte o partidă. Fiecare dintre partide este data că o pereche de jucători (i,j) cu semnificația că jucătorul i l-a învins pe jucătorul j. Afișați primii 3 jucători în ordine descrescătoare a numărului de victorii din turneu. Rezolvare problema tenis de masa:
      problema tenis de masa
  4. varianta
    1. Definiti: graf antisimetric, graf conex, graf planar, numar cromatic, multime de articulatie.
    2. Reprezentarea grafurilor ca si liste ale arcelor.
    3. Algoritmul lui Prim pentru determinarea arborelui partial de cost minim exemplu si implementare.
    4. Într-un grup de n persoane se precizează perechi de persoane care se consideră prietene. „Prietenul prietenului meu mi-e prieten”. Determinaţi toate grupurile cu un număr maxim de persoane între care există relaţii de prietenie. Citim de la tastatură matricea de adiacenţă. Rezolvare problema prietenul prietenului:
      problema prietenul prietenului
Puteti lasa si voi variantele voastre la aceasta materie, in comentariile acestei pagini.
Acest site utilizeaza cookie-uri. Navigand in continuare va exprimati acordul asupra folosirii cookie-urilor.