Coloración de un grafo

Universidad Autónoma de Aguascalientes

[pic 1]

Practica 3

Coloración de un grafo

Hugo David Pedroza Hernández | Optimización inteligente | 12 de octubre del 2018 | Dra. Aurora Torres Soto

Capturas de pantalla y explicación de consola

Primeramente, explicaremos el funcionamiento del programa ejecutado en consola

• [pic 2]
• Tomaremos en cuenta primeramente este grafo de grado 5 donde el vértice 1 es de grado 2, el vértice 2 es de grado 3, el vértice 3 es de grado 2, el vértice 4 es de grado 3 y asimismo el vértice 5 es de grado 4
  
• Al ejecutar nuestro programa nos despliega la siguiente pantalla
  
  [pic 3]
  
  Insertamos el grado de nuestro grafo, así como en el ejemplo insertaremos 5
  
  
• Para optimizar el numero de preguntas de las aristas que unen a los vértices, el programa opta por preguntar si el enésimo vértice cuenta con alguna otra arista (recibe como parámetro 1:SI, 0: No ):
  
  [pic 4]
  
• Por ejemplo, en nuestro grafo de ejemplo, el vértice 1 tiene conexión con el vértice 2 y el 5 entonces nos queda:
  
  [pic 5]
  
  y así sucesivamente vamos llenando nuestro grafo hasta realizar todas las conexiones
  
• [pic 6]
  
• Cuando terminemos de llenar las conexiones se dividirá las impresiones a pantalla en: Matriz de adyacencia, Grados de cada uno de los vértices, los vértices ordenados según su grado, el procedimiento de cada iteración de la función de coloreo, el vector coloreado y el numero cromático:
  
  
• Matriz adyacencia
  
  [pic 7]
  
• Grados de los vértices:
  
  [pic 8]
  
• Vértices ordenados según su grado:
  
  [pic 9]
  
• Procedimiento de cada interacción
  
  [pic 10]
  
• Coloreo y numero cromático:
  
  [pic 11]
  
  
• Ahora si coloreamos el grafo tomando en cuenta como
  
  Color 1: Rojo
  Color 2: Verde
  Color 3: Azul
  
  Nos queda:
  
  [pic 12]
  

Conclusiones

Este método va a ser de gran utilidad para la introducción a las heurísticas y entender cómo funcionan, como podemos optimizar una solución a partir de un planteamiento inicial a través de distintos métodos.

...