Juego de islas y teoría de grafos

Question

Estoy tratando de recrear una versión electrónica del juego que se muestra a continuación:

El juego es básicamente un gráfico conectado, con el número que representa los grados obligatorios de cada vértice. El jugador debe conectar todo el grafo sin perder de vista los grados de cada vértice.

Mi objetivo es generar el gráfico correcto, para que definitivamente haya una solución. Mi idea inicial es generar aleatoriamente una matriz de adyacencia y comprobar si la matriz es euleriana. ¿Existe un algoritmo/fórmula de este tipo?

Otro método sería generar un gráfico conectado, y luego simplemente contar el grado de cada vértice y presentarlo al usuario. Pero prefiero la primera opción de generar un gráfico euleriano desde el principio.

Tal vez incluso lo esté complicando demasiado. Estaré encantado de escuchar cualquier otra idea.

Answer 1

Por lo general, es crucial para los rompecabezas de este tipo tener una solución única . Así que yo aconsejaría generar un árbol de expansión aleatorio, derivar la instancia del problema y luego comprobar si esta es la única solución.

Yo empezaría a simplificar el gráfico primero. Aquí hay tres reglas que puedes aplicar en cualquier orden repetidamente

1. Si se tiene que el grado-límite es igual al grado del vértice en el gráfico, entonces todas las aristas incidentes tienen que pertenecen al árbol de expansión. Por lo tanto, se seleccionan estas aristas y se elimina el vértice. A continuación se resta del límite de grado de los vértices adyacentes 1.

2. Si tienes un vértice de grado 0, entonces puedes sacar este vértice y todas las aristas incidentes.

3. Si tienes que el grado-límite es mayor que el grado de algún vértice entonces no puede haber una solución.

Si aún te quedan vértices debes retroceder. Recomiendo empezar con un vértice con un grado de vértice pequeño en el gráfico restante. Luego prueba todas las posibilidades para seleccionar las aristas incidentes, y ve si puedes continuar con las reglas 1-3. De este modo, puedes retroceder con bastante facilidad a través de todas las soluciones. Mientras retrocedes, registra las aristas seleccionadas. Todavía tiene que comprobar cada vez que resolvió todos los vértices, si el gráfico inducido no contiene ciclos.

Answer 2

¿Por qué no construyes un árbol de expansión aleatorio en un gráfico de cuadrícula, y luego eliminar las aristas?