Lista de probleme 75
Filtrare
#19
Se consideră un graf neorientat cu n vârfuri și m muchii și un vârf cunoscut X. Să se afişeze vârfurile vizitate în urma parcurgerii în lățime a grafului pornind din vârful X.
Vasilut Lucian (Vasilut)
Lucian Vasilut
ușoară
Clasa 11
Teoria Grafurilor
Parcurgerea grafurilor neorientate
#539
Se consideră un graf neorientat cu n vârfuri și m muchii și un vârf cunoscut X. Să se afişeze vârfurile vizitate în urma parcurgerii în adâncime a grafului pornind din vârful X.
Candale Silviu (silviu) #4204
Popa Daniel (popadaniel72)
Daniel Popa
ușoară
Clasa 11
Teoria Grafurilor
Parcurgerea grafurilor neorientate
Grafuri
arbori
#437
Se dă lista muchiilor unui graf neorientat. Să se verifice dacă graful este sau nu conex.
#438
Se dă lista muchiilor unui graf neorientat. Să se afișeze componentele conexe ale acestui graf.
#4781
Se dă lista muchiilor unui graf neorientat. Să se afișeze componentele conexe ale acestui graf.
#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.
#4962
Se dă lista muchiilor unui graf neorientat. Să se determine muchiile care pot fi adăugate în graf astfel încât numărul de componente conexe ale grafului să nu se modifice.
#4963
Un teren de paintball este reprezentat prin n zone de luptă, numerotate de la 1 la n, interconectate prin tuneluri bidirecționale. Luptele pot avea loc doar în cele n zone; traversarea unui tunel, între două zone învecinate, durează un minut, iar traversarea unei zone se face instantaneu.
La joc participă trei jucători: doi jucători roșii, care se pot deplasa prin terenul de joc, folosind rețeaua de tuneluri, și un jucător albastru, Blue, care se află în zona de luptă b și nu o poate părăsi. Blue este mai puternic decât oricare dintre cei doi jucători roșii și orice luptă dintre Blue și un jucător roșu va fi câștigată de Blue. Jucătorii roșii pot câștiga numai dacă îl atacă pe Blue în același timp.
Jocul se desfășoară în felul următor:
- jucătorii roșii intră pe teren, în două zone diferite ale acestuia;
- fiecare se deplasează spre zona de luptă a lui Blue, pe cel mai rapid drum, parcurgând un tunel într-un minut;
- când un jucător roșu ajunge în zona lui Blue, are loc lupta.
Determinați în câte moduri pot fi alese zonele inițiale pentru jucătorii roșii, astfel încât să, mergând pe drumul cel mai scurt spre zona b a lui Blue, să ajungă în același timp și să îl învingă.
#537
Se dă lista muchiilor unui graf neorientat. Să se determine numărul de muchii care pot fi eliminate din graf astfel încât numărul de componente conexe ale grafului să nu se modifice.