¿Cómo calcular el número de gráficos sin vértices de grado 0 utilizando el principio de inclusión-exclusión?

Question

Así que, hay esta tarea la pregunta donde tenemos que determinar el número de gráficos sin vértices de grado 0 mediante la inclusión-exclusión principio. Con $V = {1, 2, ... n}$ y la respuesta debe ser una función de n.

Sé que esto es la inclusión-exclusión en el principio de la regla y que el número total de gráficas posible es $2^{\binom{n}{2}}$. Así que sería de $|A_1| + |A_2| + ... + |A_n|$.

$$\left| \bigcup_{i = 1}^{n} A_i \right| = \sum_{k = 1}^{n} (-1)^{k - 1} \sum_{I \in \binom{\{1, 2, \ldots, n\}~}{k}} \left| \bigcap_{i \in I} A_i\right|$$

Pero yo no sé realmente lo $|A_1 \cap A_2|$ se supone que significa eso/en este ejemplo y ninguno de los otros. Alguien me puede ayudar con esto?

Answer 1

Usted puede pensar $|A_i|$ como el número de gráficos que el vértice $i$ con $1 \le i \le n$, $d(i)=0$. En este caso, si queremos dar un ejemplo, $|A_1 \cap A_2|$ es el número de gráficos que vértice $1$ $2$ tiene el grado de $0$. Lo que quiero hacer es encontrar el número de gráficos con al menos un vértice con grado cero y restar de la cantidad total de las gráficas, se puede tener, que es como se dijo, $2^{\binom{n}{2}}$. Aquí, puedo decir que para cada $i$, $|A_i| = 2^{\binom{n-1}{2}}$ porque nos están quitando todos los bordes conectados a $i$ con el fin de hacer $d(i) = 0$, y la construcción de un nuevo gráfico con el resto de los bordes y $n-1$ vértices. Del mismo modo, $|A_1 \cap A_2| = 2^{\binom{n-2}{2}}$ y así sucesivamente. Ahora, usted puede usar la Inclusión-Exclusión Principio para encontrar el número de la mala gráficos (los gráficos que tienen al menos un vértice con grado cero). Entonces, la respuesta debería ser $$2^{\binom{n}{2}} - |\bigcup \limits_{i=1}^{n}A_{i}| =\sum \limits_{k=0}^{n}{(-1)^k\binom{n}{k}2^{\binom{n-k}{2}}}$$

Tenga en cuenta que yo también se incluye el término $2^{\binom{n}{2}}$ a la suma.