Problema de Oberwolfach
¿ Para qué gráficos de 2 vértices regulares se puede descomponer el gráfico completo en copias disjuntas de aristas de ?
El problema de Oberwolfach es un problema no resuelto de matemáticas que puede formularse como un problema de programación de asignaciones de asientos para los comensales o, de manera más abstracta, como un problema de teoría de grafos , en las cubiertas de ciclo de borde de gráficos completos . Lleva el nombre del Instituto de Investigación Matemática de Oberwolfach , donde Gerhard Ringel planteó el problema en 1967 . [1]
En las conferencias celebradas en Oberwolfach, es costumbre que los participantes cenen juntos en una sala con mesas circulares, no todas del mismo tamaño, y con asientos asignados que reorganizan a los participantes de una comida a otra. El problema de Oberwolfach pregunta cómo hacer un plano de asientos para un conjunto dado de mesas de modo que todas las mesas estén llenas en cada comida y todos los pares de participantes de la conferencia se sienten uno al lado del otro exactamente una vez. Una instancia del problema se puede denotar como dónde están los tamaños de tabla dados. Alternativamente, cuando se repiten algunos tamaños de tablas, se pueden denotar usando notación exponencial; por ejemplo, describe una instancia con tres tablas de tamaño cinco. [1]
Formulado como un problema de teoría de grafos, los pares de personas sentadas una al lado de la otra en una misma comida pueden representarse como una unión disjunta de gráficas de ciclo de las longitudes especificadas, con un ciclo para cada una de las mesas de comedor. Esta unión de ciclos es un grafo de 2 regulares , y todo grafo de 2 regulares tiene esta forma. Si es este gráfico de 2 regulares y tiene vértices, la pregunta es si el gráfico completo se puede representar como una unión disjunta de bordes de copias de . [1]
