conexidad

Conexidad

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

Fie un graf neorientat cu $N$ noduri şi $M$ muchii, care NU este conex.
Să $i$ se adauge grafului un număr minim de muchii, astfel încât acesta să devină conex.
Fie $extra{~i~}$ numărul de muchii nou-adăugate care sunt incidente cu nodul $i$, iar max_extra cea mai mare dintre valorile $extra{~1~}$ , $extra{~2~}$ ,... , $extra{~$~}$N$ . Mulţimea de muchii adăugate trebuie să respecte condiţia ca valoarea $max_extra$ să fie minimă.

Fie un graf neorientat cu $N$ noduri şi $M$ muchii, care **NU este conex**.
 
h2. Cerinţă
 
Să i se adauge grafului un număr minim de muchii, astfel încât acesta să devină conex.
Fie $extra{~i~}$ numărul de muchii nou-adăugate care sunt incidente cu nodul $i$, iar $max_extra$ cea mai mare dintre valorile $extra{~1~}$ , $extra{~2~}$ ,... , $extra{~N~}$ . Mulţimea de muchii adăugate trebuie să respecte condiţia ca valoarea $max_extra$ să fie minimă.

h2. Date de intrare

* $0 ≤ M ≤ N*(N-1)/2$
* Nodurile grafului sunt numerotate de la $1$ la $N$ inclusiv.
* Muchiile prezente în fişierul de intrare sunt distincte.

* Pentru orice muchie $[a,b]$ aflată în fişierul de intrare, avem $a &neq; b$.

* Pentru orice muchie $[a,b]$ aflată în fişierul de intrare, avem $a$ este diferit de $b$.

* Graful din fişierul de intrare nu este conex.
* În cazul în care soluţia afişată pentru un anumit test conectează graful cu număr minim de muchii, dar nu minimizează valoarea lui $max_extra$, se vor acorda $50%$ din punctajul pentru testul respectiv.
* Dacă există mai multe soluţii optime, se va admite oricare dintre acestea.

3 1
| Graful este format din două componente conexe, cu noduri din
mulţimea {1,2,4} respectiv nodul izolat 3.

După adăugarea muchiei (3,1) vom avea valorile $extra{~1~}$ =1,
$extra{~2~}$ = 0, $extra{~3~}$ =1, $extra{~4~}$ =0, deci max_extra=1.
Se poate demonstra că nu există soluţie cu max_extra<1.

După adăugarea muchiei (3,1) vom avea valorile $extra{~1~}$ = 1,
$extra{~2~}$ = 0, $extra{~3~}$ = 1, $extra{~4~}$ = 0, deci max_extra = 1.
Se poate demonstra că nu există soluţie cu max_extra < 1.

|
| 5 1
3 4

| Graful este format din patru componente conexe, cu noduri din
mulţimea {3,4}, respectiv nodurile izolate 1, 2 şi 5.
După adăugarea muchiilor (1,3), (2,3) şi (4,5), vom avea

valorile $extra{~1~}$ =1, $extra{~2~}$ =1, $extra{~3~}$ =2, $extra{~4~}$ =1,
$extra{~5~}$ =1, deci max_extra=2.
Se poate demonstra că nu există soluţie cu max_extra<2.

valorile $extra{~1~}$ = 1, $extra{~2~}$ = 1, $extra{~3~}$ = 2, $extra{~4~}$ = 1,
$extra{~5~}$ = 1, deci max_extra = 2.
Se poate demonstra că nu există soluţie cu max_extra < 2.

|
== include(page="template/taskfooter" task_id="conexidad") ==