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

h2. 'Alinuta':problema/alinuta