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 <tex> NeConex[V'] = \displaystyle\sum_{V'' \subset V'} Conex[V''] * 2^{|E'-E''|} </tex>. Rezultatul il vom gasi in $Conex[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$<sub>$1$</sub> ale lui $V'$ din care face parte $X$ $(V$<sub>$1$</sub> != $V'$). Consideram ca multimea $V$<sub>$1$</sub> reprezinta componenta conexa din care face parte nodul $X$. Numarul de subgrafuri ale lui $V'$ avand fixata multimea $V$<sub>$1$</sub> este egal cu produsul dintre numarul de subgrafuri conexe ale lui $V$<sub>$1$</sub> si numarul total de subgrafuri ale lui $V$<sub>$2$</sub> = $V'-V$<sub>$1$</sub>. Astfel, relatia de recurenta devine <tex> NeConex[V'] = \displaystyle\sum_{V'' \subset V'} Conex[V''] * 2^{|E2|} </tex>. Rezultatul il vom gasi in $Conex[V]$.

h2. 'Alinuta':problema/alinuta