Lista de probleme 234

Se consideră un graf cu N noduri numerotate de la 1 la N și M operații de trei tipuri:

• 1 x y – se adaugă în graf muchia (x, y). Dacă muchia există deja, operația nu se efectuează
• 2 x y – întrebare: nodurile x și y se află sau nu în aceeași componentă conexă?
• 3 – care este numărul maxim de noduri dintr-o componentă conexă?

Trebuie să răspundeți la toate întrebările de tip 2 și 3.

Se dă lista arcelor unui graf orientat. Construiți matricea drumurilor, folosind algoritmul lui Roy-Warshall.

Se dă lista muchiilor unui graf neorientat cu n vârfuri și trei vârfuri p q r. Să se determine toate lanțurile elementare cu extremitățile în p și q care conțin vârful r.

În judeţul lui Dorel sunt n localităţi legate între ele prin m drumuri. Dorel e interesat să afle în câte moduri se pot alege n-1 drumuri din cele m date, astfel încât folosind aceste drumuri să se poată ajunge de la orice localitate la oricare alta.

Considerăm un ansamblu format din n roți dințate, numerotate de la 1 la n. Fiecare roată se poate roti spre dreapta sau spre stânga. Dacă o roată se rotește spre dreapta, toate roțile pe care le angrenează se vor roti spre stânga, și invers.
Una dintre roți este conectată la un motor și se va roti spre dreapta, iar toate roțile din ansamblu se vor roti în mod corespunzător. Ansamblul este construit astfel încât toate roțile vor fi angrenate și fiecare roată va fi angrenată de o unică altă roată.

Dându-se numărul de roți n, numărul de ordine x al roții conectate la motor și perechile de roți conectate între ele, să se determine sensul de rotație al fiecărei roți.

Într-o clasă sunt n elevi, numerotați de la 1 la n, iar unii dintre ei pot cunoaște numerele de telefon ale altor elevi. Dirigintele dorește să-i anunțe pe elevi despre un eveniment deosebit și pentru aceasta vrea să transmită informația unui singur elev din clasă, urmând ca acesta să-și anunțe colegii cărora le cunoaște numărul de telefon, aceștia să-și anunțe colegii cărora le cunosc numărul de telefon etc, astfel încât toți elevii să afle informația respectivă.

Determinați care sunt elevii din clasă care pot fi anunțați inițial astfel încât, toți elevii să fie în cele din urmă informați.

Se dă lista muchiilor unui graf neorientat cu n vârfuri și trei vârfuri p q r. Să se determine toate lanțurile elementare cu extremitățile în p și q care nu conțin vârful r.

Se dă lista muchiilor unui graf neorientat cu n vârfuri și un vârf p. Să se determine un ciclu elementar care conține vârful p.

Se dă un arbore cu n noduri şi rădăcina r, nodurile fiind etichetate cu numerele de la 1 la n. Se cere să se afle pentru fiecare nod i, câte noduri din subarborele cu rădăcina i au eticheta mai mică decât i.

Pe teritoriul insulelelor FalkLand exista n britanici notati de la 1 la n si m argentinieni notati de la 1 la m.

Se știe că fiecare britanic poate lega o singura relație de prietenie cu una dintre cunoștințele sale Argentiniene și vice-versa. Pentru a detensiona relațiile, cele două naționalități sunt obligate să se cunoască și să lege cât mai multe relații de prietenie.

Având în vedere faptul că fiecare britanic poate lega o singură relație de prietenie cu un argentinian, iar relatiie de prietenie se știu deoarece acestea sunt evidente, Margaret Thatcher va solicită ajutorul în aflarea numărului maxim de relații noi de prietenie care se vor lega pe insula .