Cómo colorear un mapa, de modo que un color cubra la máxima superficie.

Question

Dado un gráfico $G$ donde cada nodo se asemeja a un número. ¿Cómo se puede colorear este gráfico, de modo que no haya dos nodos conectados que tengan el mismo color y que un color tenga el máximo de área? El área se define por el número que hay dentro del nodo.

Para este problema de ejemplo encontré una solución de $22$ . Esto se consigue coloreando el número 8, el 5 inferior, el 3 superior, el 4 superior derecho y el 2 restante. Me gustaría saber si hay un buen método para encontrar este número sin usar el ensayo y error.

EDIT: Puedes usar tantos colores como quieras, así que el teorema de los cuatro colores no se aplica aquí.

Answer 1

Creo que he encontrado una solución al problema del ejemplo y un método decente para llegar a él. Copia del problema:

Primero decidí que no era necesario etiquetar todos con el mismo color. Sólo hay un color que nos interesa. Así que podemos etiquetar cada nodo con R (Rojo) u O (Otro).

Para el 8 tenemos dos opciones: R o O. Si lo coloreamos con O debe significar que tendríamos que colorear el 4, el 2 o el 3 con R. Porque si los cubriéramos todos con O, simplemente perderíamos los 8 puntos sin razón. Entonces, ¿cuál es la máxima cantidad de puntos que podemos obtener coloreando el 4, el 2 y el 3? Siete, por supuesto (coloreando el 4 y el 3). Pero 7 es menos que 8, así que habría que colorear el 8. Hay básicamente dos opciones:

8: R, 4: O, 2: O, 3: O --> esto resulta en una puntuación de 8.

8: O, 4: R, 2: O, 3: R --> resulta en una puntuación de 7 y además haces que otros 3 nodos (el 5, el 2 y el 3) sean O, por lo que no pueden aportar ningún punto.

Así que coloreo el 8 de rojo. Los 4, 2 y 3 deben ser de cualquier otro color.

No puedo levantar el 8, el 4, el 2 y el 3 del gráfico. Se han coloreado, así que ya no importan. Ahora podrías simplificar el problema a esto:

problema simplificado

Podrías volver a plantear el problema una vez más, pero en lugar de fijarte en el 8, puedes fijarte en el 5 inferior. De nuevo hay dos opciones:

5: R, 2: O, 3: O, 2: O --> resulta en una puntuación de 5.

5: O, 2: R, 3: O, 2: R --> resulta en una puntuación de 4 y cubre otros 4 nodos con O.

Así que coloreo el 5 de rojo y el 2, 3 y 2 deben ser de cualquier otro color.

rencia y repetición:

Gráfico más simplificado

Echa un vistazo a los dos de la izquierda.

Dos opciones:

El 2 más bajo: R, el 2 más alto: O --> resulta en una puntuación de 2.

El 2 más bajo: 0, el 2 más alto: R --> resulta en una puntuación de 2 y cubres el 4.

Tomar el más bajo 2. Simplificar.

Última versión simplificada

De aquí puedo ver que, para tomar la cantidad máxima, ahora necesito tomar el 3 y el 4 para obtener el máximo en este gráfico. Y en este punto hemos terminado. Tenemos un total de: 8 + 5 + 2 + 4 + 3 = 22.

NOTA: Este sudoku del gráfico no siempre funciona (al igual que no todas las posiciones iniciales de un sudoko tienen solución). Lo intenté por ejemplo con el mapa de los Estados Unidos: Me quedé atascado. El "algoritmo" que utilicé sigue siendo extremadamente engorroso y lleva mucho tiempo.