¿Cuántas gráficas diferentes hay de la forma $G=(V,E)$ y $V=\{1,...,n \} $ .

Question

¿Cuántas gráficas diferentes hay de la forma $G=(V,E)$ y $V=\{1,...,n \} $ .

Esto es lo que pensé:

$E$ es un conjunto que contiene las líneas que son $2$ -conjuntos de elementos. Allí $\binom n 2$ diferentes formas de conseguir dicho conjunto, así que creo que esta debe ser la respuesta. Pero no estoy seguro.

Answer 1

SUGERENCIA: $^nC_2$ es el número de aristas posibles. Ahora considera la formación de gráficos a partir de estas aristas.

(Puede tomar o no alguna arista en particular).

Answer 2

Para dar una respuesta completa a esta pregunta: en cualquier gráfico con conjunto de vértices $\{1,2,\ldots,n\}$ Hay $\binom{n}{2}$ posibles bordes. Para construir un grafo, para cada una de estas posibles aristas, podemos elegir incluirla o no. Por lo tanto, hay $2^{\binom{n}{2}}$ gráficos distintos en el conjunto de vértices $\{1,2,\ldots,n\}$ .

Equivalentemente, es el número de conjuntos de aristas distintos, es decir, el número de subconjuntos de $$\big\{\{a,b\}:a,b \in \{1,2,\ldots,n\} \text{ and } a<b \big\}.$$

Tenga en cuenta que esto cuenta los gráficos etiquetados, por ejemplo, cuando $n=3$ tenemos los gráficos:

Vemos que varios de ellos son esencialmente iguales, es decir, son isomorfos. El número de grafos no isomórficos (estructuralmente no equivalentes) viene dado por la fórmula de Sloane A000088 .