20 votos

Trayectorias hamiltonianas cuyos vértices son particiones enteras

Llevo varios meses trabajando en este problema, pero no he avanzado mucho. Se trata del conjunto de todos los particiones de enteros de n.

Sean los vértices del grafo G=G(n) todas las particiones enteras p(n) de n. Hay una arista entre dos particiones si y sólo si una puede transformarse en otra con sólo mover un punto entre filas en sus representaciones del diagrama de Ferrers.

Así, por ejemplo, las particiones (3,2,1) y (3,3) de 6 están enlazadas porque podemos mover el punto de la última fila a la segunda fila.

OOO               OOO
OO      --------  OOO
O   

Mi pregunta: ¿para qué valores de n tiene G(n) un camino hamiltoniano de (n) a (1,1,...,1)?

Es decir, ¿es posible recorrer, sin repetición, todas las particiones de n simplemente desplazando los puntos en los diagramas de Ferrers?

¿Existe una forma determinada de construir estos caminos?

Sólo he podido construir trayectorias para n = 1 a 6.

n=1 (trivial)

n=2: (2) => (1,1)

n=3:
(3) => (2,1) => (1,1,1)

n=4:
(4) => (3,1) => (2,2) => (2,1,1) => (1,1,1,1)

n=5: (5) => (4,1) => (3,2) => (2,2,1) => (3,1,1) => (2,1,1,1) => (1,1,1,1,1)

n=6: (6) => (5,1) => (4,1,1) => (4,2) => (3,3) => (3,2,1) => (2,2,2) => (2,2,1,1) => (3,1,1,1) => (2,1,1,1,1) => (1,1,1,1,1,1)

Ninguno de los teoremas básicos sobre las trayectorias hamiltonianas me ha ayudado en este caso.

18voto

Robert Höglund Puntos 5572

Lo que quieres se conoce como código Gray para particiones enteras.

Existe.

Véase C. D. Savage, Secuencias de código gris de las particiones , Revista de algoritmos 10 (1989) 577-595. Descargo de responsabilidad: no he leído este artículo. Otras fuentes, como esta encuesta realizada en 1997 por Savage y estas notas de clase no dicen cuál es la construcción, sino que dicen que es complicada.

11voto

David Precious Puntos 4429

Hay dos grandes fuentes generales de códigos Gray sobre objetos combinatorios que podrían gustarte:

  1. Frank Ruskey " Generación combinatoria "Libro

  2. Don Knuth's "Art of Computer Programming", Vol. 4, Fascicle 2-4 (publicado por separado - todo excelente), véase https://www-cs-faculty.stanford.edu/~knuth/taocp.html

Las versiones preliminares de algunos de ellos pueden descargarse de la página archivo de internet .

4voto

andrei Puntos 1

Si te refieres a permitir que cualquier parte baje en 1 y cualquier parte (o 0) suba en 1, manteniendo el orden no creciente, entonces el artículo de Carla Savage de 1989 resuelve de hecho tu problema (sin requerir "movimientos dobles" como en la 10ª partición enumerada de 7 más arriba).

Existen refinamientos de esta operación en la literatura. Si sólo se permite que un punto "caiga" en una parte adyacente, es decir, de $(\ldots, p_i, p_{i+1}, \ldots)$ con $p_i \geq p_{i+1}+2$ a $(\ldots, p_i - 1, p_{i+1}+1, \ldots)$ que se denomina "operación de la pila de arena" o "regla vertical de Brylawski". Existe una regla horizontal de transposición, y restricciones de éstas denominadas $\theta$ y "pila de hielo", respectivamente. Para algunas de estas operaciones, el conjunto de particiones de $n$ no es un grafo conexo, y mucho menos uno con un camino hamiltoniano. En https://www-complexnetworks.lip6.fr/~latapy/Publis/tcs04a.pdf .

3voto

Rakesh Juyal Puntos 203

Parece haber un patrón general indicado por su $n=6$ ejemplo. He aquí una ruta para $n=7$ :

1.  7
2.  6 + 1
3.  5 + 2
4.  5 + 1 + 1
5.  4 + 1 + 1 + 1
6.  4 + 2 + 1
7.  4 + 3
8.  3 + 3 + 1
9.  3 + 2 + 2
10. 2 + 2 + 2 + 1
11. 3 + 2 + 1 + 1
12. 3 + 1 + 1 + 1 + 1
13. 2 + 2 + 1 + 1 + 1
14. 2 + 1 + 1 + 1 + 1 + 1
15. 1 + 1 + 1 + 1 + 1 + 1 + 1

He escrito esto para que sea obvio que las 15 particiones de 7 están contabilizadas. Observe la décima partición.

Aquí tiene uno para $n = 8$ :

1.  8
2.  7 + 1
3.  6 + 2
4.  6 + 1 + 1
5.  5 + 1 + 1 + 1
6.  5 + 2 + 1
7.  5 + 3
8.  4 + 4
9.  4 + 3 + 1
10. 4 + 2 + 2
11. 4 + 2 + 1 + 1
12. 4 + 1 + 1 + 1 + 1
13. 3 + 1 + 1 + 1 + 1 + 1
14. 3 + 2 + 1 + 1 + 1
15. 3 + 3 + 1 + 1
16. 3 + 2 + 2 + 1
17. 3 + 3 + 2
18. 2 + 2 + 2 + 2
19. 2 + 2 + 2 + 1 + 1
20. 2 + 2 + 1 + 1 + 1 + 1
21. 2 + 1 + 1 + 1 + 1 + 1 + 1
22. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

$n=9$ :

1.  9  
2.  8 + 1   
3.  7 + 2   
4.  7 + 1 + 1    
5.  6 + 1 + 1 + 1    
6.  6 + 2 + 1    
7.  6 + 3   
8.  5 + 4   
9.  5 + 3 + 1    
10. 5 + 2 + 2    
11. 5 + 2 + 1 + 1    
12. 5 + 1 + 1 + 1 + 1    
13. 4 + 1 + 1 + 1 + 1 + 1    
14. 4 + 2 + 1 + 1 + 1    
15. 4 + 2 + 2 + 1    
16. 4 + 3 + 1 + 1    
17. 4 + 4 + 1    
18. 4 + 3 + 2    
19. 3 + 3 + 3    
20. 3 + 3 + 2 + 1    
21. 3 + 2 + 2 + 2    
22. 2 + 2 + 2 + 2 + 1    
23. 3 + 2 + 2 + 1 + 1    
24. 3 + 3 + 1 + 1 + 1    
25. 3 + 2 + 1 + 1 + 1 + 1    
26. 2 + 2 + 2 + 1 + 1 + 1    
27. 3 + 1 + 1 + 1 + 1 + 1 + 1    
28. 2 + 2 + 1 + 1 + 1 + 1 + 1    
29. 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1   
30. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

0voto

Fly Puntos 46

Creo que tu problema está relacionado con la ordenación parcial dominante de las particiones; dadas las particiones $\alpha=(\alpha_1,\alpha_2,\dots)$ y $\beta=(\beta_1,\beta_2,\dots)$ de $n$ decimos que $\alpha$ domina $\beta$ y escribe $\alpha\succeq\beta$ si $\alpha_1\geq\beta_1$ , $\alpha_1+\alpha_2\geq\beta_1+\beta_2$ etc. Este orden parcial tiene un único elemento máximo $(n)$ y un único elemento mínimo $(1^n)$ . Ahora no es una orden total, pero dado $\alpha$ y $\beta$ existe una única partición mínima $\mu$ tal que $\mu\succeq\alpha$ y $\mu\succeq\beta$ . Asimismo, existe una única partición maximal $\nu$ tal que $\alpha\succeq\nu$ y $\beta\succeq\nu$ . Por último, la dominancia se genera mediante desplazamientos de una casilla, es decir, dada una partición $\alpha$ y $i<j$ tal que $\alpha_i>\alpha_{i+1}=\alpha_{i+2}=\dots=\alpha_{j-1}<\alpha_j$ consideremos la partición $\beta$ con $\beta_i=\alpha_i-1$ , $\beta_j=\alpha_j+1$ y $\beta_u=\alpha_u$ para $u\ne i,j$ . Entonces $\alpha\succeq\beta$ y no hay $\gamma\ne\alpha,\beta$ con $\alpha\succeq\gamma\succeq\beta$ . Además, para un par arbitrario $\alpha\succeq\beta$ podemos obtener de $\alpha$ a $\beta$ a través de una secuencia de tales desplazamientos de una casilla.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X