Estoy consultando en un proyecto de arte donde una pregunta acerca de los colores.
Considerar el color RGB como un gráfico.
- Los nodos están ordenados triples $(r, g, b)$ donde cada entrada es un número entero de $[0, 255]$.
- La distancia entre dos nodos $(r, g, b)$ $(r', g', b')$ se define a ser $|r - r'| + |g - g'| + |b - b'|$.
- Hay una arista entre dos nodos si y sólo si la distancia entre ellos es $1$.
Es fácil encontrar un camino Hamiltoniano en este gráfico - para un dibujo he utilizado el código Gris algoritmo presentado en la Pava de 1998 - , pero este se inicia en negro $(0, 0, 0)$ y termina en blanco $(255, 255, 255)$ , por lo que no es enfáticamente un ciclo.
Para lo que vale, hay $8$ nodos de la orden de $3$ y muchos ($387096 = 2 \cdot 3 \cdot 254 \cdot 254$) de los nodos de la orden de $5$ (cualquier triple que contiene exactamente una de $0$ o $255$), así que no hay camino Euleriano es posible.
Y es fácil construir un ciclo Hamiltoniano usando una variación en la Pava para $4$-tuplas, pero, por desgracia, los modelos de color sólo tiene tres componentes.
La experimentación me lleva a creer que un ciclo no existe para $3$-tuplas si te pones a trabajar en dos direcciones de negro, puede progresar, pero parece que se dejan atrás los nodos que usted no será capaz de alcanzar de nuevo - y mi intuición es que algún tipo de paridad argumento debería ser posible, pero una prueba real ha eludido a mí.
El mejor resultado sería la construcción de un ciclo Hamiltoniano para este gráfico. Casi tan buena como sería de un máximo de Hamilton subcycle. La existencia o inexistencia de la prueba sería estupendo también!
