Lista de probleme 234

Atunci când nu se luptă cu Vilgax, Ben și Gwen se joacă pe calculator sau pe telefon. Unul dintre jocurile lor preferate se numește CTC și presupune numărararea vârfurilor din componentele tare conexe ale grafurilor orientate. Mai exact, Ben numără câte componente tare conexe au număr par de vărfuri, iar Gwen numără câte componente tare conexe au număr impar de vârfuri. Stabiliți care dintre cei doi veri câștigă jocul.

Eșuînd în a-și regăsi adevărata identitate, Brush se refugiază în magicul tărâm al arborilor. Arbotra o sună și îi dă următoarea problemă: se dă un arbore cu N noduri, o rădăcină fixată, și M întrebări de forma: câte perechi neordonate de noduri pot forma, luând noduri doar din subarborele nodului X (inclusiv pe X).

Î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.

Se dă lista muchiilor unui graf neorientat cu n vârfuri și două vârfuri p q. Să se determine toate lanțurile elementare cu extremitățile p și q.

Se dă lista muchiilor unui graf neorientat cu n vârfuri și un vârf q. Să se determine cel mai lung lanț elementar cu extremitatea finală în q.

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

Se dă un arbore cu n noduri, în care fiecare muchie are asociat un număr natural. Se cere răspunsul la Q întrebări de forma: dacă u şi v sunt două noduri din arbore, care este valoarea xor a tuturor numerelor asociate muchiilor situate pe lanţul ce uneşte u şi v?

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.

Într-un oraș sunt n case numerotate de la 1 la n. Între anumite case sunt străzi bidirecționale. În casa cu indicele g locuiește Ghiocel. El are k colege ale căror numere de casă îi sunt cunoscute și Ghiocel dorește să le ducă ghicei la inceputul lunii martie. Pentru că este leneș, Ghiocel se decide să ducă ghiocei colegei sau colegelor care stă (stau) la o casă până la care Ghiocel are de parcurs un număr minim de străzi. Ajutați-l pe Ghiocel să determine numerele acestor case.

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.