2 casos de S6 (720 vértices), C2C4.

Disclaimer. Entrada en construcción en la parte de actualizaciones. Puede contener errores. Estará terminada cuando desaparezca este mensaje. 

¡¡ Actualizado 19 de septiembre: ya está claro el esbozo del método de obtención de un certificado de no hamiltonicidad para los casos twisted. Ya le hemos puesto nombre y todo :-): método de la escalera. Para más detalles ver en este mismo post la actualización correspondiente al final !!.

En esta entrada mostramos las imágenes correspondientes a 2 los dos casos de S6 del tipo C2C4 (es decir, que tienen un generador de orden 2 y otro de orden 4).

Tenga el lector en cuenta que ya en estos casos, que si tienen recorridos hamiltonianos, tienen pocos, ya empieza a ser prohibitivo el  usar métodos algorítmicos. Incluso, como veremos, aplicar nuestro algoritmo, tal y como está programado ahora mismo (sin incorporar los últimos avances que hemos descrito en las últimas entradas) es prohibitivo: puede tardar semanas.

1.Caso de S6, C2C4, IAS 5, Circunferencia 10. No es ni 1-twisted ni 2-twisted.   

Comentar primero que finalmente he puesto a prueba este caso  con nuestro algoritmo y tras varios días tuve que apagarlo (ya que necesitaba usar el ordenador para otros temas) sin haber podido determinar si tiene recorridos hamiltonianos en uno de los  dos vértices finales posibles en los que puede tenerlos.

Por ello nos resulta de gran interés poder pulir los métodos que estamos describiendo en las anteriores entradas para poder determinar sus propiedades de hamiltonicidad sin necesidad de aplicar el algoritmo. O de manera alternativa También incorporar los avances señalados en las anteriores entradas al algoritmo (los que aceleran el encontrar un recorrido hamiltoniano en este tipo de casos cuando existe) para que pueda determinar esto mismo de manera más eficiente.

Nota. Es muy importante tener en cuenta que una cosa son los problemas de existencia y otra los problemas de construcción. En algunos  casos nos puede interesar conocer si un caso en concreto puede tener recorridos hamiltonianos o no, sin objetivos constructivos, sin necesitar construir un recorrido hamiltoniano en concreto aunque estos existan.

En otros casos una vez aclarado positivamente el tema de la existencia nos puede interesar construir uno, varios o todos los recorridos hamiltonianos del caso que estudiamos.

Cualquiera de estos dos problemas o de estas dos fases del mismo problema nos interesa resolverlos de la manera más eficiente posible. Tan práctico y útil para el investigador de estos problema es lo uno como lo otro.  Espero que esto lo tengan claro en la USPTO.  Fin de nota.

Como se puede ver no es ni 1-twisted ni 2-twisted y según la definición más restrictiva  sería smooth. Pero como ya como comentamos en otra entrada, no nos interesa una definición esencialista, escolástica, sino  una pragmática.  ¿ Que pasa en este tipo de casos, según el análisis que hemos presentado en  la entrada anterior ?. ¿ Es twisted o smooth en sus efectos ?. Lo dejamos como problema de momento…

La imagen se puede agrandar, para un poco  más de claridad. No está completo. Se muestra con una linea más oscura solo uno de los pares de permutaciones repetidas al expandirlo.

s6-twisted-o-smooth

Vamos a calcular las cotas teóricas de las fronteras para este caso, según el método apuntado en la entrada justo anterior. Tiene 720 vértices /ciclos de orden 4 / orden de IAS 5 = 36. Hay 720 / 5 = 144 IASes. Por lo tanto la cota de la frontera del generador 2 es  (36,108). Y para el generador de orden 4 es (72,72). ¿ No hay un patrón aquí: cuando el ciclo es de orden 2, no tiene que estar la frontera en la  mitad ?. En fin, las cotas teóricas para este caso son [C2(36, 108);C4(72,72)].

El rango que está entre las cotas teóricas de las fronteras tiene 36 pares. Es bastante más amplio que en el caso 2-twisted estudiado en la entrada anterior. Lo que no tengo claro es como funciona en este caso el mecanismo de amplificación, al no ser ni 2-twisted ni 1-twisted. No puedo dimensionarlo esta segunda pata con la que anda el método (de momento ni por aproximación) y esto es clave para determinar si el caso puede tener recorridos hamiltonianos (en este caso caminos) o no. No es fácil analizar manualmente estos casos de 720 vértices…

2. Caso de S6, IAS 6, circunferencia 3 (6 IASes). Es 2-twisted.

Este caso, pese a ser 2-twisted, tiene recorridos hamiltonianos según la investigación de Ruskey y Effler. No sabemos si se conformaron con encontrar un RH en uno de los dos vértices finales posibles que pueden serlo de un ciclo hamiltoniano o lo determinaron para los dos. Imaginamos que la primera opción es la correcta.

La pregunta es si este caso también tiene recorridos hamiltonianos en el resto de vértices finales posibles. Para ello pusimos a prueba este caso con el algoritmo para encontrar un camino hamiltoniano en uno de los vértices finales posibles y tras varios días de computo tuvimos  finalmente que apagar el programa ya que necesitábamos utilizar el ordenador para otros usos.

¿ Podemos utilizar los métodos de las  entradas anteriores para determinar si tiene recorridos hamiltonianos en todos los VFs sin necesidad de aplicar el algoritmo ?.

El caso en cuestión (no está completo).Hemos marcado en rojo las permutaciones que se repiten en el IAS nº 8 y en el nº 23. Esto demuestra que el caso  es 2-twisted:

s6-ias7

Primero es interesante comparar este caso con el caso 2-twisted de S5 que estamos comentando en otras entradas. Las propiedades de ese son S5, IAS 5, Circunferencia 6. Como el IAS es 5 se aplica el teorema de Rankin y sabemos que no puede tener recorridos hamiltonianos. Este de S6 es IAS 6, circunferencia 6 y sabemos que si tiene recorridos hamiltonianos al menos en uno de los dos vértices finales posibles. Aunque los dos son 2-twisted, por ser uno de IAS impar y el otro par no son del todo comparables.

Vamos  a determinar las cotas teóricas de las fronteras del rango de la distribución para este caso.

–C2: 720 vértices  /ciclos de orden 4 /IAS de orden 6 = 30. 720 / 6 = 120. Por lo tanto (30, 90).

–C4: 720 vértices / ciclos de orden 2 / IAS de orden 6 = 60. Por lo tanto (60,60).

Las fronteras teóricas del rango para este caso son [C2(30,90); C4(60, 60)]. Hay unos 30 pares con activaciones que podrían tener recorridos hamiltonianos.  Bastante más que en el  caso 2-twisted anterior.

Como este caso es 2-twisted, y ya tenemos referencias de casos similares (similares pero no exactamente con los mismo parámetros: el otro caso 2-twisted tiene IAS 5 y este IAS 6) más manejables, vamos a ver si es posible dimensionar la otra pata del método (lo que hemos  llamado la media) en él.

En otra entrada hemos manejado la idea de que el amplificador es constante dado el orden del IAS. Si esto se confirmase ya estaría gran parte del  trabajo realizada. Sólo habría que determinar cual es la contribución del tamaño del IAS a la diferencia en los efectos del amplificador.

Actualización 15 de  septiembre de 2016.

Ya tengo una idea sobre como dimensionar esta segunda pata. Cuando tenga todo más claro lo publicaré. Ya adelanto que, si finalmente es válido, y creo que sí, sería una cota inferior de la media. No es muy eficiente si tomamos como tamaño del caso el grado de la permutación ya que, de momento, implica activar por el generador de orden 2 tantos IASes como tenga  la frontera de este generador en la distribución. Pero es posible que el método actual sea reducible a fórmula una vez se conozca el grado de retorcimiento.

En retrospectiva, diría que obvio también. Un resumen: sabemos que para que pueda haber un recorrido hamiltoniano, hay que activar tantos IASes como tenga la frontera del generador de orden 2. Por ejemplo 30 para el primer caso de los 2 que figuran arriba. Entonces los seleccionamos de tal manera que intentamos minimizar la activación de IASes por el generador de orden 4. Esto se puede hacer (incluso automatizar) y no es complicado. Tras cada activación, controlamos las consecuencias (como en el algoritmo de la patente). Habrá momentos en los que no podamos continuar y habrá que dar marcha atrás: si se ha activado un IAS por el generador 2 siguiendo el principio  de minimización y esto nos lleva a contradicción, entonces habrá que activarlo por el generador de orden 4 para poder continuar. Así hasta generar los 30. Al final de este proceso obtenemos un par, por ejemplo (30, 60), que no suma todos los IASes que tenga el caso. Con este par calculamos la  proporción o media mínima (60/30), que en este caso sería de 2 (2 IASes del generador de orden 4 por cada uno marcado del generador de orden 2). Y tanteando encontramos el número de IASes que se tienen que activar por el generador de orden 2, para que con esta media el par obtenido sume el número total de IASes.

Un ejemplo real: el caso 2-twisted que hemos presentado en la entrada anterior. Si activamos el primer IAS por el generador 2, se activan 5 IASes por el generador 4. El contador del par es (1,5). Luego podemos activar varios (hay varias alternativas equivalentes) que van a hacer que el contador pase a (2,8). La siguiente activación el contador pasa a (3,9). Y la siguiente a (4,10). En este punto hay una activación de otro IAS (hay dos equivalentes en este sentido) que haría que el contador pase a (5,11), pero esto lleva a contradicción. Por lo tanto con los 4 IASes ya activados, tenemos que necesariamente este IAS se active por el generador de orden 4 y el contador pasa a (4,11). No he terminado el análisis pero ya podemos calcular una media (la final podrá ser diferente, pero estimo que no muy diferente): 11/4 = 2,75. Si con esta media mínima activásemos 7 IASes por el generador 2 (el mínimo necesario), obtendríamos 19,25 IASes activados por el 4. Aunque redondeemos por lo bajo a 19, tenemos que 19+7= 26 > 24, el número total de IASes. Por lo tanto tenemos que activar menos, por ejemplo 6. En este caso aplicando la media obtenemos menos  IASes que la cantidad total, 6+16,5 = 22,5. ¿ Debemos de redondear hacía arriba o  hacía abajo ?. Supongamos que hacia abajo, tenemos (6,16) y 2 IASes por asignar. ¿ Como se deben de asignar ? Esto es lo que queda por aclarar. En cualquier caso, como se ve, el par que está justo por encima de la frontera (7,19), es imposible de alcanzar con esta media minima. ¿ No podemos concluir sólo por esto que no pueden existir recorridos hamiltonianos en este caso, solo por esto ? Creo que intuitivamente es así, pero tampoco lo tengo 100% claro de momento.

Como se ve el método es sencillo y casi evidente aunque hay que pulir el final.

Fin de actualización.

Actualización 16 de septiembre 2016.

Tras consultar con la almohada me sigue pareciendo un método válido: si activando el mínimo número posible de IASes por el generador de orden 2 (es decir llegando a la frontera de este generador) de manera que se activen el mínimo número posible de generadores de orden 4, es decir obteniendo la media mínima, ya nos salimos del rango, con cualquier otra activación sería peor.

Pero veo un problema: tenemos que estar seguros que estamos trabajando con la media mínima. Hemos dado por supuesto que determinar la media mínima es un problema sencillo. Pero ¿ no estamos en realidad sustituyendo (reduciendo) un problema complicado (determinar si un caso tiene recorridos hamiltonianos, por otro problema complicado (encontrar esta media mínima) ?. Ya hemos visto que durante el proceso de determinación de la media mínima, en determinados momentos, hay varias alternativas equivalentes. ¿ No es posible que sólo una secuencia de estas alternativas nos lleve a la media mínima ? Nos gustaría tener evidencias claras que obtener la media mínima es sencillo.

De momento, además de la  manera de pulir el método, esta es la principal objeción que le veo.  Y es seria.

Veamos el caso que estamos analizando (S5, 2-twisted) con más detalle. En la imagen siguiente aparece la situación tras haber marcado los IASes 1= 2 (es decir por el generador 2; para este primer paso todos los IASes son equivalentes y hemosmarcado el de la identidad por convención); IAS 3 = 2 (para este segundo paso hay varios equivalentes que suman 3 al contador en C4; es el mínimo y entiendo que aquí marcar uno u otro no marca la diferencia); 7=2 (aquí creo recordar que no hay opción, es el único tal que al ser marcado suma 1 al contador en C4) y 12=2 (no recuerdo si es el único que suma 1 en este momento o hay más; lo repasaremos en su momento).

c2c4-nuevo-metodo

Como se ve, la situación tras marcar todos estos es que el contador indica (4,10) y por lo tanto faltan 10 IASes por marcar (recordemos que en este caso en total hay 120/5=24 IASes). Detallamos esto (esto ya es muy costoso y no es necesario hacerlo en el método):

–si activamos el 13 por 2, activaría 1 de 4, el 14,

–idem el 15.

–idem el 22.

–idem el 5 con el 19,

–idem el 10,

–idem el 21,

–el 9 activaría 2 de C4, el 19 y el 14,

–idem anterior el 24,

–el 19 activaría 5 de C4, el 10, 9, 21, 5, 24.

–idem el 14 con el 13, 24, 22, 9, 15.

Tenemos también los siguientes ciclos de orden 4 con 2 arcos marcados:

–el nº 9,

–el nº 16,

–el nº 17,

–el nº 18,

–el nº 28,

Y hay ciclos más largos (que incluyen ya arcos de los dos generadores que están a falta de dos arcos). No vamos a detallarlos pero si los tendremos en cuenta a la hora de detectar las contradicciones.

Se ve una cierta estructura y ya en esta situación podemos deducir muchas cosas. De lo comentado anteriormente se ve que si queremos seguir el principio de minimización, tenemos que activar cualquiera entre la siguiente lista: el 13,15,21,5,10,22. Cualquiera de ellos activan sólo uno de C4 y esto es lo mínimo que podemos obtener. Veamos que pasa activando cada uno de ellos:

–si activamos el 5 por C2, contradicción (necesariamente 10=4, lo cual nos lleva a una serie de consecuencias que terminan en contradicción: un ciclo que recorre completamente el IAS 4, dado que el 5=2, el 22=2 y el 9=2.  En conclusión, 5 = 4.

–si activamos el 10=2, entonces el 5=4 (actuamos como si no supiésemos el resultado del punto justo anterior), el 19=4. De esto se sigue que el 22=2, 14=4, el 24=4 (para evitar que el IAS 11 sea recorrido por un ciclo). Pero si 6=4 (resultado que se obtiene al marcar 1=2), 5=4, 19=4 y 24=4 el ciclo 26 queda completado y tenemos una contradicción. En conclusión 10=4.

–si activamos el 21=2, entonces 19=4 y punto (no he encontrado más consecuencias ni contradicciones). Aquí hay una alternativa.

Espero que al activar los otros tres que quedan obtengamos una situación similar.

–si 13=2 entonces, 14=4, 15=4 (si no se completa un ciclo que cubre todo el IAS 2), 21=2 (se sigue de lo anterior y de que si no  un ciclo de orden 4 se completaría, el 16), 19=4 (se sigue de 21=2), 9=2 (si no el ciclo de orden 4 nº 14 se completaría). Pero entonces se completa un ciclo que recorre el IAS 23, lo cual es la contradicción que se esperaba. Conclusión: 13=4.

–si el IAS 15=2, entonces contradicción (13=4,14=4,21=2 y 24=2, pero entonces se completa el ciclo que recorre el IAS 20). Conclusión: 15=4.

–si activamos el 22=2, entonces 14=4 y punto (no he encontrado ninguna consecuencia adicional ni contradicción al realizar esta activación). Esta puede ser una alternativa.

Tras marcar de manera alternativa todos estos IASes tenemos que  cuatro de ellos tienen que ser marcados por 4 y entonces el contador pasa a ser de (4,14) y 2 de ellos quedan como alternativa. Están por activar 6

Con los datos que  tenemos ya podemos ir anticipando un poco los resultados, aunque habrá que esperar al análisis.

Primero marcamos los cuatro IASes indicados por 4. Con esto ya se marcan todos los restantes y ya surge una contradicción. El resultado final depende del orden en el que se extraigan las consecuencias. Este es un tema a pulir.

Posibilidad 1. Un posible orden es el que sigue:

–Primero comprobar los ciclos del generador de orden 4. Esto  es lo más sencillo.

–luego comprobar los ciclos de mayor tamaño, por ejemplo los que cubren los IASes completos. Diría que son los segundos de menor tamaño.

–Luego comprobar ciclos mayores.

Según esto, tendríamos

–14=2, si no, ciclo de orden 4 nº 1.

–21=2, si no ciclo de orden 4 nº 9.

–22=2, si no ciclo de orden 4 nº 18

Y con esto terminamos las posibilidades de ciclo de orden 4. Nos quedan

Posibilidad 2. Otra regla que me gusta más es activar los IASes que quedan teniendo buscando lo más parecido a un recorrido hamiltoniano, que es lo que en definitiva estamos buscando: un longest path. Es decir los activamos de tal manera que  se genere el ciclo (no hamiltoniano) más largo posible o ¿ de manera equivalente el cycle cover ? con el mínimo de componentes. De alguna manera esta es la regla inversa de la anterior.

Posibilidad 3. Las dos posibilidades anteriores parecen ya un poco arbitrarias y no sé si tienen mucho sentido: ¿ que información útil se puede extraer tras haber llegado en un proceso a una contradicción ? ¿ Y más concretamente que información útil para lo que nos ocupa podemos  extraer al rematar las dos posibilidades anteriores ?. La conclusión principal de momento es que al llegar al contador (4,14) , con una media de 3,5, bastante elevada, llegamos a una contradicción y tenemos que dar marcha atrás. El último IAS que habíamos marcado por 2 marcarlo por cuatro (es decir el 12). Esta sería la tercera posibilidad: al llegar a una contradicción que no nos permita seguir adelante, anotamos el resultado del contador y hacemos backtraking. Nos quedamos con esta posibilidad, sin olvidar de momento las otras. ¿ Que pasa si haciendo este backtraking todos los nodos terminales nos llevan a contradicción sin poder llegar a la frontera ?.

Por otra parte, y al margen de todas estas posibilidades, no me queda claro si está siendo mucho más fácil encontrar la media mínima (ya se ve que hay que hacer backtraking por igual) que determinar si el caso tiene recorridos hamiltonianos aplicando el algoritmo incorporando el acelerador que hemos descrito en la últimas entradas. Y esto es clave también. Primero veamos a donde nos lleva todo esto y luego estudiaremos este otro tema.

Fin de actualización.

Actualización 19 de septiembre de 2016. 

Primero comentar que hay un paso de la actualización anterior que no tengo claro que sea correcto. Es correcto deducir, por los análisis que hemos realizado que cada uno de ellos debería de ser marcado por el generador de orden 4. Pero,  ¿ es correcto marcarlos todos a la vez ?. ¿ No es más correcto hacer este mismo análisis pero de manera secuencial ?. Es decir, diría que lo correcto es marcar primero por ejemplo el IAS 5 (que sabemos que tiene que ser marcado por el generador 4), por este generador y luego marcar otro, por ejemplo el 9, de los que sabemos que también lleva a contradicción (sin haber marcado el 5) por el generador de orden 2 para ver si también lleva a contradicción condicionado a haber marcado el 5 =4, y ver si con esta situación también se llega a contradicción.  Si es así, marcar el segundo IAS, el 9 por el generador 4 para ver si lleva a contradicción. Si no llevase a contradicción, se repite lo mismo con el siguiente IAS, y así los todos (en este caso los cuatro) succesivamente.

Segundo comentar que he repetido los análisis desde el inicio. 1=2 x convención (marcando cualquier otro llegaríamos al mismo resultado). 3=2, idem, por convención (idem). 7=2 (en este punto hay una alternativa equivalente, marcar el 10). 10=2 (en este punto hay una alternativa equivalente, marcar el 12; es lo que hicimos en la ocasión anterior). Siguiendo esta ruta se llega a una situación equivalente a la que se llega con la ruta de marcar el 12.  Hay 6 alternativas equivalentes y 4 de ellas llevan a contradicción. He probado el proceso indicado en el punto primero de esta actualización y tanto 5=4 y 9=2 como 5=4 y 9=4 llevan a contradicción. Habría que repetir lo mismo con todos los pares posibles para ver si con todos se llega a contradicción (predecimos que así será). En cuyo caso ya no se puede seguir más adelante por esta ruta. Anotamos el valor contador al marcar el último IAS tal que al extraer las consecuencias (según el algoritmo nuestro) se llegue a una situación estable sin contradicción. Es decir en este caso el 5. Concretamente el valor obtenido es (5,12), es decir una media de 2,4.

Tras repetir la búsqueda de la media mínima con atención, sigo pensando que encontrar la media mínima no  va a ser complicado. Ya haremos un análisis de complejidad computacional.

Y también que, al calcular esta media,  sigamos la ruta que sigamos vamos a encontrar el mismo resultado. Es decir, siguiendo con el ejemplo antarior, cuando el contador llegue a (5,12), independientemente de la ruta que hallamos seguido, se llegará a contradicción.

Entonces repetimos la pregunta que ya hicimos  en la última actualización: ¿ que pasaría en este caso ?. Pasaría lo siguiente: tenemos que relajar las condiciones de la media mínima y, digamos, subir un escalón hacía la “media mínima siguiente”. ¿ Como ?. Pues siguiendo con el ejemplo anterior, si hemos marcado secuencialmente 1=2, 3=2, 7=2, 10=2, 5=4 y hemos llegado a contradicción con un contador de (5,12), al relajar tenemos que marcar 1=2, 3=2, 7=2, 10=4 (es decir hacemos un backtraking), y luego seleccionamos el IAS que a partir de aquí siga la ruta mínima. Así hasta que de nuevo lleguemos a un punto en el que no podemos seguir más (por haber una contradicción).

Es posible que con esta relajación nos pase lo mismo y todas las rutas posibles asociadas a ella nos lleven a contradicción sin que el contador sume 24 (el número total de IASes). Entonces hay que subir otro escalón. ¿ Así hasta cuando ?. Entiendo que hasta obtener, sin contradicciones, un par del rango que sume el número total de IASes.

Lo más importante: obviamente las medias asociadas a estas nuevas rutas mínimas serán cada una de ellas superiores a las anteriores: cualquier activación que se aleje de la ruta mínima inicial obtendrá, necesariamente una media superior y lo mismo con las nuevas relajaciones. Por ello podemos llamar a este método el método de la escalera.

¿ Por qué es importante esto ?. Ilustremos lo que tengo en la cabeza con el ejemplo anterior: con la ruta mínima más exigente tenemos un contador de (5,12) y una media de 2,4. Si encontramos el valor tal que al aplicarle este 2,4 el contador sume 24 (el nº total de IASes de este caso), estaría entre 7 y 8 (7×2,4=16,8+7=23,8 y con 8 tendríamos 27,2, bastante más alejado de 24 que con 7). Es decir ya con esta media gran parte del rango posible se queda fuera y estamos casi con una única posibilidad, el valor del rango de (1,17). Si la segunda media mínima es algo superior digamos 2,8, ya el par correspondiente a este valor quedaría fuera del rango posible y sólo serían posibles los valores del rango en los que sabemos que no puede haber recorridos hamiltonianos.

Entiendo que con este método de la escalera podemos obtener demostraciones de no existencia más rápidas que lo que ahora tenemos (aplicando el algoritmo modificado)…Por supuesto hay que ir atando cabos, cortando flecos y puliendo el método. Queremos inssistir una vez más en que la propiedad estructural que hace que estos casos no tengan recorridos hamiltonianos es la propiedad de ser twisted.

Y ojo, lo que obtenemos es un certificado de no hamiltonicidad. Me explico: ¿ que se supone que tendría que pasar aplicando este método en los casos que si tienen recorridos hamiltonianos ? Que se llegaría a un par del rango sin contradicciones que sume el nº total de IASes y que esté dentro del rango posible. Pero realmente que el método permita llegar al rango posible no es demostración de que tiene recorridos hamiltonianos. Aunque pensamos que los obstáculos a la hamiltonicidad que hemos señalado en el método de la patente son los únicos posibles y todos los resultados experimentales indican que así es, no hay demostración sobre ello.

Para aquellos casos que si tengan recorridos hamiltonianos, este método se puede utilizar también para acotar los pares del rango posibles entre los que si podemos esperar obtener recorridos hamiñtonianos.

Creo que lo hasta aquí descrito es un avance significativo con respecto a los métodos que ya hemos presentado:

–recordamos que este blog precisamente empezó a publicarse (y en principio iba a ser un blog sólo vinculado a estos temas) para presentar un método (algorítmico) que permitía encontrar soluciones a casos complicados (e incluíamos a los casos que no tienen recorridos hamiltonianos). Sigue estando publicado en el primer post.

–un segundo avance ha sido de hace poco cuando hemos encontrado una subrutina que incorporada al algoritmo más general permite acelerar el determinar que un caso no tiene recorridos hamiltonianos (dado un vértice final posible). Hemos publicado varias entradas este verano presentando esta subrutina. No tengo claro que este método sea más rápido que el anterior en todos los casos y es un tema pendiente de estudiar.

— y el tercer método, que pensamos mejora significativamente a los dos anteriores es el que estamos presentando ahora. Cuando lo tengamos pulido 100% y puesto a prueba experimentalmente haremos una entrada detallada. Entre otras cosas, cuando tenga todos cabos atados, quiero ver como funciona para casos de S6.

Fin actualización.

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: