--------------------------------------------------------------------------
Într-un magazin sunt 8 raioane, distribuite în trei zone importante, în fiecare zonă fiind un număr par, nenul, de raioane. În scopul fluidificării deplasării clienților se marchează unele culoare, astfel încât fiecare culoar să conecteze două raioane, iar deplasarea pe el să se facă într-un singur sens. Se realizează o hartă, sub forma unui graf orientat, în care vârfurile reprezintă raioanele din magazin, iar arcele reprezintă culoarele marcate. Indicați numărul maxim de culoare care se pot marca, astfel încât graful să aibă trei componente tare conexe, fiecare componentă fiind reprezentarea pe hartă a câte uneia dintre cele trei zone importante din magazin.
--------------------------------------------------------------------------
Explicații:
Numerele posibile de raioane din cele 3 zone pot fi:
- Zona 1: 2 raioane
- Zona 2: 2 raioane
- Zona 3: 4 raioane

O componentă tare conexă este un subgraf în care există un drum orientat între orice pereche de vârfuri. Fiecare zonă trebuie să fie un subgraf tare conex, iar între zonele diferite nu există drumuri directe, ceea ce înseamnă că arcele care leagă zonele diferite vor fi unidirecționale.

Într-o componentă tare conexă cu k vârfuri, numărul maxim de arce este k(k-1), deoarece fiecare vârf poate avea un arc către fiecare dintre celelalte k-1 vârfuri.

Pentru Zona 3: numărul maxim de arce într-o componentă tare conexă cu 4 vârfuri este 4(4-1) = 4*3 = 12 arce.

Pentru Zona 1 sau Zona 2: numărul maxim de arce într-o componentă tare conexă cu 2 vârfuri este 2(2-1) = 2*1 = 2 arce.

Din Zona 3 merg spre Zona 1 încă 8 arce, idem din Zona 3 spre Zona 2.

Din Zona 1 merg spre Zona 2 (final) încă 4 arce.

Nr. maxim de arce: 12+2+2+8+8+4 = 36

--------------------------------------------------------------------------
a) 20
b) 28
c) 36 (*)
d) 56
--------------------------------------------------------------------------
Răspuns corect: c)



