Șiret - IXIA

Șiret

== include(page="template/taskheader" task_id="siret") ==

== include(page="template/ixia") ==

== include(page="template/ixia-winner" round_id="7" user_id="spatarel") ==

Obişnuit cu probleme ştiinţifice şi concepte abstracte, Dani a ajuns la o vârstă care îi solicită subtil să înveţe şi alte lucruri de natură mai prozaică. De exemplu să-şi lege şireturile. În viziunea lui Dani, şireturile sale sunt amplasate pe două axe paralele, iar fiecare şiret este un simplu segment care are un capăt pe o axă, iar celălalt capăt pe axa opusă. Se poate presupune că pe ambele axe capetele sunt situate echidistant unele fata de altele. Având o astfel de configuraţie faţă, Dani desenează din reflex un graf după următoarele reguli:

Obişnuit cu probleme ştiinţifice şi concepte abstracte, Dani a ajuns la o vârstă care îi solicită subtil să înveţe şi alte lucruri de natură mai prozaică. De exemplu să-şi lege şireturile. În viziunea lui Dani, şireturile sale sunt amplasate pe două axe paralele, iar fiecare şiret este un simplu segment care are un capăt pe o axă, iar celălalt capăt pe axa opusă. Se poate presupune că pe ambele axe capetele sunt situate echidistant unele faţă de altele. Şireturile sunt numerotate de la $1$ la $N$ in ordinea capetelor superioare. Având o astfel de configuraţie în faţă, Dani desenează din reflex un graf după următoarele reguli:

* Graful are exact atâtea noduri câte şireturi există.

* Graful are $N$ noduri.

* Există muchie neorientată de la nodul $i$ la nodul $j$ dacă şiretul $i$ se intersectează cu şiretul $j$.
Numim acest tip de graf un graf şiret. Numim $clică$ a unui graf un subgraf al său care are muchie între oricare două noduri ale subgrafului.

h3. Explicaţie

...

Configuratia de sireturi pe baza careia s-a construit graful din exemplu este urmatoarea.
!problema/siret?imag3.png!

== include(page="template/taskfooter" task_id="siret") ==

8371