La conjetura de Szymanski

Problema sin resolver en matemáticas

¿Puede cada permutación en el${\displaystyle n}$¿Se puede enrutar un grafo hipercubo doblemente dirigido de -dimensiones con caminos disjuntos en aristas ?

Más problemas sin resolver en matemáticas

En matemáticas, la conjetura de Szymanski , que lleva el nombre de Ted H. Szymanski, ^{[ 1 ]} afirma que toda permutación en el${\displaystyle n}$Un grafo hipercubo doblemente dirigido de dimensión puede ser enrutado con caminos disjuntos en aristas . Es decir, si la permutación${\displaystyle \sigma }$coincide con cada vértice${\displaystyle v}$a otro vértice${\displaystyle \sigma (v)}$, luego para cada${\displaystyle v}$Existe un camino en el grafo del hipercubo desde${\displaystyle v}$a${\displaystyle \sigma (v)}$de tal manera que no existan dos caminos para dos vértices diferentes${\displaystyle u}$y${\displaystyle v}$Utilice el mismo borde en la misma dirección.

Mediante experimentos informáticos se ha verificado que la conjetura es cierta para${\displaystyle n\leq 4}$. ^{[ 2 ]} Aunque la conjetura permanece abierta para${\displaystyle n\geq 5}$, en este caso existen permutaciones que requieren el uso de rutas que no son las más cortas para poder ser enrutadas. ^{[ 3 ]}

Aunque la conjetura completa sigue abierta, se han establecido varios resultados parciales. En particular, se ha demostrado que el hipercubo es 2-reordenable, lo que significa que cualquier permutación puede dividirse en dos permutaciones parciales, cada una de las cuales puede ser enrutada por caminos disjuntos en aristas. ^{[ 4 ]} Este resultado tiene aplicaciones en enfoques de tiempo compartido y redes ópticas con múltiples longitudes de onda, donde se puede lograr la duplicación virtual de aristas sin agregar conexiones físicas. El resultado de 2-reordenabilidad también proporciona un algoritmo de 2-aproximación para el problema de caminos disjuntos máximos en el hipercubo, que tiene aplicaciones en el control de admisión para redes de alta velocidad.

Un resultado relacionado muestra que cuando los vértices de origen y destino están separados por al menos dos niveles en el hipercubo (en términos del peso de Hamming ), existen dos colecciones disjuntas de aristas de caminos disjuntos de vértices que los conectan. ^{[ 5 ]} De manera más general, se ha conjeturado que si los vértices de origen y destino están separados por${\displaystyle r}$niveles, entonces${\displaystyle r}$Tales colecciones disjuntas por aristas deberían existir. ^{[ 5 ]}

La conjetura está estrechamente relacionada con la capacidad de enrutamiento por conmutación de circuitos de las redes, que se utiliza para admitir comunicaciones simultáneas a través de sistemas de telecomunicaciones y procesamiento paralelo multiprocesador. En el enrutamiento por conmutación de circuitos, se establece una ruta dedicada para cada par origen-destino, y los datos se transmiten en paralelo a través de dicha ruta. Si el hipercubo es reordenable (lo que significa que la conjetura de Szymanski es cierta), garantizaría que cualquier solicitud de enrutamiento por permutación pueda satisfacerse con rutas disjuntas en aristas, permitiendo la transferencia paralela de datos entre cada par origen-destino. ^{[ 4 ]}

La conjetura también tiene conexiones con la comprobación de propiedades , particularmente en el contexto de la comprobación de la monotonicidad de funciones booleanas sobre el dominio del hipercubo. ^{[ 5 ]} La comprensión de las propiedades de enrutamiento del hipercubo tiene implicaciones para el desarrollo de algoritmos eficientes para la comprobación de monotonicidad y problemas relacionados en la informática teórica.