Lista de probleme 9

Se dă un graf orientat cu n noduri. Să se determine câte componente tare conexe are graful dat.

Se dă un graf orientat cu n vârfuri și m arce prin lista arcelor. Se numește arc inutil un arc cu proprietatea că are extremitățile în componente tare conexe diferite. Afișați numărul de arce inutile și care sunt acestea.

Se dă un graf orientat cu n vârfuri și m arce prin lista arcelor și un număr natural k. Afișați numărul de vârfuri ale componentei tare conexe în care se află vârful k.

Se dă un graf orientat cu n vârfuri și m arce prin lista arcelor. Afișați componentele tare conexe formate din număr maxim de vârfuri.

Se dă un digraf (graf orientat) cu n noduri numerotate de la 1 la n. Graful componentelor tare conexe se obține astfel: se construiesc componentele tare conexe, apoi fiecare astfel de componentă devine nod în noul graf. Apoi din lista inițială de arce se păstrează în noul graf numai arcele care au extremitățile în componente tare conexe diferite. Să se afișeze listele de adiacență asociate noului digraf.

La cursul de comunicare organizat în vacanță, au participat N persoane, numerotate cu numere de ordine de la 1 la N. Fiecare persoană are la curs mai mulți prieteni apropiați, cărora le comunică orice informație imediat cum a aflat-o. Relaţiile de comunicare nu sunt bidirecţionale, cu alte cuvinte dacă persoana a îi transmite imediat informații persoanei b, nu este obligatoriu ca şi persoana b să transmită imediat informaţiile pe care le primeşte persoanei a.

Profesorul studiază relaţiile dintre participanţii la curs. El defineşte un nucleu de comunicare ca fiind un grup cu număr maxim de cursanţi cu proprietatea că oricare ar fi a şi b doi cursanţi din grup, dacă a primeşte o informaţie, aceasta va ajunge şi la cursantul b (direct sau prin intermediul altor cursanţi din grup).

Profesorul dorește să determine numărul de nuclee de comunicare existente la cursul său.

Cunoscând N, numărul de cursanţi, precum și prietenii fiecărui cursant, scrieţi un program care să determine numărul de nuclee de comunicare existente.

Pentru a testa o nouă topologie s-a construit o reţea de calculatoare în care fiecare calculator transmite informaţia unidirecţional către un singur calculator din reţea. Numim conexiune o pereche ordonată de calculatoare, nu neapărat distincte, în care primul este cel care trimite informaţia iar al doilea este cel care o recepţioneaza direct. Fiind dată o astfel de reţea şi conexiunile existente între calculatoarele care o alcătuiesc, să se determine submulţimea cu număr maxim de calculatoare-feed-back. Un calculator-feed-back are proprietatea că informația ce pleacă de la acesta ajunge, prin intermediul conexiunilor succesive, înapoi la calculatorul de la care a plecat.

Scrieţi un program care, pentru o reţea cu n calculatoare numerotate de la 1 la n şi conexiuni precizate, determină submulţimea cu număr maxim de calculatoare-feed-back.

Premierul Marii Britanii, Rishi Sunak, a decis să reorganizeze structura administrativă a comitatului Oxfordshire. În Oxfordshire sunt prezente N orașe numerotate de la 1 la N, conectate prin M autostrăzi (drumuri unidirecționale ce conectează două orașe). Rishi a hotărât ca toate orașele cu proprietatea că cetățenii tuturor celorlalte orașe pot ajunge în ele prin intermediul autostrăzilor să devină reședințe. Deoarece numărul de orașe și autostrăzi din Oxfordshire este foarte mare, Rishi vă cere ajutorul în rezolvarea a două probleme cheie.
1. Care sunt indicii orașelor reședință din Oxfordshire.
2. Care este distanța minimă de la fiecare oraș până la cea mai apropiată reședință de acel oraș.

Alex, un mare entuziast al turismului, a decis să-și transforme pasiunea într-o afacere și să organizeze tururi ale orașului Bistrița. Orașul poate fi reprezentat ca un graf orientat al obiectivelor turistice, conectate direct de străzi. Totuși, dat fiind că abilitatea de a se orienta a lui Alex nu este comparabilă cu entuziasmul lui, organizarea traseelor este dificilă pentru el. În primul rând, el vrea să numere câte astfel de trasee există în oraș. Un traseu reprezintă o listă ordonată \(a\) de \(k\) obiective turistice, cu următoarele proprietăți:

• De la nodul \( {a}_{i} \) se poate ajunge în nodul \( {a}_{i+1} \)
• De la nodul \( {a}_{k} \) se poate ajunge în nodul \( {a}_{1} \)

Spunem că se poate ajunge de la nodul x la nodul y dacă există un drum de 0 sau mai multe străzi care începe în nodul x și se termină în nodul y. Există 2 tipuri de trasee turistice:

• Tipul 1, în care obiectivele se pot repeta
• Tipul 2, în care obiectivele trebuie să fie distincte

Graful obiectivelor turistice este un graf orientat în care o muchie de la x la y reprezintă un drum direct de la nodul x la nodul y. Alex are nevoie de ajutorul vostru, pentru a determina câte trasee de lungime k există pentru un tip dat de trasee turistice (Tipul 1 sau Tipul 2), pentru fiecare k de la 1 la Q.