Por qué hay $11$ gráficos no isomórficos de orden $4$ ?

Question

Soy nuevo en la teoría de grafos y tampoco pienso convertirme en un estudiante serio de teoría de grafos. Mi libro sugiere que hay $11$ gráficos no isomórficos de orden $4$ pero no veo por qué.

Sé que la aproximación más ingenua es que puedo usar la fuerza bruta y dibujar cuatro vértices y luego intentar conectar dos vértices por una arista de tal manera que no obtenga grafos isomórficos en cada paso. Pero entonces la pregunta es, ¿cómo puedo saber que he contado todas las posibilidades al final? Y cuando el tamaño del grafo es mayor, ¿cómo puedo saber que no estoy contando dos estructuras isomorfas más de una vez?

Para ser más preciso, tengo 5 preguntas sobre la determinación del número de grafos no isomórficos con $n$ vértices:

1. ¿Existe un enfoque algorítmico para crear todos los grafos no isomórficos de un determinado orden $n$ ?
2. ¿Tiene algo que ver con las secuencias gráficas y el algoritmo Havel-Hakimi o algo así?
3. ¿Es posible contar el número de grafos no isomórficos con $n$ vértices sin conocerlos realmente o sigue siendo un problema abierto?
4. ¿Es posible resolverlo parcialmente utilizando la teoría de grupos?
5. ¿Cómo puedo ver que hay $11$ gráficos no isomórficos con $4$ vértices sin fuerza bruta?

Answer 1

El problema del isomorfismo de grafos es "una curiosidad" según el artículo de Wikipedia porque es uno de los pocos problemas que son NP pero que no se sabe si están en P o si son NP-completos. Hay enfoques algorítmicos, pero no están estrechamente relacionados con la teoría de grupos, excepto en el sentido general de utilizar simetrías, y a menudo son muy abordables por métodos conocidos. El método de Brendon McKay NAUTY fue el primero en producir todos los 11 vértices ( $n=11$ ) hasta el isomorfismo, y puede comprobar el isomorfismo de la mayoría de los pares de grafos de hasta 100 vértices con bastante facilidad.

OEIS A000088 ofrece una tabla de resultados conocidos para $n=0,1,2,\ldots,19$ y algunas referencias útiles.

Una imagen de los once grafos simples posibles (hasta el isomorfismo) sobre cuatro vértices es fácilmente dibujado .

Para demostrar que son exhaustivos, podemos centrarnos en algunas propiedades del grafo que se conservan por isomorfismo (invariantes del grafo). Una de ellas es el número de componentes conectados. Como se muestra en los diagramas, tenemos que tener en cuenta un gráfico con cuatro componentes, uno con tres componentes, tres con dos componentes y seis que están conectados (un componente).

Otros invariantes fáciles del grafo son el número de aristas, los grados recogidos de los vértices (secuencias de grados) y el número de 3 y 4 ciclos (posiblemente cero).

Dado que los diagramas mostrados en el enlace anterior están ordenados por número de bordes que oscila entre $0$ (sin bordes) a $6$ (gráfico completo) $K_4$ ), tal vez sea la forma de empezar, primero para asegurarnos de que los once gráficos son realmente no isomorfos, y segundo para asegurarnos de que no hay ninguna posibilidad que se pase por alto.

Los extremos (ninguna arista, una arista, seis aristas) dan todos gráficos únicos, y un momento de reflexión te dirá que cinco aristas también dan un gráfico único (porque estás eligiendo cualquiera de las aristas del gráfico completo para eliminar, y todas esas opciones son equivalentes).

Hay dos casos con dos aristas, que debes convencerte de que se diferencian por si las aristas se conectan o no, y que agotan todas las posibilidades de dos aristas en cuatro vértices.

Los dos casos con cuatro aristas se distinguen de forma similar por si eliminamos dos aristas (del gráfico completo) que se conectan o no. Obsérvese que la eliminación de dos aristas que no conectar deja un cuatriciclo (cada vértice tiene grado dos), donde al quitar dos aristas que sí se conectan queda un vértice "terminal" de grado uno, por lo que son claramente no isomorfos (y agotan todas las posibilidades).

Los tres casos con tres aristas son los más interesantes, porque como clase están cerrados bajo complementación. Uno ( threeB ) es el grafo simple no trivial autodual más pequeño, un grafo isomorfo a su complemento. Los otros dos ( threeA y threeC ) son complementarios entre sí y claramente no son autoduales ( threeC está conectado y su complemento no; threeA contiene un ciclo y su complemento no).

Para ver que éstas agotan las posibilidades de tres aristas, observe que cualquier árbol (un grafo conectado sin ciclos) en cuatro vértices tendrá precisamente tres aristas. Si un grafo de cuatro vértices con tres aristas tiene un ciclo, debe ser un triángulo (3 ciclos), ya que no tenemos suficientes aristas para algo más grande. De lo contrario, tenemos un árbol, y el árbol debe consistir en un vértice de grado tres que se conecta a los otros tres vértices, o bien un camino de tres aristas que conecta todos los vértices.

Answer 2

Si sólo buscas un recuento, puedes calcularlo utilizando el Teorema de Enumeración de Polya. Lo que quieres aquí es el índice de ciclo del grupo de permutación de aristas $G$ del gráfico completo $K_4$ que es un tetraedro (esta observación ayuda a visualizar la estructura de ciclo de las permutaciones). Las permutaciones de $G$ se pueden enumerar de la siguiente manera.

Está la identidad, que contribuye $$a_1^6.$$ Podemos fijar un vértice y girar los otros tres, lo que da, cuando se aplica a las aristas, $$4\times 2\times a_3^2.$$ Podemos girar 180 grados alrededor de los puntos medios de dos aristas opuestas, fijando dichas aristas, para $$3\times a_1^2 a_2^2.$$ Podemos reflejar, mapeando los puntos medios de dos aristas opuestas entre sí, seguido de una rotación de 90 o 270 grados, dando $$3\times 2\times a_2 a_4.$$ Finalmente podemos hacer un único squish, intercambiando los vértices de una arista, lo que da $$6\times a_1^2 a_2^2.$$ Así se obtiene el índice de ciclo $$Z(G) = \frac{1}{24} \left(a_1^6 + 8 a_3^2 + 3 a_1^2 a_2^2 + 6 a_2 a_4 + 6 a_1^2 a_2^2\right)$$ que es $$Z(G) = \frac{1}{24} \left(a_1^6 + 8 a_3^2 + 9 a_1^2 a_2^2 + 6 a_2 a_4\right).$$ Se deduce que la función generadora ordinaria de los grafos no etiquetados en cuatro vértices por el número de aristas viene dada por $$Z(G)(1+z) = 1/24\, \left( 1+z \right) ^{6}+3/8\, \left( 1+{z}^{2} \right) ^{2} \left( 1+z \right) ^{2}+1/3\, \left( 1+{z}^{3} \right) ^{2}\\+1/4\, \left( 1+{z}^{2} \right) \left( 1+{z}^{4} \right)$$ que se amplía a $$Z(G)(1+z) = 1+z+2\,{z}^{2}+3\,{z}^{3}+2\,{z}^{4}+{z}^{5}+{z}^{6}.$$ De ello se desprende que hay $$\left.Z(G)(1+z)\right|_{z=1} = 11$$ grafos no isomórficos en cuatro vértices.

El siguiente enlace lo hace Enumeración de Polya para grafos de un número arbitrario de vértices. Aquí hay otro interesante Enumeración de Polya II .

Answer 3

Su tercera y cuarta pregunta están relacionadas. Puedes contar el número de grafos no isomórficos en $n$ vértices mirando las órbitas de etiquetado de las aristas de $K_n$ con dos colores, bajo la acción del grupo de automorfismo de las aristas de $K_n$ . Esto se puede hacer con la enumeración de Polya, que se basa en el lema de Burnside, y que probablemente ya conozcas de la teoría de grupos. Puede encontrar este útil, ya que demuestra este proceso para contar los gráficos en $4$ vértices.