Lista de probleme 46

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#1707 Retea

Se consideră o rețea formată din n servere, numerotate de la 1 la n. În rețea există m perechi de servere x y cunoscute între care există legături de comunicație directe. Între oricare două servere din rețea există legături, fie directe, fie prin intermediul altor servere.

Stabiliți pentru fiecare dintre cele n servere dacă eliminarea sa din rețea conduce la pierderea legăturii dintre cel puțin două servere rămase.

#1462 Gasti

Să se determine câte găști există în orașul Nicăieri și în câte moduri se poate forma o nouă relație de prietenie, astfel încât, să se obțină o nouă gașcă, cu număr maxim de membri.

Se dă lista muchiilor unui graf neorientat și două vârfuri p q . Să se determine cel mai scurt lanț cu extremitățile p q.

Se dă lista muchiilor unui graf neorientat cu n vârfuri și vârf p . Să se determine toate nodurile q ale grafului cu proprietatea că lungimea minimă a unui lanț de la q la p este L.

#541 Lant1

Se dă lista muchiilor unui graf neorientat și trei vârfuri p q r . Să se determine un lanț cu extremitățile p q care conține vârful r.

#126 DMax

Să se determine maximul distanţelor minime între nodul 1 şi celelalte noduri, într-un graf neorientat.

#1604 DMin

Se consideră un graf neorientat conex cu n vârfuri, numerotate de la 1 la n, şi m muchii. Definim distanţa minimă dintre două noduri x şi y ca fiind numărul minim de muchii al unui lanţ elementar care uneşte x cu y.

Se dau k perechi de vârfuri x y. Determinați pentru fiecare pereche distanța de la x la y.

Într-o țară locuiesc n persoane. Anumite perechi de persoane se cunosc între ele și se cunosc aceste perechi. Relația de cunoaștere între două persoane este reciprocă.

În țară izbucnește o epidemie (nu este mortală, doar foarte contagioasă). Dacă persoana A este bolnavă și cunoaște persoana B, se va îmbolnăvi și aceasta, după o perioadă de incubație a bolii de 1 zi. Inițial sunt bolnave k persoane cunoscute. Se cere să se determine după câte zile sunt bolnave toate cele n persoane.

#1841 fortuna

În orășelul Cota trăiesc N oameni între care se cunosc M relații de prietenie. Atunci când persoana K este afectată de boala Fortuna, maladia începe să se răspândească la toți prietenii săi și apoi mai departe, la prietenii prietenilor, până când toată populația va fi afectată. În ziua D după îmbolnăvirea cu boala Fortuna, un om va avea boala Fortuna de grad D. Știind aceste informații, Doctorul Bilet îi poate vindeca doar după ce toți oamenii vor fi afectați, iar fiecare va avea boala de cel puțin gradul P.
Sarcina ta este sa îi ajuți pe oamenii din orășelul Cota să afle după câte zile vor putea fi vindecați.

Concursul de Informatica "Spiru Haret" Targu Jiu, ed. I

Se dă un graf neorientat conex cu n vârfuri și număr par de muchii. Să se determine un graf parțial al celui dat care să fie conex și să fie obținut prin eliminarea a jumătate din numărul de muchii.