Colorear, clicks y establos

Coloración gráfica

El problema de coloración del gráfico, para un gráfico G no dirigido, consiste en asignar un color a cada vértice para que no se atribuya el mismo color a dos vértices adyacentes.

Cuando el gráfico es plano, se reduce al problema de colorear un mapa geográfico. El problema de colorear un gráfico surge en muchas áreas prácticas, como la coincidencia de patrones, la planificación deportiva, el diseño de planos de asientos, la revisión de horarios, la planificación de taxis y la resolución de Sudoku.

El número mínimo de colores necesarios para colorear el gráfico G se denomina número cromático de G y se denota por X (G).

El problema de encontrar el número cromático de una gráfica es un problema Np-completo. El problema de colorear un gráfico con un número limitado de colores: ¿es posible colorear el gráfico con x colores? Si es así, ¿cómo? - también es un problema de Np-completo.

Un gráfico plano es como máximo 4 cromático.

Una cadena es como mucho 2-cromática.

Un ciclo es como mucho 3 cromático.

Una camarilla de tamaño n es n-cromática.

Ejemplo: un conjunto determinado de tareas debe asignarse a intervalos de tiempo, cada tarea requiere solo un intervalo. Las tareas se pueden programar en cualquier orden, pero los pares de tareas pueden entrar en conflicto en el sentido de que no se pueden asignar al mismo intervalo de tiempo, por ejemplo, porque ambos dependen de un recurso compartido. El gráfico correspondiente contiene un vértice para cada trabajo y una ventaja para cada par de trabajos en conflicto. El número cromático del gráfico es exactamente el mínimo requerido, el tiempo óptimo para completar todo el trabajo sin conflictos.

Problema: clics

Dado un gráfico G no dirigido, una camarilla es un subconjunto de vértices que están todos conectados en pares por aristas. En otras palabras, es un subgrafo completo.

Encuentra un clic w pedido k en una gráfica es un problema Np-completo.

El siguiente gráfico tiene una camarilla de orden 5:

hacer clic

Problema: estable

Dado un gráfico G no dirigido, un establo es un subconjunto de vértices que no están conectados en pares por aristas. Encontrar un establo de orden k equivale a encontrar una camarilla de orden k en la gráfica inversa, es decir que tiene una arista si no existe en la gráfica original, y viceversa.

Encuentra un establo Para de orden k en una gráfica es un problema Np-completo.

estable

Relación entre los tres problemas y la heurística

Tenemos las siguientes tres propuestas:

  • a (G) = w (no G)
  • w (G) = a (no G)
  • X (G)> = w (G)

Se dice que un S estable de G es máximo por inclusión si no hay un S 'estable de G tal que S esté estrictamente contenido en S'. Una camarilla K es máxima por inclusión si no hay camarillas K 'de G tales que K esté estrictamente contenido en K'.

Por esta definición, deducimos que un estable de orden máximo también es un estable máximo por inclusión, lo contrario no es cierto. La heurística clásica para obtener un establo grande es buscar un establo máximo por inclusión.

estable

El algoritmo de Brélaz es un algoritmo codicioso que permite conocer un límite máximo del número cromático de un gráfico. Su principio es simple y se desarrolla de forma iterativa.

Siempre que haya un vértice sin color, elegimos el vértice sin color con el mayor número de vecinos coloreados con diferentes colores. Luego, este vértice se colorea con el color más pequeño posible (los colores se ordenan en un orden ascendente arbitrario). Si todos los colores existentes ya son usados por un vecino, agregamos un nuevo color a nuestra paleta (agregando un color con un valor más alto que todos los demás existentes).

La noción de estable también puede proporcionar indicaciones sobre el color de un gráfico. De hecho, podemos suponer que en un establo, todos los vértices tienen el mismo color. Colorear en k colores equivale a encontrar una partición del conjunto de vértices estables en k.

El algoritmo de Welsh and Powell se basa en esta proposición:

  1. Ordena los vértices del gráfico en orden decreciente de grado
  2. Recorriendo la lista en orden, asigne un color no utilizado al primer vértice sin colorear pag, y asigne este color a cada vértice incoloro siguiente de modo que no sea adyacente al vértice pag.
  3. Regrese a 2 si hay vértices sin color en la lista. De lo contrario, devuelva la lista.

Ejemplo

sudoku gráfico para colorear

Pour voir la connexion entre le Sudoku et la coloration des graphes, nous allons d’abord décrire le graphe du Sudoku, que nous appellerons par commodité S. Le graphe S a 81 sommets, chaque sommet représentant une cellule. Lorsque deux cellules ne peuvent pas avoir le même nombre (soit parce qu’elles sont dans la même rangée, dans la même colonne, ou dans la même boîte), nous mettons une arête reliant les sommets correspondants du graphe Sudoku S.

Par exemple, puisque les cellules a3 et a7 sont dans la même rangée, il y a un arête joignant leurs sommets correspondants; il y a aussi un arête reliant a1 et b3 (ils sont dans la même case), et ainsi de suite. Chaque sommet du graphique Sudoku a un degré 20, et le graphique a un total de 810 arêtes. S est trop grand être pour dessiner, mais nous pouvons avoir une idée de la structure de S en regardant un dessin partiel. Le dessin montre les 81 sommets de S, mais seulement deux (a1 et e5) ont leur ensemble complet d’arêtes incidentes.

sudoku gráfico para colorear

El segundo paso para convertir un Sudoku en un problema de coloración de gráficos es asignar colores a los números del 1 al 9. Esta asignación es arbitraria y no es un orden de prioridad de colores como en el algoritmo.

sudoku gráfico para colorear

Una vez que tenemos el gráfico de Sudoku y una asignación de colores a los números del 1 al 9, cualquier Sudoku se puede describir mediante un gráfico de Sudoku donde algunos de los vértices ya están coloreados (los correspondientes a los datos). Para resolver el Sudoku, todo lo que tenemos que hacer es colorear el resto de los vértices usando los nueve colores.

sudoku gráfico para colorear

Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: