Deje $G = (V, E)$, ser un grafo conexo con $V$ vértices y $E$ bordes. Definimos $H(x)$ como el número de vértices inducida por subdiagramas con $x$ bordes.
Como, por definición, $\sum_{i=0}^{i=m} H(i) = 2^V$. Suponemos que considerar nula gráfico como también uno de los inducida por subdiagramas.
Por ejemplo, supongamos $G(V, E) = \{(1, 2), (2, 3), (1, 3)\}$ donde $V = \{1, 2, 3\}$, luego $H(0) = 4$, $H(1) = 3$, $H(2) = 0$, $H(3) = 1$.
Además, supongamos que escribimos el polinomio $P(x) = \sum_{i=0}^{i=m} H(i) * x^i$, entonces, ¿qué podemos decir acerca de la $P(x)$ en términos de$V$$E$? Esto es debido a que nos puede ayudar a resolver el algoritmo anterior de manera eficiente mediante la diferenciación de la polinomio $E$ veces, poniendo a $x = 0$, cada tiempo y obtener el coeficiente correspondiente.
Existe un algoritmo eficiente para la misma?
Gracias por su ayuda de antemano.
Actualización : Gracias a @Dap, mi problema está resuelto. Pero sentía curiosidad por saber si alguien puede ayudar con ideas para encontrar $\sum_{i=0}^{i=m} {i}^{k} H(i)$ fijos $k$ variable $k$, la solución será '#-$P-hard$' como @Dap se sugiere en uno de los comentarios. Por ejemplo, ¿cuáles podrían ser los posibles enfoques para decir $k = 2, 3, 4$. Me enteré de que para$k = 0$,$\sum_{i=0}^{i=m} {i}^{0} H(i) = 2^V$, y para$k = 1$,$\sum_{i=0}^{i=m} {i}^{1} H(i) = E * 2^V$.
Actualización 2: La modificación problema basado en la sumatoria $\sum_{i=0}^{i=m} {i}^{k} H(i)$ también se resuelve ahora, gracias a @Dap.
