La cubierta de la rejilla grafo con ciclos simples

Question

Tengo dos dimensiones n x m de cuadrícula gráfico. Y quiero saber de cuántas maneras, esta red puede ser cubierto con ciclos simples (puede ser un ciclo de uno o puede ser de muchos ciclos) de tal manera que cada vértice está cubierto por un solo ciclo. Los ciclos de longitud 1 (que cubren sólo un vértice) no son considerados.

Por ejemplo, todos los de la 1xn cuadrículas habrían $0$ ciclos, y por un 2x4 de la cuadrícula se puede cubrir con los ciclos en $2$ diferentes formas:

y

---

Similar pregunta fue hecha en un concurso hace un par de semanas y yo sólo era capaz de llegar con los siguientes pensamientos:

• la respuesta para n x m = m x n, por lo que puedo considerar sólo las cuadrículas donde $n \leq m$
• para todos 3xn las cuadrículas de la respuesta es $0$. Gracias a Calvin comentario ahora veo que este no es el caso. Ahora me pueden encontrar por lo menos 3 formas para cubrir 3x4 cuadrícula con los ciclos de
• para todos 2xn las cuadrículas de la respuesta es $fibonacci(n)$

Pero todavía soy incapaz de encontrar la solución para un caso general.

P. S. ciclos pueden ser no-convexo, ciclos anidados permitido.

Answer 1

No hay ninguna fórmula general para un $m\times n$ cuadrícula, pero no es un enfoque recursivo que permite calcular el número de $C(m,n)$ de diferentes maneras para cubrir la rejilla con ciclos simples para cualquier $m,n$.

Primera nota de que una vez que se ha cubierto la red, basta conocer las líneas horizontales, con el fin de determinar todos los ciclos. Así que usted puede asignar a cada uno cubriendo un $(n-1)$ tuplas de subconjuntos de $\{1,\dots,m\}$. Cada subconjunto indica que las líneas horizontales
son parte de los ciclos, la numeración de las posibles líneas horizontales de 1 a $m$, la de menor valor correspondiente a 1.

Voy a tratar de aprender cómo incluir gráficos en mis respuestas, por el momento Voy a utilizar los gráficos proporcionados por el OP. Para los dos diferentes que cubren de una cuadrícula de 2 x 4, tenemos los 3-tuplas $(\{1,2\},\emptyset,\{1,2\})$ y $(\{1,2\},\{1,2\},\{1,2\})$. A la cobertura de la 5x6 cuadrícula dada anteriormente, la correspondiente 5-tupla es $(\{1,5\},\{1,2,4,5\},\{1,2,3,5\},\{1,2,4,5\}, \{1,5\})$, mientras que si lo hacemos girar la rejilla de 90 grados, se obtiene una cobertura de un 6x5 cuadrícula con la correspondiente 4-tupla $(\{1,6\},\{1,2,3,4,5,6\},\{1,2,5,6\},\{1,6\})$.

Tenga en cuenta que debe haber un número par de líneas horizontales, ya que son parte de ciclos simples.

Para la validez de la elección de líneas horizontales $(X_1,X_2,\dots,X_{n-1})$ $m\times n$ cuadrícula, con $X_i\subset\{1,\dots,m\}$, no es exactamente un formulario para agregar líneas verticales con el fin de obtener ciclos simples que cubre la rejilla: Si un horizontel de la línea de $j\in X_k\cap X_{k+1}$, entonces no puede haber líneas verticales de $j-1$ $j$o de$j$$j+1$. Si el nombre de las restantes extremos cada vez más, con $c_1,\dots,c_k$, entonces usted debe conectar $c_1$$c_2$, $c_3$ $c_4$ y, en general,$c_{2i-1}$$c_{2i}$, con líneas verticales, que no se cruzan conectados a las líneas horizontales. Conectados a las líneas horizontales y las líneas verticales que cubren todos los puntos de $1,\dots,m$.

En particular, si queremos aplicar este algoritmo a un par $S_0,S_1\subset \{1,\dots,m\}$, luego podemos obtener una validez de dos columnas de cuadrícula, o puede ocurrir que no es posible. Por ejemplo, si $m=4$, luego $\{1,4\},\{2,3\}$ es una coincidencia válida, sino $\{1,2,3,4\},\{2,3\}$ es no, puesto que no se puede conecte $c_1=1$ $c_2=4$ sin que se cruzan las líneas horizontales en 2 y 3. Del mismo modo $\{2,3\},\{2,3\}$ no es una coincidencia, ya que no cubra el punto 1.

Esto nos da las condiciones necesarias en un $(n-1)$-tupla a ser una opción válida:

DEFINICIÓN:

Una $(m,n)$-cubrimiento es una $(n-1)$-tupla $(X_1,\dots,X_{n-1})$ de los subconjuntos $X_i\subset \{1,\dots,m\}$, tal que

• Cada una de las $X_i$ tiene un número par de elementos.

• Set$X_0:=\emptyset$$X_n:=\emptyset$. A continuación, $X_k,X_{k+1}$ debe ser una coincidencia válida para $k=0,\dots,n-1$.

Esta definición permite ahora a contar las diferentes formas de cubrir una $m\times n$ cuadrícula con cosas simples ciclos: Es el número de diferentes $(m,n)$-cubrimientos.

Ahora el índice de las diferentes opciones válidas de líneas horizontales en una columna. Por el momento no se $2^{m-1}$ opciones correspondiente al número de incluso los subconjuntos de a $\{1,\dots,m\}$, más adelante veremos que podemos eliminar algunos de ellos. Por ejemplo, si $m=2$ tenemos $S_0^{(2)}:=\emptyset$$S_1^{(2)}:= \{1,2\}$. Válido que los partidos se $(S_0,S_1)$, $(S_1,S_0)$ y $(S_1,S_1)$, es decir, todos menos $(S_0,S_0)$ (eliminamos el superíndice si $m$ está claro).

En el caso de $m=3$,$S_0=\emptyset, S_1=\{1,2\},S_2=\{2,3\}$$S_3=\{1,3\}$. La validez de los partidos se $(S_0,S_3)$, $(S_1,S_3)$, $(S_2,S_3)$ y su simétrica pares. Podemos codificar la validez de los partidos en una matriz (llamada de adyacencia de la matriz), $$A=\pmatrix{ 0&0&0&1\\ 0&0&0&1\\ 0&0&0&1\\ 1&1&1&0}.$$ Aquí $A_{i,j}=1$ si $(S_i,S_j)$ es una coincidencia válida, y 0 si no lo es no válido.

Para $m=4$ hemos $S_0=\emptyset, S_1=\{1,2\},S_2=\{2,3\}$, $S_3=\{3,4\}$, $S_4=\{1,4\}$ y $S_5=\{1,2,3,4\}$. La validez de los partidos están dadas por la matriz $$A=\pmatrix{ 0&0&0&0&1&1\\ 0&0&0&1&1&1\\ 0&0&0&0&1&0\\ 0&1&0&0&1&1\\ 1&1&1&1&0&1\\ 1&1&0&1&1&1}.$$

Tenga en cuenta que los conjuntos de $\{1,3\}$ $\{2,4\}$ solo pueden ser igualadas uno con el otro, y así pueden ser nunca parte válido de $(n-1)$-tupla, y pueden ser despedidos.

Una vez que se tiene la matriz de adyacencia, que usted puede utilizar para calcular los $C(m,n)$: $$C(m,n)=(A^n)(e_0))_0=(A^{n})_{0,0},$$ es decir, se aplica la $n$ los tiempos de la matriz $A$ a el vector columna $e_0$ (correspondiente a un conjunto vacío en $X_0$) y calcular el $0$'th entrada (correspondiente a la emptyset en $X_{n}$).

En el caso de $m=2$ se sabe que la matriz $$A=\pmatrix{0&1\\ 1&1}$$ corresponde a la secuencia de Fibonacci. En nuestro caso hemos empezar con $a_1=0$$a_2=1$, y obtener un $C(2,n)=a_n$.

En el caso de $m=3$ un sencillo cálculo muestra que $C(3,2n+1)=0$ y, desde $$A^{2n-1}=3^{n-1}\pmatrix{ 0&0&0&1\\ 0&0&0&1\\ 0&0&0&1\\ 1&1&1&0},$$ tenemos $C(3,2n)=3^{n-1}$.

${\bf{EDIT}}$: Una cubierta de una $m\times n$ cuadrícula se llama 2-factor de $P_m\times P_n$ o también abarca 2-regular subgrafo (que cubre todos los vértices: expansión, cada vértice tiene dos aristas: 2-regular, los bordes están contenidos en la red: subgrafo). En la tabla 3 de http://www.emis.de/journals/PIMB/070/n070p023.pdf el número de 2-factores que se dan para $2\le m\le 7$$2\le n\le 10$. En el mismo artículo el método de la matriz de adyacencia se explica, aunque el método para obtener estas matrices se parece más complicado que el método explicado anteriormente. El autor también da a la generación de funciones para las relaciones de recurrencia para$f_m(n):=C(m,n)$$m=2,\dots, 7$.

En https://oeis.org/A003693 la recursividad fórmula para $a(n)=C(4,n)$ se da: $$a(n) = 2a(n-1) + 7a(n-2) - 2a(n-3) - 3a(n-4) + (n-5)$$ para $n>5$, y los cinco primeros términos se $0,2,3,18,54$.

En https://oeis.org/A003776 la recursividad fórmula para $b(n)=C(5,2n)$ se da: $$b(n) = 24b(n-1) - 57b(n-2) + 26b(n-3),$$ para $n>3$, y $b(1)=C(5,2)=3$, $b(2)=C(5,4)=54$ y $b(3)=C(5,6)=1140$. Por otra parte, el autor de http://www.emis.de/journals/PIMB/070/n070p023.pdf dice que es fácil probar que $C(n,m)>0$ fib $m\cdot n$ es aún, por lo tanto $C(5,2n+1)=0$, para todos los $n$.

En https://oeis.org/A222202 los valores de $C(2n,2n)$, y en https://oeis.org/A222203 los valores de $C(n,n+1)$.