h2. 'Ndap':problema/ndap

Avand o submultime $V$ a nodurilor si submultimea $E$ de muchii determinata de $V$ (muchiile care au ambele capete in $V$), trebuie sa calculam $nrCon[V]$ = numarul de subgrafuri conexe ale submultimei de noduri $V$. Observam ca ar fi mai usor sa calculam $nrNecon[V]$ = numarul de subgrafuri sigur neconexe ale submultimei de noduri $V$. Este clar ca numarul de subgrafuri ale submultimei de noduri $V$ va fi intotdeauna egal cu $2^|E|^$ ( prin $|E|$ intelegem modulul multimii $E$ ), deci $nrCon[V]$ va fi egal cu $2^|E|^ - nrNecon[V]$.

Pentru fiecare submultime $V'$ a lui $V$, notam cu $E'$ multimea muchiilor care au ambele capete in $V'$, cu $NeConex[V']$ numarul subgrafurilor neconexe ale lui $V'$, iar cu $Conex[V']$ numarul subgrafurilor conexe ale lui $V'$. Se cunoaste faptul ca numarul total al subgrafurilor unui graf este egal cu $2^|E|^$, de aici rezultand egalitatea $Conex[V']$ = $2^|E'|^ - NeConex[V']$. Pentru fiecare sumbultime $V'$, vom incerca sa calculam NeConex[V']. Gasim un nod oarecare $X$ din $V'$. Pentru ca un subgraf al lui $V'$ sa fie neconex, componenta conexa din care face parte nodul $X$ trebuie sa fie diferita de $V'$. Vom genera toate submultimile $V"$ ale lui $V'$ din care face parte $X$ $(V" != V')$. Consideram ca multimea $V"$ reprezinta componenta conexa din care face parte nodul $X$. Numarul de subgrafuri ale lui $V'$ avand fixata multimea $V"$ este egal cu produsul dintre numarul de subgrafuri conexe ale lui $V"$ si numarul total de subgrafuri ale lui $V'-V"$. Astfel, relatia de recurenta devine NeConex[V'

...

h2. 'Alinuta':problema/alinuta