Caso de S5 2-4 generado retorcido o twisted (2).

Esta es una entrada en construcción. Estará finalizada cuando desaparezca este mensaje. 

Ahora que tengo un poco de tiempo retomo el punto 2 de la entrada del mismo título para analizar paso a paso el caso que inicialmente motivó la entrada. Voy redactando a medida que vaya realizando avances.

Recordamos que el algoritmo tal y como está programado necesita 27 opciones. Buscamos un método más económico. Y que además ponga de manifiesto que la obstrucción está relacionada con la propiedad de retorcimiento o twistedness.

Se confirma que marcar inicialmente el IAS de la identidad y el opuesto es aparentemente una buen paso.  Hace días detecté la primera consecuencia de marcar estos dos IASes, que comentamos a continuación y hoy he detectado la segunda, que pasamos a redactar inmediatamente. Ninguna de las dos es evidente, sobre todo en un dígrafo dibujado de manera tan confusa. Menos lo ha sido la segunda.

Nota. Este caso pone de manifiesto (me refiero a la primera consecuencia) que uno de los pasos del algoritmo (marcar todos los IASes en cada iteración) para ver si se genera un ciclo o camino no hamiltoniano, es ¿ necesario ? para los casos difíciles. No es buena noticia, pues este paso es computacionalmente muy costoso. Fin de nota.

Pasamos a analizar el caso, con texto y gráficos:

Paso 1, opción 1 y 2. Marcamos el IAS de la identidad y su opuesto en la circunferencia por los generadores de orden 2. Esto son dos opciones. La idea es probar las cuatro combinaciones posibles de marcar estos dos IASes y ver si surge una contradicción rápidamente en las cuatro posibilidades, si es posible sin marcar más opciones o pocas más en cada una.

A continuación el estado del dígrafo al marcar el IAS identidad y su opuesto en la circunferencia por el ciclo de orden 2.

Estado al marcar ias identidad y su opuesto en circunferencia

Consecuencia 1. En la imagen se aprecia que el IAS amarillo (el que rodea el dígrafo) no puede ser marcado por el ciclo de orden 2, en cuyo caso se completaría un ciclo no hamiltoniano alrededor del IAS identidad. Hay que marcar este IAS por el generador de orden 4. En la imagen siguiente el estado del dígrafo tras realizar esto.

Consecuencia 1

Consecuencia 2. Se aprecia que entre la permutación 21534 y la permutación 24531 hay un camino ya marcado. Luego hay un arco de un IAS rojo de generador 4 sin marcar que une la permutación 24531 con la permutación 45321, luego hay varios arcos marcados entre 45321 y 32154 y luego hay un arco de un IAS azul claro que lleva de 32154 a 21534, que es la que iniciaba el camino que estamos describiendo.

Por lo tanto los dos arcos que hemos señalado no pueden marcarse a la vez pues se produciría un camino no hamiltoniano.  Y hay un IAS, de color violeta tal que si lo marcamos por el generador de orden 2 haría que se marcasen. Por lo tanto este IAS tiene que estar marcado por el generador de orden 4. En la imagen siguiente aparece el resultado de realizar esto.

paso 2 consecuencias

Llegados a este punto el digrafo está bastante saturado (en el sentido de que muchos IASes están ya activados en un sentido  u otro). En algún vistazo superficial no he encontrado de momento una consecuencia evidente, pero estoy convencido de que tiene que existir. Tras unas cuantas vueltas, no he encontrado ninguna consecuencia evidente (es decir que se pueda ver sin necesidad de utilizar más cálculos, o dicho de otra manera, lápiz y papel). Aunque mi búsqueda no a sido exhaustiva ya no estoy tan convencido que haya alguna consecuencia en este estado. No nos queda otra que elegir una opción

Opción 3.  Si marcamos un IAS negro por el generador de orden 2, que rodea la parte superior del dígrafo (el que conecta los IASes marcados con un cuadrado dentro del cual aparece una cruz y la palabra negro), entonces se acaban marcando todos los IASes y se genera un ciclo no hamiltoniano. Mostramos la situación en la imagen siguiente:

consecuencia 3

Por lo tanto este IAS  tiene que estar marcado por el generador de orden 4. Si también se llegase a contradicción, cosa que comprobaremos en breve, entonces habríamos llegado al final de esta primera posibilidad: tras tres opciones se concluye que no hay RH.

Obviamente esta es la posibilidad que necesita menos opciones, ya que al activar 2 IASes por el generador 2, se maximiza el número de IASes que se deben de activar como consecuencia (por cierto me pregunto si con la activación de cualquier par de IASes por el generador 2 también se llegaría al final con 3 opciones o el hecho de ser opuestos añade algo…). De cualquier manera, cuando lleguemos a la activación de los dos IASes por el generador 4, obtendremos el máximo de opciones. Iremos viendo…

Confirmado:  si se marca el IAS “negro” por el generador de orden 4, se desencadena un proceso en el que se acaban marcando todos los IASes y surge una contradicción. La imagen siguiente muestra la situación.

contradicción

Damos por terminado el análisis de esta primera (de cuatro) posibilidad.

Nota.

Posteriormente analizaremos si los obstáculos a la hamiltonicidad en este caso dependen de la propieda de retorcimiento. Veremos que así es. Y veremos que existe una definición de esta propiedad basada en los IAEses y en los ciclos (similar a la definición de cycle-entangled). Lo cual nos da a la vez una definición clara de la propiedad de smoothness o lisura.

Fin de nota.

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: