shgraf

Shgraf

== include(page="template/taskheader" task_id="shgraf") ==
Miruna a devenit de curând fascinată de grafuri. Mirunei i-au plăcut grafurile atât de tare, încât s-a decis să inventeze o nouă proprietate a lor. Astfel, ea consideră că un graf neorientat simplu are proprietatea de $„SHGRAF”$ dacă şi numai dacă se respectă una dintre următoarele două cerinţe:

Este un graf conex în care numărul de noduri este egal cu numărul de muchii.
Nu este un graf conex, dar fiecare componentă conexă a sa are proprietatea de „SHGRAF”.

 
* Este un graf conex în care numărul de noduri este egal cu numărul de muchii.
* Nu este un graf conex, dar fiecare componentă conexă a sa are proprietatea de $„SHGRAF”$.

Prietena cea mai bună a Mirunei, A. Irina, este o fire foarte curioasă. Ea s-a gândit la două numere naturale $N$ şi $K$, iar acum o întreabă pe Miruna câte grafuri etichetate cu $N$ noduri şi cu proprietatea de $„SHGRAF”$ există, astfel încât orice ciclu din graf are lungimea mai mare sau egală decât $K$.

table(example). |_. shgraf.in |_. shgraf.out |
| 3 3

| 1
|
 
Singurul graf care respectă condiţiile impuse este ciclul elementar format din 3 noduri.
 
table(example). |_. shgraf.in |_. shgraf.out |

| 1 |

| 50 10
| 20726
|

Numărul de grafuri este prea mare pentru mai multe explicaţii, va trebui să ne credeţi pe cuvânt ;)

h3. Explicaţie
 
# Singurul graf care respectă condiţiile impuse este ciclul elementar format din 3 noduri.
# Numărul de grafuri este prea mare pentru mai multe explicaţii, va trebui să ne credeţi pe cuvânt ;)

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

3790