Cómo probar un gráfico asimétrica?

Question

Un 3-regular gráfico que no tiene otra automorphism otros de la identidad.

He buscado y encontrado que esto significa que la gráfica es asimétrica y hay un ejemplo: el Frucht gráfico. Pero puede que alguien me muestre cómo demostrar esta propiedad? Si usted tiene un enlace por favor, acaba de publicar aquí. Gracias.

Answer 1

Dibujar el Frucht gráfico como

Deje $U$ el conjunto de vértices que están fijas en cada automorphism.

Sólo hay un 4-ciclo de $(9-10-11-12)$, por lo que cualquier automorphism mapas que a sí mismo. Sólo hay un 5-ciclo de $(8-9-12-11-10)$ que contiene los vértices en los que el 4-ciclo. Por lo $8 \in U$ (desde $8$ es el único miembro de la 5-ciclo que no está en el 4 ciclo).

$7 \in U$ (el único vértice que es un vecino de $8$ y no en el 4 ciclo).

$2 \in U$ (el único vértice en la distancia de 4 de $8$).

$3 \in U$ (el único vértice en la distancia de 3 de$7$, y también en la distancia de 3 de $8$).

$4 \in U$ (el único otro miembro de un triángulo que contiene $2$$3$).

$5 \in U$ (el único vértice adyacente a $4$$7$).

$6 \in U$ (el único otro miembro de un triángulo que contiene $5$$7$).

... etc.

Answer 2

Empezar con la idea de hacer una muy simétrica cúbicos gráfico que tiene un vértice $v$, que es tan especial que necesariamente debe ser un punto fijo de cualquier automorphism, a continuación, hacer cambios menores que no afectan la posición excepcional de $v$, pero que se rompen todas las simetrías.

Para un caso concreto, comencé con la propiedad especial: $v$ es el centro de la gráfica: es el único vértice al darse cuenta el radio de la gráfica. Ahora dibuje el siguiente gráfico: $v$ está en el centro, sus vecinos se $0,1,2$, con la etiqueta hacia la izquierda. Ahora crecen más 2 'generaciones': empate a dos vecinos de $0$, más hacia el exterior, con la etiqueta $00$ $01$ hacia la izquierda, lo mismo para $1$$2$, y para la tercera generación empate a dos vecinos de $00$, más hacia el exterior, con la etiqueta $000$ $001$ y lo mismo para las otras 5 segunda generación de vértices. Ahora que usted ha dibujado un buen simétrica de árbol donde cada nodo interno tiene un grado 3. Finalmente, conecte las hojas en sentido antihorario: $000$ con $001$, $001$ con $010$ etc. Ahora tenemos una muy simétrica cúbicos gráfico con 22 vértices $(1+3+6+12)$.

$v$ tiene una distancia de más de $3$ a cualquier otro vértice y es fácil ver que es el único vértice con esta propiedad. Ahora lo único que queda por hacer es hacer pequeñas modificaciones en las tres "ramas" (crías de 0, la descendencia de 1 y la descendencia de 2) que satisfacen las 4 condiciones

• Cubicidad se conserva
• La posición especial de $v$ se conserva
• Las ramas, para obtener diferentes modificaciones
• Todos simetría se ha ido

La segunda condición que garantiza que $v$ seguirá siendo un punto fijo para cualquier automorphism. La tercera condición garantiza que $0$, $1$ y $2$ también serán puntos fijos (bueno, no del todo, pero ya el segundo intento fue exitoso). La cuarta condición es que se cumple con el requisito para esta pregunta. Nota sin embargo que es ahora relativamente fáciles de controlar, ya que tenemos una base fija'.

Debido a que sólo creció tres generaciones, las modificaciones en las ramas puede ser menor, en este caso nos acaba de quitar dos aristas no adyacentes $pq$ $rs$ y reemplazarlos con $pr$ $qs$ de la siguiente manera:

• En el 0-rama removemos un borde exterior y una tercera generación de borde: se retire $\{000,001\}$ $\{01,010\}$ y reemplazarlos con $\{01,001\}$$\{000,010\}$.
• En el 1-rama podemos cambiar nada en absoluto.
• En el 2-rama nos quite los dos bordes exteriores que conectan los vértices con el mismo padre: nos quite $\{200,201\}$ $\{210,211\}$ y reemplazarlos por $\{200,210\}$$\{201,211\}$.

Tenga en cuenta que las ramas todavía tienen simetrías internas, pero ya que ellos también están atados el uno al otro todos los mundiales de simetrías son eliminados.

También tenga en cuenta que después de la modificación en el 0-rama de $v$ ya no es el centro único, pero lo es aún lo suficientemente especial como: $v$ es de 20 vértices a distancia en la mayoría de los 2, todos los demás vértices tiene menos de 16 vértices en la distancia de más de 2.

He utilizado nauty para una verificación independiente de que el gráfico final, de hecho, es asimétrica. Aquí está la muestra dreadnaut sesión que muestra que hay de hecho ninguno de los automorfismos.

> n=22 g
 0 : 1 2 3 ;
 1 : 4 5 ;
 2 : 7 15 ;
 3 : 8 9 ;
 4 : 10 11 ;
 5 : 11 13 ;
 6 : 14 15 16 ;
 7 : 16 17 ;
 8 : 18 19 ;
 9 : 20 21 ;
10 : 12 21 ;
11 : 12 ;
12 : 13 ;
13 : 14 ;
14 : 15 ;
15 : ;
16 : 17 ;
17 : 18 ;
18 : 20 ;
19 : 20 21 ;
20 : ;
21 : .
> x
level 1:  1 cell; 22 orbits; 0 fixed; index 1/22
22 orbits; grpsize=1; 0 gens; 23 nodes (21 bad leaves); maxlev=2
cpu time = 0.00 seconds
>

Imagen de la gráfica antes de la manipulación

Imagen de la gráfica después de la manipulación (por desgracia, la herramienta decidió espejo de la imagen, pero estoy seguro de que sus cerebros son capaces de hacer frente a una leve molestia)

(Gracias a MJD para enseñarme a hacer fotos)

La generalización de las grandes gráficos es sencillo. He escrito un programa de ordenador que genera estos gráficos para un número arbitrario de las generaciones (bueno, hasta que se agote la memoria, que será rápida teniendo en cuenta el crecimiento exponencial) y, a continuación, realiza las mismas modificaciones menores (levantado a la más alta de la generación). Los resultados han demostrado ser asimétrica por nauty. Los gráficos en formato DOT o dreadnaut formato de entrada están disponibles bajo petición.

También hay una simple verosimilitud del argumento que no puede ser una automorphism. $v$ como centro de la gráfica debe ser un punto fijo. La no modificada de la rama 1 no tiene 4 ciclos, pero rama 0 tiene un clúster de 3 de 4 ciclos, cuya distancia a 0 es fácilmente visible a ser más pequeño que su distancia a la 1 o las 2. La rama 2 se 2 de 4 ciclos y un análogo argumento se aplica. Esto asegura que, de hecho, 0,1 y 2 deben ser puntos fijos, como bien esto será suficiente para solucionar el resto de la gráfica.

Answer 3

Tienes razón en que este problema es difícil: en realidad, el problema de la prueba si un grafo tiene un trivial automorphism grupo pertenece a la clase NP-complejidad, y se desconoce si existe un algoritmo que puede comprobar esta propiedad en el polinomio de tiempo (es decir, el número de pasos que el algoritmo toma es una función polinómica del número de vértices del grafo).

Sin embargo, te puedo dar una prueba de que el Frucht gráfica tiene un trivial automorphism grupo. Esta es la prueba dada por Frucht a sí mismo en su papel de "Gráficos de grado tres con un resumen de grupo".

En primer lugar, la etiqueta de los vértices de la gráfica, como se muestra:

Observe que la gráfica de es $3$-regular: cada vértice tiene exactamente tres vecinos. Esto nos permite definir el tipo de $(\kappa,\lambda,\mu)$ de un vértice $V$ como sigue:

Escribe los tres vecinos de $V$ $V_1$, $V_2$ y $V_3$.

Recordemos que un ciclo de longitud $\nu$ se define como una secuencia finita de vértices $v_1,v_2,\dots,v_\nu$ de manera tal que no hay dos $v_i$ son los mismos, y hemos $v_i\sim v_{i+1}$ ($\sim$ significa 'conectado') para todos los $i=1,\dots,\nu-1$, e $v_\nu\sim v_1$; es decir, un bucle de $\nu$ diferentes vértices conectados por aristas. Por ejemplo, $A,B,F,E$ es un ciclo de longitud $4$.

Ahora nos vamos a $\kappa$ ser el más pequeño $\nu$ tal que existe un ciclo de longitud $\nu$ que contiene los bordes $VV_1$ $VV_2$ (En general, un ciclo no podría existir. En ese caso, establezca $\kappa=\infty$.). De manera similar $\lambda$ a ser el más pequeño $\nu$ tal que existe un ciclo de longitud $\nu$ que contiene los bordes $VV_1$$VV_3$, e $\mu$ a ser el más pequeño $\nu$ tal que existe un ciclo de longitud $\nu$ que contiene los bordes $VV_2$$VV_3$. El tipo de $V$ es entonces el triple $(\kappa,\lambda,\mu)$. Puesto que el orden en el que situamos a los vértices $V_1,V_2,V_3$ es completamente arbitraria, podemos suponer que la $\kappa\leq\lambda\leq\mu$.

Vamos a probar y encontrar el tipo de vértice $A$. $A$ tiene tres vecinos - $B$, $E$ y $M$. El ciclo más corto que contiene los bordes $AB$ $AE$ es el ciclo de $A,B,F,E$, que tiene una longitud de $4$. El ciclo más corto que contiene los bordes $AB$$AM$$A,B,C,D,M$, que tiene una longitud de $5$. El ciclo más corto que contiene los bordes $AE$$AM$$A,E,F,B,C,D,M$, que tiene una longitud de $7$. Por lo tanto, el tipo de $A$$(4,5,7)$.

Usted puede ir a través de la gráfica de computación de los tipos de vértices. Luego de obtener los tipos de la siguiente manera:

$$\begin{array}{lCr} A & \cdots & (4,5,7) \\ B & \cdots & (4,5,6) \\ C & \cdots & (5,5,6) \\ D & \cdots & (3,5,5) \\ E,F & \cdots & (3,4,5) \\ G,H & \cdots & (3,6,7) \\ J,K,L,M & \cdots & (3,5,6) \end{array}$$

Es muy fácil ver que, si $\tau$ es un automorphism de la gráfica, el tipo de $\tau(V)$ es el tipo de $V$ para cualquier vértice $V$. De ello se deduce que si existe el $\kappa\leq\lambda\leq\mu$ que no es exactamente un vértice con el tipo de $(\kappa,\lambda,\mu)$ luego de que el vértice es fijado por $\tau$. Por lo tanto, cualquier automorphism de la gráfica debe fijar los vértices $A,B,C,D$.

Ahora un automorphism $\tau$ debe fijar bien $E$ $F$ o el intercambio de ronda (puesto que son los únicos vértices de tipo $(3,4,5)$). Desde $A\sim E$$A\nsim F$, sabemos que $\tau(A)\sim\tau(E)$$\tau(A)\nsim\tau(F)$; es decir, $A\sim\tau(E)$ $A\nsim\tau(F)$ (desde $\tau$ corrige $A$). Eso significa que $\tau$ corrige $E$$F$.

Un argumento similar muestra que $\tau$ debe arreglar $G$$H$: se debe arreglar o cambiar, sino $G$ está conectado a $E$ (que sabemos que es fijo) y $H$ no lo está, así que tienen que ser fijo.

Ahora hemos solucionado $A,B,C,D,E,F,G,H$, sabemos que $J$ es fijo (ya que es el único común vecino de $C$$H$), y, por tanto, que el $K$ es fijo (ya que es el único común vecino de $J$$H$), y, por tanto, que el $L$ es fijo (ya que es el único común vecino de $K$ y $D$), y, por tanto, que el $M$ es fijo (ya que todos los otros vértices son fijos). Por lo $\tau$ debe ser la identidad. $\Box$

En general, si usted quiere mostrar que una gráfica no tiene simetrías, teniendo en cuenta los tipos de $(\kappa, \lambda, \mu)$ de vértices (o algún otro invariante) es el camino a seguir. Si sabes alemán (que yo no), entonces este papel por Frucht da una idea de cómo usted puede venir para arriba con una gráfica.

Answer 4

Las fotos de los puestos de Robert Israel y Donkey_2009 son elegidos muy instructiva. Aquí una forma que utiliza la imagen de Donkey_2009 para agregar el nodo más a la Frucht Gráfico. La eliminación de todos los puntos de la mentira en triángulos. Para el resto de los puntos de un único isomorfismo se pueden derivar. La extensión de este isomorfismo con los demás puntos es único también.

La imagen de Robert Israel puede ser usado también para encontrar una extensión:

Olvidar el verde de los nodos y bordes. Para el resto de los Nodos con el negro y el azul nodos, sólo existe un isomorfismo $\phi$ con $$\text{color}(\phi(\text{node}))=\text{color}(\text{node}) \tag{1}$$

Ahora añadimos los bordes rojos (tres o más, adyacente a esta red de puntos de borde). El gráfico sólo tiene un isomorfismo de tipo $(1)$.

Ahora para cada uno azul nodo añadimos el verde de los nodos de nuevo y una antisimétrica gráfica de nuevo

Answer 5

El camino del perezoso para hacer la asignación original en Sage.

sage: for G in graphs.nauty_geng("12 -d3 -D3"):
         if G.automorphism_group().order() == 1:
            G.show()