¿Cómo puedo contar el número de combinaciones de color en un conjunto de regiones?

Question

Primero, permítanme empezar diciendo como usted puede haber adivinado, esta es una tarea problema. Por lo tanto estoy buscando una respuesta a la pregunta. Estoy buscando ayuda en la forma de analizar (Mi libro de texto es horrible).

Tengo una cuadrícula de 9 plazas rodeadas de un círculo. Puedo utilizar tres colores para el color de cada región con ninguna región de tocar cualquier otra región con el mismo color (esquinas no cuentan). **`

Me preguntan para encontrar el número de posibles diferentes colorantes.

Dibujé un conjunto de nodos con líneas que conectan las regiones vecinas, pero todavía no tengo idea de cómo calcular el número de combinaciones.

También hice una conjetura de tres (que yo sé que está mal), ya que puede colorear las regiones una vez con los tres colores, a continuación, asignar a cada color a una diferente dos veces después de la primera para colorear.

No azul está en contacto con otras regiones azul, blanco no está en contacto con otras regiones blancas, de color rojo es el que toca cualquier otro rojo regiones.

Answer 1

No estoy seguro acerca de esto, tal vez no entiendo el problema, pero aquí va. Si el color de la región fuera de la rejilla, el 8 de las células externas de la rejilla debe ser de color alternativamente con B y C, y el uno en el centro, con A. por Lo tanto usted tiene dos posibles coloraciones. Lo mismo si el color de la región fuera de la B, o C. por Lo tanto el número total de colorantes sería de 6.

La actualización , de Hecho, hay más. Si el exterior de las células son de color B y C, entonces el uno en el centro puede ser Una, y ya sea B o C, por lo que hay 12 diferentes coloraciones de ahora.

Answer 2

Si bien es valiosa para atacar estos problemas "por la mano", aquí están algunas de las generalidades. La versión general de este problema se llama gráfico de colorear. (El gráfico de ser de color aquí es el grafo cuyos vértices son las regiones del diagrama donde hay una arista entre dos regiones, si son adyacentes.) Recuento de los colorantes es conocido por ser #P-duro, por lo que no es tan fácil de hacer en general. Para los pequeños gráficos hay una manera razonable para calcular el número de colorantes por cualquier número fijo de colores $n$ mediante la eliminación de la contracción de recurrencia para el polinomio cromático.

Answer 3

He encontrado que la manera más sencilla de atacar problemas como este es realmente por una escalera de enumeración. Empezar por la coloración de la región externa, luego de ver lo que los colores que las fuerzas o elimina; en este caso, significa que ninguno de los ocho exterior de las celdas de la cuadrícula se pueden compartir ese color. Ahora, elige otro no forzados célula (por ejemplo, la esquina superior izquierda de la cuadrícula) y ver cómo muchas maneras que usted puede color; en este caso tenemos dos diferentes colores que podemos usar, y lo que usamos, a continuación, las fuerzas de los colores en todo el exterior de las celdas de la cuadrícula, lo que nos deja con sólo una onu-obligó a color (la plaza central de la cuadrícula puede ser uno de los dos colores), etc. Mientras que esto es una especie de un gráfico para colorear problema, es realmente más cerca de un problema de satisfacción de restricciones en disfraz, y los métodos utilizados para la resolución de muchos de los populares de lápiz-y-papel puzzles como el Sudoku/Kakuro/Picross/etc. están muy estrechamente relacionadas con esta.