HPC. Generalización del método de la patente US 8266098 a (algunos) casos no vértice simétricos.

1. Hace tiempo, años, que quiero escribir una entrada comentando éste tema, pero siempre se me acaba pasando, ya que de momento es sólo una idea que no he explorado ni superficialmente. Realmente no se ni siquiera si es una buena idea….Pero ahora que estoy plenamente concentrado en éstos temas me he acordado y no quería que se me pasase la oportunidad de  publicar la idea.

Claramente los resultados de nuestro método dependen sobre todo de la regularidad del IAS y de como están unidos los diferentes IAS. En este sentido, por ejemplo, mientras sean regulares, el grado de los dígrafos sea 4 (con dos entrantes y dos salientes) y el entorno de  la identidad sea liso entiendo (sólo  hipótesis de trabajo) que nuestro resultado  para estos casos se mantendría aunque los tamaños  de los IASes no fuesen todos  iguales. Si los tamaños de los  IASes ya no son todos iguales, entonces ya no estamos hablando de dígrafos vértice- simétricos.

¿ Siguen siendo válidos las técnicas de la patente para estos casos más generales ?. Entiendo que sí.

¿ Cuán generales son estos casos, con la restricción de vértice-simetría relajada ?. Estoy pensando en una posible relación (reducción) polinómica, por ejemplo, con los grafos de los que se habla en el resultado de Plesnik  u otros que son generales desde el punto de vista de la complejidad computacional.

Tema a estudiar.

2. Actualización día 28, 2:30 am.

Un ejemplo que acabo de construir nos demuestra (como era de esperar) que se pueden construir éste tipo de digrafos y que los métodos de la patente funcionan perfectamente. Desde los preliminares de marcar el vértice inicial hasta el final (marcar opciones, cinco en éste caso, y sacar consecuencias).

Los números indican el “orden” del IAS. El caso ha resultado ser fácil y siguiendo el método de la patentes he encontrado el recorrido hamiltoniano a la primera: es como un dihédrico, el producto de dos IASes de orden 4 (u 8), por otros tantos de orden 2.

Generalización

Esto le da mucha más flexibilidad al método de la patente, pues abarca una clase más amplia de dígrafos (no se si mucho más amplia pues aparentemente hay que cumplir con ciertas condiciones y además así de primeras no parece fácil construirlos, aunque al final igual se puede construir un modelo aleatorio: me ponga 4 de orden, 3 de orden 4, 5  de orden 6 y el resto, los que ajusten).

Pero me empieza a parecer una buena idea o al menos una idea digna de explorar y me pregunto si ya está circulando por ahí. Me pregunto también si  se corresponden con alguna estructura algebraica más flexible que los grupos (no creo)…

En fin hay que ver lo que dan de sí. En el segundo intento voy a intentar, valga la redundancia, que sea más irregular y entrelazado.

3. Actualización 28 de junio 2015,11:30 am.

Disclaimer. Esta parte 3 puede contener errores. Cuando los detecte los iré  corrigiendo.

Seguimos comentando sobre esta  clase de dígrafos.

a) Primero vamos a ponerles nombre: dígrafos IAS-regulares.

b) ¿ Son nuevos ?.

Un artículo sobre otras generalizaciones de los dígrafos o grafos de Cayley.

Cayley graphs and coset diagrams

1 Introduction Let G be a finite group, and X a subset of G. The Cayley graph of G with respect to X, written Cay(G,X) has two different definitions in the literature. The vertex set of this graph is the group G. In one definition, there is an arc from g to xg for all g ∈ G and x ∈ X; in the other definition, for the same pairs (g,x), there is an arc from g to gx. Cayley graphs are generalised by coset graphs. For these we take a subgroup H of G as part of the data. Now the vertices of the graph may be either the left cosets or the right cosets of H in G; and an arc may join the coset containing g to the coset containing xg, or to the coset containing gx. Thus, there are four possible types of coset graphs.

The two types of Cayley graph are in a certain sense equivalent, while the four types of coset graph fall into two distinct types:

–one type encompasses all vertex-transitive graphs,

while the other is seldom vertex-transitive but has more specialised uses in the theory of regular maps.

The purpose of this essay is to explain where the definitions come from and what purposes they serve.

En un principio no aparece el autor pero el estilo es claro y conciso, me sonaba. Y efectivamente, es de un autor conocido: Peter Cameron. Aunque claro y conciso todavía no  me he enterado muy bien sobre éstas generalizaciones, pero aparentemente no incluyen la nuestra.   

c) ¿ Son generales (desde el punto de vista de la complejidad computacional ?

Está claro que pertenecen a la clase de dígrafos 4-regulares, pero posiblemente sean una restricción de  ésta clase que ya por si misma es una restricción. ¿ Cuan general  es la  clase de grafos 4-regulares desde el punto de vista de la complejidad computacional ?. El artículo de Plesnik trata precisamente de ésto:

Extractos.

Garey , Johnson, and Stoclcmeyer [2] have proved that the problem remains NP-complete also in the case of undirected graphs with degrees at most 3. Then Garey, Johnson, and Tarjan [3] have shown. Then Garey, Johnson, and Tarjan [3] have shown the W-completeness under coustraints that the undirected graphs are planar, cubic, and 3-connected. This is obviously the best possible result as for degree bound. Replacing every line uu of undirected graphs with two arcs uv and vu, they have simultaneously settled the NP-completeness in the case of planar digraphs with indegrees and outdegrees at most 3. Here we show that the last result can be still improved as follows: The hamiltonian cycle problem is NPcomplete even in the case of planar digraphs with outdegrees at most 2. Clearly, t bound two on degrees is the best possible

Es decir los casos cuyos vértices tengan como mucho grado 2 de entrada y grado dos de salida (pueden tener menos, por ejemplo 1 de entrada y 2 de salida o viceversa) y son planares, siguen siendo NP-completos. Por lo tanto, entiendo que se puede afirmar que el problema para los dígrafos 4-regulares(2-in,2-out) es también NP-completo, dado que los casos de Plesnik son una restricción de éstos.

Todo ésto nos aclara que nuestros dígrafos son una restricción de una clase restringida que es bastante general, desde el punto de vista de la complejidad computacional, pero no que ellos mismos sean generales. Para demostrar que lo son se debería de construir una reducción de los casos de Plesnik a la generalización que estamos  estudiando.

Es posible que el  lector piense que estas clases son muy restringidas. Sin embargo la cantidad de dígrafos 4-regulares que se pueden construir ya es brutal para un tamaño de vértices no demasiado grande. Si tenemos en cuenta la isomorfia, la cantidad sigue siendo enorme. Por ejemplo para 13 vértices hay 7 371 560 dígrafos 2-regulares (es decir 2-in, 2-out; en otra fuente dan otro dato, similar pero no exacto: 13, 71971687). Que yo sepa no existe una fórmula exacta (o función que se pueda expresar mediante una fórmula más o menos sencilla y de un número exacto) tal que dados estos dos parámetros nos permita calcular el número de dígrafos no isomorfos. Sí existen fórmulas asíntoticas o que acotan superiormente ésta cantidad (para grafos). Ver también este otro enlace. Exista fórmula exacta o no, nos quedamos con que la cantidad ya es astronómica para pequeñas cantidades de vértices.

Posiblemente la mayoría de éstos, de éste tamaño, no tendrán la propiedad que tienen los que estamos investigando. Podemos preguntarnos cuando n (nº de vértices) tiende a infinito, ¿ cual es la probabilidad de que si seleccionamos un dígrafo k-regular sea uno de los nuestros ?. Teniendo en cuenta que la familia que estudiamos es bastante más amplia que los Dígrafos de Cayley, esto nos da una idea de los escasos que son éstos. Son verdaderas joyas, con propiedades muy ventajosas, y por eso se estudian tanto.

d) Método de construcción y cuantificación.

En éste punto presentamos  un método de construcción e intentamos dar  una cota superior de la cantidad de éste tipo de dígrafos dado el número de vértices. Primero ilustramos al lector con otro caso.

Ya he construido otro dígrafo IAS-regular y estoy viendo que no es complicado construir casos. Incluso no es complicado obtener un modelo aleatorio de construcción.

En la imagen el segundo caso que hemos construido. Es un dígrafo de 28 vértices, que tiene IASes de orden IV, III y II (4 de IV, 4 de 2 y 1 de 3):

generalización iases regulares

Dejamos al lector que determine si el dígrafo de la imagen tiene recorridos hamiltonianos o no.

Nota al margen.

En la imagen, a la derecha un dígrafo más pequeño que representa un IAS irregular, pero en  el que se sigue  pudiendo aplicar la técnica de arc-forcing (¿ piensa el lector generalizar el resultado de vértices finales a éstos casos de IAS-irregular ?). Si relajamos la restricción de regularidad en el IAS, y aceptamos este tipo de IASes que se muestran en este perqueño dígrafo, entonces obtenemos una generalización algo más potente que tratamos en el siguiente punto.

Fin de nota al margen.

Siguiendo con la primera generalización, los dígrafos IAS-regulares, hay un dato importante que es fácil ver: el tipo de dígrafos de IAS regular (es decir aquellos que se pueden descomponer IASes regulares de cualquier tamaño) tienen que tener un número par de vértices.

¿ Dado un número par de vértices, cualquiera, podemos construir un dígrafo IAS-regular ?

Sí, uno y varios, incluso bastantes, si el número de vértices que nos dan es elevado.

En lo que sigue vamos a intentar dar una fórmula (exacta o de acotación superior) que nos permita estimar o conocer dado un número de vértices, cuantos dígrafos de ésta clase diferentes podemos construir. Sólo nos interesan los dígrafos conexos y de momento excluimos la posibilidad de ciclos de orden 2, es decir de “involuciones”.

Primero mostramos un procedimiento de construcción y para obtener la fórmula que buscamos vemos de cuantas maneras diferentes se puede realizar ese procedimiento.

El procedimiento es muy sencillo: hacemos una partición en números pares del número de vértices, con p>4, siendo p el número mínimo de vértices de una parte (es decir el  IAS regular mínimo contiene 4 vértices), construimos los IASes correspondientes a cada parte y luego unimos cada uno de estos IASes con otros IASes regulares (al igual que cuando el número de vértices es elevado el número de particiones pares de un número será elevado, el número de maneras de unir con otros IASes estos IASes que se han conseguido para cada partición, será elevado también).

Por lo tanto dado un número (par) de vértices n, una fórmula para calcular el número de dígrafos IAS-regulares correspondiente tendría que tener dos componentes: primero las particiones pares, digamos P2(n); segundo, para cada partición el número de maneras diferentes de unir con IASes regulares a los obtenidos en la partición. Al final tendremos un sumatorio.

Para el primer componente ya existen fórmulas (que al menos nos permiten acotar superiormente la cantidad, de  momento nos es suficiente). Casi de todas ellas me quedo con la siguiente, que aunque sea de acotación, es la más sencilla de recordar: Hardy and Ramanujan (1918) used the circle method and modular functions to obtain the asymptotic solution

 P(n)∼1/(4nsqrt(3))e^(pisqrt(2n/3))
(23)

Como se ve vamos a tener un sumatorio con una cantidad subexponencial de términos.

De momento no tengo claro un modelo combinatorio sencillo para el segundo componente pero seguro que existe. Estoy en ello.

d1) Primer intento.

No estoy convencido de que sea la manera más directa, sencilla y económica de hacerlo, ni siquiera estoy seguro sobre la corrección (y el lector debe de tener ésto muy en cuenta) pero así vamos viendo.

Actualización: Parece que lo más sencillo hubiese sido asumir  que el grafo es bipartito y ahorrarse todo el tema de convertirlo en un bloque conexo. Fin de actualización.

Al final de la primera operación de partición y de construcciones de los IASes correspondientes nos quedan tantos componentes (dígrafos) sueltos como elementos de la partición. Ahora algunas definiciones. Digamos que |V| = número de vértices y |V| = p1+p2….pi es una partición cualquiera de éste número de vértices en números pares. Llamamos pp(|V|) a la partición en números pares del número  de vértices (que también es par). Tenemos i componentes o dígrafos disconexos. Si llamamos saturar un vértice hacer que tenga 2-in y 2-out arcos (condición necesaria para que el dígrafo pertenezca a la clase que estamos construyendo), de momento todos están no saturados. Algunos (la mitad) tendrán 2-in y otros (la otra mitad) tendrán 2-out.

Ahora tenemos  que ir añadiendo arcos. Decidimos primero añadir arcos de cualquier manera para obtener un dígrafo conexo

Las primeras elecciones de arcos son para unir los componentes sueltos y obtener un dígrafo conexo.

Maneras de dibujar el primer arco (por ejemplo de cualquier vértice del componente 1 a cualquiera del resto de vértices): (p1/2)*((|V|-p1)/2). Dividimos por 2 dado que obviamente no es cualquiera con cualquiera, sino 2-in con 2-out. Hemos unido p1, con por ejemplo p2 (pero da igual, podría haber sido con cualquier otro y obtendríamos la misma fórmula). Con esto ya tenemos (i-1) componentes diferentes. Tenemos que continuar con el procedimiento hasta obtener 1 sólo componente, el dígrafo que nos interesa.

Maneras de dibujar el segundo arco (por ejemplo, de nuevo cualquiera del componente que hemos  obtenido en el paso anterior, con cualquiera de los restantes; puede ser un arco que pertenezca al mismo IAS que el primer arco o a otro diferente, ésto da igual):

(((p1-1)+(p2-1))/2)*(((|V|-(p1+p2))/2) < |V|^2,

Maneras de dibujar el tercer arco (idem):.

(((p1-1)+(p2-1))-1)+(p3-1)/2)*((|V|-p1+p2+p3)/2) <|V|^2,

Maneras de dibujar el iésimo-1 arco.

Para obtener un sólo componente tenemos que utilizar ( i-1) arcos.

(((p1+p2+p3…+(pi-1)-2(i-1))/2)*(|V|-(p1+p2+p3+…+p(i-1))/2) <|V|^2

Como cada una de estas maneras de conseguir un dígrafo conexo se puede hacer de manera independiente de las otras  la manera de combinar cada una de estas maneras es la multiplicación.

Para cada partición, obtendríamos un productorio acotado por < |V|^2i. 

Por lo tanto una cota superior a la cantidad que estamos estimando es de momento pp(|V|)*|V|^2i. < O (subexp |V|).

Ya tenemos un sólo componente y de momento no hemos saturado ningún vértice. Tenemos (i-1) vértices con tres arcos y |V|-(i-1) vértices con dos arcos cada uno. Como de momento nos interesa sólo una cota superior vamos a simplificar: nos olvidamos de los arcos semi-saturados y consideramos que todos están en situación 2-in o 2-out. Tras esta simplificación ahora podemos pensar en un digrafo bipartito con dos partes, cada una con |V|/2 vértices. Y, de nuevo para simplificar, y para obtener una fórmula comparativa con la fórmula que hemos dado para dígrafos generales, nos da igual la conexión y la isomorfia. Calculamos el número de grafos bipartitos de grado o valencia 2 (como todos los arcos van en un mismos sentido, de un grupo de vértices, al otro, ¿ nos podemos olvidar de la dirección?).

e) ¿ Que ganamos y que perdemos con ésta generalización ?

stá claro también que hay parámetros (por ejemplo el orden del IAS / DAS, de la circunferencia etc…) y propiedades (por ejemplo la propiedad de lisura en el entorno de la  identidad) que, debido a la pérdida de simetría, o dejan de tener sentido (orden de IAS o de circunferencia, ya no habría una medida única para todo el dígrafo) o ya no se pueden testar de manera local y extrapolar a todo el dígrafo (la lisura en el entorno de la  identidad; ahora hay comprobar que se da en cualquier entorno). No está claro tampoco no lo sé) que esta nueva clase se pueda describir de manera sucinta. Por lo tanto al pasar a esta nueva clase,  se pierde potencia en los métodos.

4. Otra generalización: los dígrafos arc-forcing.

Estoy pensando que, en principio, nada nos obliga a que un IAS sea regular, en el sentido de que no se crucen los arcos que en él están contenidos.

En realidad, podemos suponer que la única propiedad que interesa que se conserve es que el dígrafo se pueda descomponer en grupos de arcos entre los que se pueda aplicar la técnica del arc-forcing, es decir que la inclusión de un arco en el recorrido hamiltoniano excluya a otro en contacto inmediato con él, y que ésta exclusión a su vez hace que un tercero inmediato quede incluido así hasta que se llega al primer arco que se había incluido. Llamemos a éste tipo de dígrafos, Dígrafos Arc-Forcing.

De  hecho, como  ya hemos comentado en la descripción de la patente, ni siquiera todos los Dígrafos de Cayley tienen el IAS regular: la mayoría de los abelianos o commutativos no tienen IASes regulares. Sin embargo si se conservan otras propiedades que los hacen vértice simétricos.

Digo en principio pues nos interesa que en las nuevas clases que estamos definiendo, que en las generalizaciones, sigan siendo aplicables lo máximo posible algunas de las técnicas de la patente, como el resultado de los vértices iniciales posibles, elegido un vértice inicial.

Con ésta relajación abarcamos a una clase que entiendo que es bastante más amplia. ¿ Cuan amplia ?. Por otra parte la técnica del arc-forcing es bien conocida desde hace décadas. ¿ Está ya definida esta clase que para nosotros es nueva ?.

He comprobado también sobre los Cayley Abelianos, que hacía años que no había vuelto a mirar y salvo que se cumplan determinadas condiciones arítmeticas los IASes son irregulares, multicruce. Sí creo recordar cuando los estudié, que en éste caso el resultado sobre vértices finales sí era generalizable así como todo el método: representar éstos dígrafos en forma de IAS era muy útil, aunque visualmente no eran muy atractivos.

A continuación algunos IASes irregulares o digrafos arc-forcing que he construido. Por deformación profesional utilizo en algunos arcos la línea continua y en otros la línea discontinua. A diferencia de los Dígrafos de Cayley no significan nada. En la primera linea los tres digrafos etiquetados A,B,C son mínimos:  si se les quita algún arco dejan de cumplir con la definición de arc-forcing. Podemos definir como unidad al par de arcos que salen de un vértice, uno de linea discontinua y el otro continua. Debajo, otros que no son mínimos (por cierto, el de abajo a la derecha es el que hemos  mostrado en una imagen anterior). Se les puede quitar arcos y seguimos  teniendo IASes. Todos los dígrafos no mínimos se pueden transformar en A, quitando una o varias unidades, pero no en B o C. Hay una relación en los dígrafos mínimos, de momento curiosa, pero que ya casi puedo demostrar que será robusta: nº unidades + nº de saturaciones + 1 = de vértices. Si finalmente la pudiese demostrar (como se ve si empezamos con una linea vertical con una, una y “media”, dos unidades etc…, en los extremos se puede construir un “triángulo” añadiendo una unidad y en medio serán cuadrados, añadiendo una unidad y media; seguramente todos los mínimos se podrán construir de ésta manera y teniendo ésto en cuenta es muy posible que se pueda deducir la relación señalada), podría utilizarse para identificar mínimos.

En realidad tanto los mínimos como el resto son válidos para construir los dígrafos de la clase que estamos definiendo. Pero igual se puede construir clases de equivalencia de mínimos y a lo mejor (mera ocurrencia de momento) esto es relevante para el problema de recorridos hamiltonianos en este tipo de dígrafos (igual se puede demostrar que dado un dígrafo, al transformarlo en el mínimo se mantenga la propiedad de hamiltonicidad; insisto, mera ocurrencia que puede evaporarse a la primera prueba).

Provisional: El  resultado de los vértices finales creo que sí se puede generalizar. Basta con hacer una analogía de cada caso (me refiero de momento a los mínimos, pero seguramente será ampliable a todos), con el caso homólogo regular (homólogo en el sentido de que tenga el mismo número de unidades. Etiquetamos primero los vértices del irregular con naturales (o con lo que sea). Luego construimos el homólogo regular y le vamos asignando a cada vértice correspondiente las etiquetas del irregular (los saturados aparecerán repetidos). Con aquellas etiquetas del irregular que aparecen en las posiciones del regular que serían vértices finales posibles, podemos reconstruir el mismo argumento en el irregular y obtener los vértices finales posibles de éste que serán los mismos. Sugiero que el lector lo pruebe con el mínimo más pequeño y luego es lo mismo. Fin de provisional.

Hablando de recorridos hamiltonianos, he construido un caso, el que figura debajo del todo, pero que no incluye sólo arc-forcing mínimos: le he cerrado con un IAS regular de orden 6, que es el del contorno. El lector podrá comprobar que contiene también un B y dos A.

generalis

He utilizado el método de la patente para éstos casos y funciona a la perfección (he encontrado un ciclo hamiltoniano). He marcado como vértice final e inicial dos vértices del IAS regular. Da la impresión de que todos los construidos con los mínimos van a ser fáciles. Sólo una impresión provisional. Nótese que es planar.

Por cierto, tanta estructura en los mínimos apesta, si el lector me permite la expresión: ¿ no habrá una estructura algebraica subyacente  ?.

5. Finalmente otra generalización.

La obvia: una combinación de las dos anteriores.

Con todo esto doy por satisfecha de momento mi curiosidad sobre estas generalizaciones. Si tengo tiempo en posteriores ocasiones y trabajo sobre ello, actualizaré.

Apéndice: enlaces relevantes encontrados para toda la entrada.

–una survey reciente (2010) sobre tests positivos de hamiltonicidad en dígrafos generales y algunas restricciones. Creo que toda la literatura se centra sobre todo en tests positivos. Hecho de menos literatura sobre tests negativos u obstáculos a la hamiltonicidad (y creo  que existen cosas publicadas). Sin embargo, uno de los grandes resultados de la teoría de grafos fue determinar todos los obstáculos posibles a la planaridad.

A SURVEY ON HAMILTON CYCLES IN DIRECTED GRAPHS DANIELA KUHN AND DERYK OSTHUS ¨ Abstract. We survey some recent results on long-standing conjectures regarding Hamilton cycles in directed graphs, oriented graphs and tournaments. We also combine some of these to prove the following approximate result towards Kelly’s conjecture on Hamilton decompositions of regular tournaments: the edges of every regular tournament can be covered by a set of Hamilton cycles which are ‘almost’ edge-disjoint. We also highlight the role that the notion of ‘robust expansion’ plays in several of the proofs. New and old open problems are discussed.

Por otra parte si decenas, cientos sino miles (quizás esta cantidad ya sea demasiada) de investigadores han publicado sobre tests positivos de hamiltonicidad, será porque son útiles, porque son informativos, porque ayudan al investigador de éste problema, porque le ahorran tiempo de búsqueda. Sin embargo el examinador de mi segunda solicitud de patente considera  que los tests que yo propongo, que son igualmente útiles en el mismo sentido señalado, para una clase muy concreta de dígrafos, son meras ideas abstractas, que se agotan en sí mismas, sin consecuencia práctica ninguna. Increíble pero cierto.

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: