Contar grafos etiquetados

Grafos etiquetados

Sea $n$ el número de vértices de un grafo. Hay que calcular el número $G_n$ de grafos etiquetados con $n$ vértices (etiquetados significa que los vértices están marcados con los números de $1$ a $n$). Las aristas de los grafos se consideran no dirigidas, y se prohíben bucles y aristas múltiples.

Consideramos el conjunto de todas las aristas posibles del grafo. Para cada arista $(i, j)$ podemos asumir que $i < j$ (porque el grafo es no dirigido, y no hay bucles). Por lo tanto el conjunto de todas las aristas tiene cardinalidad $\binom{n}{2}$, es decir $\frac{n(n-1)}{2}$.

Como cualquier grafo etiquetado queda unívocamente determinado por sus aristas, el número de grafos etiquetados con $n$ vértices es igual a:

$$G_n = 2^{\frac{n(n-1)}{2}}$$

Grafos etiquetados conexos

Aquí, además imponemos la restricción de que el grafo tiene que ser conexo.

Denotemos el número pedido de grafos conexos con $n$ vértices como $C_n$.

Primero discutiremos cuántos grafos disconexos existen. Entonces el número de grafos conexos será $G_n$ menos el número de grafos disconexos. Más aún, contaremos el número de grafos disconexos enraizados. Un grafo enraizado es un grafo en el que enfatizamos un vértice etiquetándolo como raíz. Obviamente tenemos $n$ posibilidades de enraizar un grafo con $n$ vértices etiquetados, por lo tanto al final necesitaremos dividir el número de grafos disconexos enraizados por $n$ para obtener el número de grafos disconexos.

El vértice raíz aparecerá en una componente conexa de tamaño $1, \dots n-1$. Hay $k \binom{n}{k} C_k G_{n-k}$ grafos tales que el vértice raíz está en una componente conexa con $k$ vértices (hay $\binom{n}{k}$ formas de elegir $k$ vértices para la componente, estos se conectan de una de $C_k$ formas, el vértice raíz puede ser cualquiera de los $k$ vértices, y los $n-k$ vértices restantes se pueden conectar/desconectar de cualquier manera, lo que da un factor de $G_{n-k}$). Por lo tanto el número de grafos disconexos con $n$ vértices es:

$$\frac{1}{n} \sum_{k=1}^{n-1} k \binom{n}{k} C_k G_{n-k}$$

Y por último el número de grafos conexos es:

$$C_n = G_n - \frac{1}{n} \sum_{k=1}^{n-1} k \binom{n}{k} C_k G_{n-k}$$

Grafos etiquetados con $k$ componentes conexas {data-toc-label=“Grafos etiquetados con k componentes conexas”}

Basándonos en la fórmula de la sección anterior, aprenderemos a contar el número de grafos etiquetados con $n$ vértices y $k$ componentes conexas.

Este número se puede calcular usando programación dinámica. Calcularemos $D[i][j]$ — el número de grafos etiquetados con $i$ vértices y $j$ componentes — para cada $i \le n$ y $j \le k$.

Discutamos cómo calcular el siguiente elemento $D[n][k]$ si ya conocemos los valores anteriores. Usamos un enfoque común: tomamos el último vértice (índice $n$). Este vértice pertenece a alguna componente. Si el tamaño de esta componente es $s$, entonces hay $\binom{n-1}{s-1}$ formas de elegir tal conjunto de vértices, y $C_s$ formas de conectarlos. Después de quitar esta componente del grafo nos quedan $n-s$ vértices con $k-1$ componentes conexas. Por lo tanto obtenemos la siguiente relación de recurrencia:

$$D[n][k] = \sum_{s=1}^{n} \binom{n-1}{s-1} C_s D[n-s][k-1]$$