* 2 noduri unite printr-o conexiune (vom numi aceasta structura "retea de baza"); in figura, nodul stanga al acestei retele este marcat cu $T{~1~}$, iar nodul dreapta cu $T{~2~}$;

!problema/rsp?1.bmp!
 

* conectarea in serie a doua retele; considerand doua retele $R{~1~}$ si $R{~2~}$, acestea se conecteaza in serie suprapunand nodul dreapta al lui $R{~1~}$ peste nodul stanga al lui $R{~2~}$; nodul stanga al retelei rezultate este nodul stanga al lui $R{~1~}$, iar nodul dreapta al retelei rezultate este nodul dreapta al lui $R{~2~}$;

!problema/rsp?2.bmp!
 

* conectarea in paralel a doua retele; considerand doua retele $R{~1~}$ si $R{~2~}$, acestea se conecteaza in paralel suprapunand nodul stanga al lui R{~1~} peste nodul stanga al lui $R{~2~}$ si nodul dreapta al lui $R{~1~}$ peste nodul dreapta al lui $R{~2~}$; nodul stanga al retelei rezultate este dat de suprapunerea nodurilor stanga ale retelelor $R{~1~}$ si $R{~2~}$, iar nodul dreapta al retelei rezultate este dat de suprapunerea nodurilor dreapta ale retelelor $R{~1~}$ si $R{~2~}$; in urma conectarii in paralel pot rezulta conexiuni multiple intre nodul stanga si nodul dreapta al retelei rezultate (de exemplu, in cazul conectarii in paralel a doua "retele de baza").

!problema/rsp?3.bmp!
 

In vederea pregatirii integrarii in Uniunea Europeana, s-au primit fonduri pentru schimbarea retelei. Operatia de schimbare a retelei presupune, in prima etapa, eliminarea tuturor conexiunilor dintre nodurile retelei (urmand ca, ulterior, aceste conexiuni sa fie inlocuite cu unele mai performante). In urma calculelor efectuate, s-a ajuns la concluzia ca cea mai eficienta metoda de eliminare a conexiunilor din cadrul retelei este de a elimina unele noduri ale retelei impreuna cu toate conexiunile adiacente acestor noduri. Asadar, trebuie eliminata o submultime de noduri astfel incat orice conexiune a retelei sa aiba cel putin unul dintre capete in aceasta submultime. Evident, se doreste sa se elimine un numar minim de noduri.
Dandu-se o retea a carei structura respecta regulile precizate mai sus, determinati numarul minim de noduri ce trebuie eliminate pentru ca, odata cu ele, sa fie eliminate toate conexiunile existente in retea.