h2. 'Ndap':problema/ndap

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'

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 <tex> NeConex[V'] = \sum_{V'' \subset V'} Conex[V'] * 2^{|E'-E''|} </tex>

h2. 'Alinuta':problema/alinuta