[Advertencia inicial:
a) Esta entrada es una republicación de una entrada de hace más o menos un año en la que publicamos la definición definitiva de la propiedad estructural de smoothness o lisura, que vamos a incluir en el informe de resultados del proyecto. Es la misma que la publicada en la patente (ésta accesible al público desde diciembre de 2009), aunque algo más general y más aterrizada y ya la definitiva.
La propiedad de lisura o smoothness es clave: una vez confirmado que un caso es smooth, cosa que se puede hacer como vamos a ver de manera eficiente con un input en representación normal, podemos conocer las propiedades de hamiltonicidad del caso: tendrá recorridos hamiltonianos en todos los vértices finales posibles y estos se pueden encontrar con relativa facilidad. Conociendo esta propiedad estructural y su relación con las propiedades de hamiltonicidad es fácil determinar las propiedades de hamiltonicidad de los casos Sigma Tau.
b) Presentación general de la investigación.
Propiedades estructurales y propiedades de hamiltonicidad.
Esta definición que presentamos en esta republicación es la que tiene que tener en cuenta cualquiera que quiera estudiar nuestros resultados que básicamente relacionan determinadas propiedades estructurales de los dígrafos de Cayley 2-generados con sus propiedades de hamiltonicidad.
Estas propiedades estructurales se pueden determinar de manera eficiente cuando el input es el dígrafo completo (se pueden considerar otros inputs, como los 2 generadores dados en forma de permutación).
—IAS regularidad. Hay una primera propiedad que divide en dos clases disjuntas a todos los dígrafos de Cayley 2-generados: la regularidad o no regularidad del IAS. No todos los dígrafos de Cayley 2-generados tienen el IAS regular. Hay dígrafos de Cayley 2-generados de grupos cíclicos (y solo estos) que pueden tener el IAS irregular. Esto es asó porque solo los grupos cíclicos pueden ser 1-generados. No hemos estudiado o muy poco, no de manera sistemática y hace tiempo los casos con el IAS irregular y por lo tanto se excluyen de nuestro proyecto de investigación.
De entre los dígrafos de Cayley 2-generados con el IAS regular, que son prácticamente todos menos algunos (realmente infinitos), las siguientes propiedades estructurales son relevantes para la hamiltonicidad:
—lisura o smoothness, que aquella sobre la que se habla en esta entrada,
–de retorcimiento o twistedness,
–de entrelazado o entanglement y sus grados (nada que ver con el entrelazado cuántico, que yo sepa). Entrelazamiento implica retorcimiento.
—entrelazado por ciclos o cycle-entanglement y sus grados. Entrelazado por ciclos implica entrelazado.
—IAS en ciclos totalidad que implica entrelazamiento por ciclos. Nos vamos a extender un poco con respecto a esta propiedad. No figura en las patentes (está dentro de los casos cycle-entangled) pero que es relevante y que caracteriza entre otros a todos los dígrafos de Cayley 2-generados abelianos (con el IAS regular) y merece la pena ser distinguida: es una propiedad que solo se puede dar entre los casos que son cycle-entangled y la propiedad es que cada IAS esté presente (tenga arcos, uno o más) en todos los ciclos de un solo generador del caso. Muchos de los resultados que existen sobre casos abelianos (Rankin (1948, Teorema 4) y Qi Fang Yang et all (1996) para 2-circulantes o Rankin 1948, Erdos-Trotter (1978) y Holtszynski-Strube (1978, sección 5), Curran y Witte (¿fecha?) para productos directos) y otros son sobre casos que tienen esta propiedad y en el fondo se basan en ella. Y es posible que haya otras publicaciones referidas a casos no abelianos que también se basen en esta propiedad. En efecto, se confirma que hay casos no conmutativos que tienen esta propiedad. Nos costó bastante encontrarlos y su búsqueda nos llevó a escribir varias entradas en el blog sobre dígrafos de Cayley de grupos construidos en base a diferentes productos o extensiones (semi-directos, wreath, split, Zappa-Szep etc…). En conclusión, hay dígrafos de Cayley 2-generados de grupos que se pueden obtener con otro tipo de productos que no sean productos directos (como, creo recordar, de productos semi-directos), que también tienen esta propiedad. Por otra parte, a diferencia de los casos abelianos con IAS regular, no todos los dígrafos de Cayley de estas construcciones tienen esta propiedad, y por lo tanto sería interesante hacer una investigación para determinar cuando se da esta propiedad en ellos (nosotros tuvimos que dejar a medias este muy interesante tema por falta de tiempo). Pensamos que, en los casos en los que la tengan esto se puede utilizar (y que de hecho se ha utilizado ya: nos referimos a algunos resultados publicados sobre digrafos de Cayley 2-generados de productos semi-directos) en estos casos, para obtener soluciones al problema de recorridos hamiltonianos. En fin, merece que se le ponga un nombre a esta propiedad, pero no se nos ocurre ninguno adecuado de momento…seguimos pensando en ello. ¿ IAS en ciclos totalidad ?. De momento vamos a trabajar con este nombre.
Notese que, aunque en la lista anterior hemos mencionado a cada una de las propiedades estructurales de forma categórica, en realidad varias de estas se dan en grados. Por ejemplo, un caso entrelazado puede estar más o menos entrelazado. Lo mismo sucede con otras como la propiedad de cycle-entanglement. Estos grados en los que se da una propiedad estructural se pueden expresar de manera cuantitativa.
En nuestra investigación dado un caso o input, nos interesa determinar si tendrá recorridos hamiltonianos (es decir caminos o ciclos) en todos sus vértices finales posibles. Utilizando las propiedades estructurales se pueden determinar las propiedades de hamiltonicidad de manera eficiente para todos los dígrafos de Cayley 2-generados.
Nuestra investigación sigue principalmente la linea de Rankin, Erdos y Trotter, Qi Fang Yang et all, Witte, Curran, Housman, Effler y Ruskey o Raamya, y otros que son los autores que han trabajado con el mismo problema definido sobre los mismos objetos matemáticos: recorridos hamiltonianos en dígrafos de Cayley bigenerados y aplicando técnicas similares. Otros autores han estudiado este problema en objetos similares como los dígrafos de Cayley n-generados o los grafos de Cayley, aplicando técnicas diferentes.
Nuestra investigación combina desarrollos experimentales (construyendo sobre la base de datos que aportaron Effler y Ruskey en su gran trabajo sobre el tema, nuestra propia base de datos, en parte más completa pues para muchos de los mismos casos, resolvía el problema de recorridos hamiltonianos en todos los vértices finales posibles; gracias a esto obtuvimos una óptica más general de este problema que nos permitió determinar que propiedades estructurales eran relevantes para el problema de recorridos hamiltonianos lo cual ha sido clave para toda la investigación), conceptuales (identificación y definición de las propiedades estructurales relevantes para el problema de hamiltonicidad), matemáticos (con demostraciones de los resultados principales) y algorítmicos.
Como resultado de todo esto este problema para los casos 2-generados cuando el input se da en representación normal, es decir cuando se da el dígrafo completo, se puede considerar cerrado, al menos desde el punto de vista de la complejidad computacional. Aunque ciertamente pensamos que los métodos algorítmicos disponibles ya eficientes, pueden ser mejorados. Y este tiene que ser el siguiente paso de la investigación cuando el input viene dado en representación normal. No damos más detalles al respecto.
Actualización 3 de diciembre 2019.
Notese que las diferentes propiedades estructurales son diferentes manifestaciones de un mismo fenómeno: que dos o más IASes estén presentes en dos o más ciclos de un solo generador y por eso se pueden dar en grados (podría haber casos en los que dos IASes están presentes en dos ciclos de un solo generador, casos en los que 3 IASes estén presentes en varios ciclos de un solo generador etc…En este sentido la propiedad de retorcimiento admite grados también (desde hace años hemos hablado en entradas de casos 1-twisted, que son aquellos en los que esta propiedad se manifiesta en mayor grado, 2-twisted etc…).
Los dos extremos del fenómeno general. Los casos smooth son un extremo de esto, en el que ningún par de IASes o más (tripletes…) están presentes en dos o más ciclos de un solo generador. Y los casos con la propiedad de IAS-ciclos totalidad es el otro extremo, el que cada IAS (todos los IASes) del caso, están presentes en todos los ciclos de un solo generador.
La conveniencia de tener en cuenta a las diferentes propiedades estructurales. Tiene sentido considerar a las diferentes propiedades estructurales (retorcimiento, entrelazado, entrelazado por ciclos, IAS-ciclos-totalidad) ya que en ellas el fenómeno general se manifiesta de diferentes maneras. Cada tipo de propiedad estructural hace que las obstrucciones y obstáculos a la hamiltonicidad se manifiesten de diferentes maneras. Por ejemplo en los casos twisted hay una cierta continuidad entre todos los vértices finales posibles con recorridos hamiltonianos, pero en los casos entrelazados puede haber agujeros (vértices finales posibles sin recorridos hamiltonianos situados entre dos vértices finales posibles que si los tienen). O por ejemplos en los casos cycle-entangled, y solo en estos, aplicando la técnica del plegamiento se puede obtener una generalización del teorema de Rankin). O por ejemplo en los casos con la propiedad IAS-ciclo-totalidad, se da un rasgo que han utilizado múltiples investigadores anteriores para obtener condiciones necesarias y suficientes de hamiltonicidad.
Condiciones necesarias y algorítmica. La existencia de determinadas propiedades estructurales es condición necesaria de que puedan existir obstrucciones u obstáculos, pero no suficiente. El algoritmo más general posible tiene en cuenta la existencia de estas propiedades estructurales que pueden ser causa de obstrucciones y obstáculos. La ruta de activaciones de IASes que sigue este algoritmo, que sigue la ruta de mínimas consecuencias, precisamente intenta minimizar los efectos de las propiedades estructurales, evitar los obstáculos e identificar las obstrucciones. Este algoritmo más general no es el óptimo.
Fin de actualización 3 de diciembre.
Input en forma sucinta.
Los dígrafos de Cayley 2-generados enseguida empiezan a ser de gran tamaño, empiezan a ocupar un gran espacio de la memoria y por ello es interesante seguir otra linea de investigación. En esta otra linea de investigación se da el objeto en forma de input sucinto, es decir en vez de que sea el dígrafo completo, que venga dado por ejemplo por los dos generadores dados en forma de permutaciones, siendo el tamaño del input entonces el grado de la permutación.
Muchas de las entradas del blog se refieren a esta segunda línea que sigue abierta. Como referencia señalamos que un problema de camino más corto (Minimal Length Generator Sequence) definido sobre exactamente este mismo objeto, los dígrafos de Cayley bigenerados dados en forma sucinta, es PSPACE-complete (creo recordar que está en NL cuando el input es en representación normal).
En esta segunda línea se intentan resolver los siguientes problemas:
—dados los generadores, determinar de manera eficiente los parámetros del caso. Un parámetro es un rasgo que tienen todos los casos y que se puede expresar de manera cuantitativa. Parámetros son el orden de los ciclos, el orden del IAS, el orden de la circunferencia. Escribimos de memoria: consideramos este tema como cerrado, existen procedimientos para obtener de manera eficiente todos estos parámetros en función del grado de la permutación.
—dados los parámetros (obtenidos antes, en el punto anterior) determinar de manera eficiente las propiedades estructurales. Sobre este tema hemos realizado grandes avances. Está conceptualmente aterrizado y falta desarrollarlo. Hemos publicado hace meses una entrada importante al respecto con todo detalle.
–dadas las propiedades estructurales (obtenidas antes, en el punto anterior), determinar de manera eficiente las propiedades de hamiltonicidad. Este tema no se puede atacar hasta que el anterior esté cerrado. Depende también de los métodos para resolverlo en el caso de input en representación normal. Si aplicamos estos mismo métodos está claro que en representación sucinta no son nada eficientes. Pero pensamos que esto es mejorable, sin saber cuanto. Por lo tanto este tema está bastante abierto. Es el que menos hemos investigado.
Actualización 1 de diciembre 2019.
Los casos abelianos en principio admiten una solución en representación sucinta tan eficiente como lo sea la solución de un problema de máximo común divisor, problema que como es sabido está en P y es uno de los candidatos a ser P-intermedio. Esto quizás se pueda tomar como una cota inferior de lo que se pueda esperar para este problema en versión sucinta para casos más complejos.
Fin de actualización.
Como se ve, esta segunda línea linea es más compleja que la anterior
Actualmente el titular de las dos patentes, que es el que escribe estas líneas se encuentra redactando un informe de resultados dónde se detallará todo esto.
A partir de aquí comienza la republicación].
Advertencia.
Lo que sigue está relacionado y protegido por las patentes que aparecen en la imagen anterior.
Fin de advertencia.
Esta entrada es continuación de la anterior.
Ya estamos redactando en el informe de resultados lo relativo a esta propiedad. En lo que sigue, en el punto 1, un extracto del informe con adaptaciones para la entrada del blog (posiblemente no será la versión definitiva pero nos vale para la entrada). En el punto 2 unos comentarios adicionales, que queremos incluir en el informe aunque todavía no tenemos la redacción definitiva. En el punto 3 explicamos dos de las vías que se pueden seguir para obtener métodos eficientes de solución del problema de recorridos hamiltonianos en este tipo de dígrafos cuando se tiene conocimiento de todo lo que explicamos en los dos puntos anteriores.
De nuevo queremos que quede claro que todo esto sobre los que hablamos en esta entrada se puede obtener de manera directa con el método descrito en las patentes. No hay nada nuevo pero si explicaciones más claras y los pasos del método más aterrizados. Precisamente la definición de entorno de la identidad basada en la circunferencia y de tablas de ciclos de este entorno que presentamos en el punto 1, la hemos obtenido intentando aterrizar lo máximo posible (para que lo entienda un lego en la materia) los métodos descritos en la patente. Y sobre el tema sobre el que tratamos en el punto 2 llevamos tratando desde las primeras entradas del blog. Y sólo se pueden llegar a él partiendo de los resultados de la patente.
En el informe cuando entramos a explicar nuestro resultado en detalle, primero hay una parte donde describimos los parametros (generador, ciclo de un generador y orden de un generador; IAS y orden del IAS; Circunferencia y orden de la circunferencia; vertices finales posibles). Un parametro es un rasgo cuantitativo que sirve para describir todos los casos. Todos los casos los tienen. A continuacion explicamos las propiedades estructurales, que a diferencia de un parametro, un caso puede tener o no. Esta es la parte que estamos terminando ahora y en una parte de la cual esta entrada esta basada. Y luego hay un punto en el que explicamos la relacion entre propiedades estructurales y hamiltonicidad. Este es el punto clave ya que en el explicamos los mecanismos de las obstrucciones (este punto sera una adaptac ion de varias entradas que hemos publicado en el blog hace anos; las repeticiones de IASes en ciclos del entorno sobre las que hablamos en esta entrada que se dan en los casos twisted, y acompanan a otras propiedades estructurales son uno de los componentes de los mecanismos). Tras este punto hay un punto en el que explicamos los metodos, que se basan en las propiedades estructurales y en los mecanismos.
1.Una definición más general de la propiedad de retorcimiento.
La definición de entorno de identidad y de la propiedad estructural que hemos dado en la patente y que hemos descrito en los puntos anteriores se basa en uno de los mecanismos que producen obstrucciones a la hamiltonicidad en los dígrafos de Cayley bigenerados (lo vamos a ver luego en detalle), captura los casos en los que estas obstrucciones son más acusadas (que en otras publicaciones o entradas del blog hemos llamado casos 1-retorcidos y 2-retorcidos) y utiliza el hecho de que los IASes del entorno de la identidad están conectados de una manera determinada que se puede identificar realizando un test.
En este punto vamos a dar una definición más aterrizada, basada en el mismo mecanismo, y que utiliza un concepto de entorno de la identidad más amplio basado en el parámetro de la circunferencia que hemos definido en puntos anteriores (y en múltiples entradas del blog ya desde 2010). Esta definición aunque algo más intensiva en uso de recursos computacionales es de alcance más general que la anterior (cubre todos los casos twisted, además de los 1-twisted y de los 2-twisted), ilustra mejor como se debe de realizar el test que distingue un caso smooth de otro twisted y hace que el mecanismo que explica las obstrucciones a la hamiltonicidad sea más explícito.
Al igual que en la definición que trabaja con el entorno de la identidad, con esta definición alternativa, para determinar si un caso es twisted o smooth hay que realizar un test. Para realizar este test hay que elaborar primero unas tablas. En lo que sigue explicamos como se deben de elaborar las tablas que se utilizarán para realizar el test que nos indica si el caso es twisted o smooth.
Instrucciones para elaborar las tablas de los ciclos del entorno de la identidad basado en la circunferencia.
Paso 1. Construcción de la circunferencia. Se construye la circunferencia del caso (esto es equivalente a construir el IAS, el DAS y los dos IASes que salen de ambos y que pertenecen a la circunferencia, según la definición anterior).
Paso 2. Ciclos de la circunferencia. Su numeración. Se construyen todos los ciclos que están en contacto con la circunferencia (equivalente a construir todos los ciclos del IAS y DAS en el entorno de la identidad) y se asigna a cada uno de ellos un número natural diferente, es decir se numeran (esto es equivalente a la numeración de ciclos descrita en el punto anterior).
Paso 3. IASes en contacto con los ciclos de la circunferencia. Su numeración. Se construyen todos los IASes que están en contacto con los ciclos construidos en el paso 2. Se asigna a cada uno de los IASes obtenidos en los pasos anteriores (a los obtenidos al construir la circunferencia según el paso 1 y a los obtenidos en el paso 3) un número natural.
Paso 5. Tablas de ciclos de las circunferencia. Se construye una tabla que contenga todos los ciclos de un generador y otra tabla que contenga todos los ciclos del otro generador. Como se haga esto no cambiará el resultado final del test: el caso será retorcido o liso independientemente de cómo se elabore la tabla. No obstante es conveniente realizar esta tabla de manera ordenada. Sugerimos el siguiente orden: en la primera columna se pondrá el número del ciclo correspondiente según la numeración realizada en el paso 2. Podemos comenzar con el ciclo del generador cuya tabla estemos elaborando que salga de la identidad y luego ir anotando el número de los consecutivos ciclos por un lado de la circunferencia y luego hacer lo mismo por el otro lado de la circunferencia. En las casillas de cada fila se irán anotando en las casillas de la tabla el número asignado a los IASes en el paso 4. Al final de este paso se obtienen dos tablas, cada una con tantas filas como ciclos estén en contacto con la circunferencia y tantas columnas como el orden del generador.
Paso 6. Test para determinar si el caso es twisted o liso. Este es el paso tal que a partir de las tablas construidas en el paso anterior 5, se determina si el caso es retorcido o es liso. Según el procedimiento de elaboración de las tablas está claro que el número correspondiente a los IASes que pertenecen a la circunferencia aparecerá en cada tabla tantas veces como el orden del IAS. Por ejemplo si el IAS del caso es de orden 3, entonces en la tabla del generador de orden X el número de este IAS aparecerá 3 veces y en la tabla del generador Y aparecerá 3 veces. Y en algunos casos (por ejemplo aquellos en los que uno de los generadores es una involución o uno de los generadores es de orden 3) algunos IASes que no pertenecen a la circunferencia aparecerán repetidos 2 veces en todos los casos. Concretamente habrá tantos IASes repetidos 2 veces en la tabla de ciclos del generador que no sea de orden 2 o 3 como ciclos de orden 2 o 3 tenga la circunferencia (por ejemplo si el IAS). Teniendo estas dos consideraciones en cuenta el caso es retorcido si el número de un IAS que no pertenece a la circunferencia aparece repetido 2 o más veces en la tabla (si el caso tiene un generador de orden 2 o de orden 3, entonces habrá IASes que aparecerán repetidos 2 veces solo por esto; 2 veces repetidas a las que se añadirán otras si el IAS en concreto es twisted).
Para ilustrar esto mostramos a continuación la tabla de ciclos del entorno de la identidad basado en la circunferencia para el generador de orden 2 para tres casos. Los tres son dígrafos de Cayley bigenerados del grupo simétrico S5 (el grado de la permutación de los generadores puede variar; escribimos de memoria). Uno es lo que en otras entradas hemos llamado 1-twisted (y no tiene recorridos hamiltonianos en ninguno de los vértices finales posibles y esto se detecta rápidamente; el algoritmo que tenemos programado lo detecta inmediatamente), otro es lo que en otras entradas hemos llamado 2-twisted (no tiene recorridos hamiltonianos en ninguno de los vértices finales posibles y no es tan sencillo como en los anteriores determinar esto, demostrarlo) y otro es smooth y tiene recorridos hamiltonianos en todos los vértices finales posibles (el IAS es de orden 4 y por lo tanto tiene 4 vértices finales posibles).
Señalamos que 9 de los casos de S5 que en la base de datos de Ruskey y Effler no tienen recorridos hamiltonianos en ninguno de los vértices finales posibles son todos o bien 1-twisted o bien 2-twisted. Todos estos son tambien de tipo 2-4 generados. El resto que no tienen recorridos hamiltonianos en ninguno de los vertices finales posibles son o bien 1/2 entangled o bien cycle-entangled (salvo 2 que se que son entangled, y diria que son 1/2 entangled pero no lo he comprobado). Notese que tambien hay casos de S6 2-4 generados. 2 de ellos pueden ser smooth o twisted (los otros no ya que son o entangled o cycle-entangled). Uno de ellos es smooth, y al ser el IAS de orden impar y ser de aplicacion el teorema de Rankin, no puede tener ciclos hamiltonianos. En una entrada anterior hemos predecido que tendrat caminos hamiltonianos en los dos vertices finales posibles en los que puede tenerlos. El otro caso lo tengo que ver en detalle.
Notese que a Ruskey y Effler solo les interesaban ciclos hamiltonianos y nosotros, utilizando nuestros resultados, determinamos las propiedades de hamiltonicidad para estos casos (y para todos los casos de S5) en todos los vértices finales posibles (ciclos o caminos).
TABLA 1. CASO SMOOTH.
|
Tabla de ciclos de la circunferencia. Caso smooth, generador de orden 2. Números de IASes que pertenecen a la circunferencia: 1,2,24,8,21,12.
|
|
|
| Número de Ciclos. |
Número de IAS |
Número de IAS |
| Ciclo 1 |
1 |
5 |
| 2 |
1 |
24 |
| 3 |
24 |
7 |
| 4 |
8 |
15 |
| 5 |
8 |
21 |
| 6 |
24 |
16 |
| 7 |
12 |
24 |
| 8 |
24 |
20 |
| 9 |
8 |
19 |
| 10 |
8 |
24 |
| 11 |
24 |
9 |
| 12 |
1 |
10 |
| 13 |
1 |
2 |
| 14 |
2 |
11 |
| 15 |
2 |
12 |
| 16 |
12 |
27 |
| 17 |
12 |
13 |
| 18 |
2 |
3 |
TABLA 2. CASO 1-TWISTED.
| Caso 1-Twisted. Los IASes que pertenecen a la circunferencia tienen números 1,2,3,4,5,6. |
|
|
| Número de ciclo. |
Número de IAS |
Número de IAS |
| 1 |
1 |
8 |
| 2 |
1 |
10 |
| 3 |
6 |
11 |
| 4 |
6 |
8 |
| 5 |
5 |
12 |
| 6 |
5 |
11 |
| 7 |
5 |
4 |
| 8 |
4 |
14 |
| 9 |
4 |
15 |
| 10 |
3 |
4 |
| 11 |
4 |
12 |
| 12 |
4 |
16 |
| 13 |
5 |
13 |
| 14 |
5 |
15 |
| 15 |
5 |
6 |
| 16 |
6 |
17 |
| 17 |
6 |
13 |
| 18 |
1 |
6 |
| 19 |
1 |
18 |
| 20 |
1 |
17 |
| 21 |
1 |
2 |
| 22 |
2 |
19 |
| 23 |
2 |
18 |
| 24 |
3 |
14 |
| 25 |
3 |
19 |
| 26 |
3 |
16 |
| 27 |
2 |
3 |
| 28 |
2 |
10 |
| 29 |
2 |
7 |
| 30 |
3 |
7 |
TABLA 3. CASO 2-TWISTED
| Caso 2-twisted. Los IASes que pertenecen a la circunferencia tienen números 1,2,8,9,23,13 |
|
|
| Número de ciclos |
Número de IAS |
Número de IAS |
| 1 |
1 |
4 |
| 2 |
1 |
6 |
| 3 |
8 |
7 |
| 4 |
8 |
15 |
| 5 |
8 |
9 |
| 6 |
9 |
19 |
| 7 |
9 |
23 |
| 8 |
9 |
4 |
| 9 |
9 |
14 |
| 10 |
8 |
10 |
| 11 |
8 |
1 |
| 12 |
1 |
11 |
| 13 |
1 |
2 |
| 14 |
2 |
12 |
| 15 |
2 |
13 |
| 16 |
13 |
17 |
| 17 |
13 |
23 |
| 18 |
13 |
6 |
| 19 |
13 |
14 |
| 20 |
2 |
15 |
| 21 |
2 |
3 |
| 22 |
23 |
3 |
| 23 |
23 |
21 |
| 24 |
23 |
7 |
Se aprecia claramente la diferencia entre los tres:
–en el caso smooth entre los IASes que no pertenecen a la circunferencia no hay repeticiones;
–el caso 1-twisted cae en el otro extremo, todos los IASes que no pertenecen a la circunferencia aparecen 2 veces en la lista;
–y el caso 2-twisted es intermedio entre los dos anteriores, la mitad de los IASes que no pertenecen a la circunferencia están repetidos.
Algunos comentarios adicionales relevantes:
–Cuando uno dibuja el dígrafo queda muy clara la diferencia entre los casos smooth, 1-twisted y 2-twisted.
–Es obvio (por vértice simetría) que si en un caso el entorno de la identidad basado en la circunferencia es smooth, lo será el entorno basado en la circunferencia de cualquier circunferencia del mismo dígrafo y por lo tanto lo será todo el dígrafo.
–Queda claro que, como en los casos cycle-entangled, un caso twisted puede ser twisted por un generador, por los dos o por ninguno (en cuyo caso será smooth).
–Desde el punto de vista de las propiedades de hamiltonicidad los casos 1-twisted son como los casos 1/2 entangled: cuando tienen obstrucciones para la hamiltonicidad, estas se manifiestan de manera muy directa, casi inmediata, y por lo tanto no se pueden considerar complicados. Mas complicados son los casos 2-twisted. En ellos determinar su no hamiltonicidad ya es más complicado, pero también se puede hacer con una demostración relativamente corta.
2.En este punto queremos tratar un tema que venimos tratando desde hace años, sobre el que ya hemos hablado en entradas anteriores (precisamente fue este tema el que nos llevó a desarrollar un método que funciona de manera eficiente para todos los casos) y que reflejaremos en el informe aunque todavía no hemos redactado en él esta parte.
Aunque lo he buscado activamente desde hace tiempo no veo ningún motivo para que no haya casos 3-twisted, 4-twisted etc…y que en algunos casos esta n-twistedness pueda originar obstrucciones a la hamiltonicidad. Ya digo que no he encontrado ninguno de estos casos, pero esto puede ser debido al tamaño de los casos que hemos analizado en profundidad.
A medida que el n en los casos n-twisted sea mayor, el número de IASes que no pertenecen a la identidad que se repitan en la tabla de ciclos del entorno serán menores. Ya hemos visto que al pasar de casos 1-twisted a 2-twisted, el número de repeticiones se reduce a la mitad. Y esta reducción al crecer el n de n-twisted seguirá (no vamos a entrar en detalles, pero hay un motivo que explica esto), lo cual atenuará los efectos del mecanismo que puede ser fuente de obstrucciones a la hamiltonicidad.
Todo esto requiere algo más de investigación que está más allá de nuestras posibilidades ahora mismo.
Todo esto ya lo tratamos en entradas de hace años, aunque con la definición del entorno de la identidad basada en la circunferencia el tema está ahora más claro.
3.Por otra parte está claro que una cosa es que un caso tenga unas determinadas propiedades estructurales que puedan ser causa de obstrucciones a la hamiltonicidad (ya hemos comentado en múltiples ocasiones que las propiedades estructurales son condición necesaria de obstrucciones a la hamiltonicidad, no suficientes) y otra cosa es determinar si en un caso en concreto con estas propiedades estructurales, tiene obstrucciones. Es decir, además del test que determina las propiedades estructurales (salvo que el caso sea smooth en cuyo caso se puede concluir directamente que tiene recorridos hamiltonianos en todos los vértices finales posibles) para determinar si el caso tendrá obstrucciones hay que realizar operaciones adicionales.
Ante esta situación se abren varias vías para obtener métodos de solución eficientes para el problema de recorridos hamiltonianos en dígrafos de Cayley bigenerados (es decir para poder determinar si en un caso con determinadas condiciones estructurales, esta serán suficientes para causar obstrucciones o no):
–una vía es la que adoptamos la última vez que hablamos sobre este tema hace años: obtener un método genérico que sólo tenga en cuenta los efectos del mecanismo que produce las obstrucciones, sin necesidad de construir el entorno de la identidad, construir las tablas de ciclos etc…(operaciones que son intensivas en uso de recursos computacionales). Este es el método que, ya está prácticamente completo (y sobre el que hemos publicado varias entradas hace años) y en principio era el único que íbamos a incluir en el informe.
–otra vía, que es la que se apuntaba en la patente, es analizar los casos tal y como estamos comentando en estas entradas, construyendo el entorno de la identidad (ahora en la versión más general, en base a circunferencia, construyendo las tablas de ciclos e identificando las obstrucciones a la hamiltonicidad). Y está claro que este método de tablas de ciclos es aplicable a otras propiedades estructurales como entrelazado, entrelazado de ciclos (en cuyo caso un mismo IAS puede aparecer varias veces en un mismo ciclo, posibilidad que no puede darse con las otras propiedades estructurales).
Desde el punto de vista de complejidad computacional los dos métodos llegan a las mismas conclusiones. Pero ahora mismo no tengo claro cual será más eficiente, incluso estando en la misma clase de complejidad….
P.s. Cuando pienso en temas de complejidad computacional relacionados con este problema pienso que la mejor medida de complejidad en este problema son operaciones de IASes dados los generadores (por ejemplo, número de IASes que hay que construir para determinar una propiedad estructural, o numero de IASes que hay que construir para decidir si el caso es hamiltoniano o no lo es) y partir del supuesto de que construir un IAS tiene un tiempo constante (cuenta como uno). Este supuesto no es realista, pues hay IASes cuyo tamaño es subexponencial con el grado de las permutaciones y otros cuyo tamaño es polinómico.
HPC MARKET 