Información

¡Ahora tu también puedes ser un científico! ¿Te animas a participar en este pequeño desafío? ¡¡¡Sigue leyendo para adentrarte en el fantástico mundo de la CIENCIA!!! (tenemos premios y galletas :v)

Los fundamentos

Un grafo es una pareja ordenada G = (V, E) compuesto de un conjunto de vértices V y un conjunto de aristas E, donde cada arista es un par ordenado formado por dos vértices (u, v). Los grafos son usualmente representados dibujando un círculo por cada vértice v y una línea conectando cada par de vértices si hay una arista e entre ellos. Por ejemplo, el siguiente grafo:

  • V: {1, 2, 3, 4, 5, 6}
  • E: {
    • (1, 2)
    • (1, 5)
    • (2, 3)
    • (2, 5)
    • (3, 4)
    • (4, 5)
    • (4, 6)
    }
puede ser representado de la siguiente manera:

Un grafo sencillo compuesto de 6 vértices y 7 aristas
Un grafo sencillo con 6 vértices y 7 aristas

Los grafos son uno de los elementos más utilizados diversas áreas dada su versatilidad y flexibilidad para representar una gran variedad de conceptos.

El desafío

Uno de los problemas más famosos en el campo de las ciencias de la computación consiste en 'colorear' grafos: asignar a cada vértice de V una etiqueta (un color) de manera que no haya vértices adyacentes (es decir, unidos por una arista) que tengan el mismo color. Dicho coloreado recibe el nombre de coloreado propio.

Si un grafo G puede ser apropiadamente colorado con k colores, se dice que G es k-coloreable (o que G tiene un k-coloreado). Por ejemplo, nuestro grafo de ejemplo tiene un 6-coloreado:

Un grafo sencillo compuesto de 6 vértices y 7 aristas con un coloreado propio usando 6 colores
Un 6-coloreado propio

La k más pequeña para la cual un grafo G tiene un coloreado propio recibe el nombre de número cromático y se representa con la letra griega chi mayúscula Χ(G). Es decir, si k es el número cromático de un grafo G, entonces G no tiene l-coloreados propios para todos los enteros l < k. En el caso de nuestro grafo de ejemplo, el número cromático es 3: necesitamos un mínimo de 3 colores para colorear el grafo apropiadamente (o lo que es lo mismo, no es posible tener un coloreado válido con solo 2 colores).

Un grafo sencillo compuesto de 6 vértices y 7 aristas con un coloreado propio usando 3 colores
Un 3-coloreado propio usando el número cromático del grafo

El desafío que te proponemos es que realizes un programa que pueda resolver el problema del Coloreado de Grafos

Dado un grafo G = (V, E), halla el número cromático Χ(G).

Simple, ¿no? ¿Aceptas el desafío?

Las reglas

  1. Puede participar cualquier persona.
  2. Cada participante debe realizar un programa que calcule el número cromático de un grafo (véase las características del programa).
  3. Los códigos fuentes de los programas deben ser enviadon a la siguiente dirección de correo electrónico: jc.aguilar1308@gmail.com con el asunto "GRAN DESAFÍO DE LA CIENCIA 2016" (en mayúsculas, si no, no vale :v).
  4. Los programas pueden ser enviados desde la publicación de esta convocatoria y hasta las 10:00 AM del 26/mayo/2016. Prórroga: ¡Ahora tienes hasta las 23:59 (medianoche) del 26/mayo/2016 para participar!
    Actualización: La participación para el desafío se encuentra ahora cerrada. Sin embargo, ¡el premio más valioso que puedes obtener es el conocimiento! ¡Gracias a todos los que participaron!
  5. Ganador:
    1. El ganador será el primer participante que envíe el programa que pueda calcular correctamente el número cromático de TODOS los grafos de prueba.
    2. En caso que ningún programa participante pueda calcular correctamente el número cromático de TODOS los grafos de prueba, se declarará como ganador al participante cuyo programa haya utilizado la menor cantidad de colores de entre todos los participantes. En caso de que dos o más programas utilicen la misma cantidad de colores, ganará el programa que haya sido enviado primero.
    3. En ambos casos, la decisión del comité organizador es inapelable
  6. Premio:
    1. El premio para el programa que pueda calcular correctamente el número cromático de TODOS los grafos de prueba (ganador caso I) es de $500.00 MXN.
    2. El premio para el programa que utilice la menor cantidad de colores y que haya sido enviado primero (ganador caso II) es de $200.00 MXN.
  7. El ganador será anunciado durante la ceremonia de clausura de la Semana de Ingeniería 2016, donde se le hará entrega de el premio en efectivo y una constancia.
  8. Los casos no previstos en la presente convocatoria serán resueltos por el comité organizador.

Las características

El programa

  • Lenguajes aceptados: Java, Python, C o C++
  • Debe incluir en un comentario al principio del archivo el NOMBRE y CORREO ELECTRÓNICO del autor. Si estos datos no están completos (o si el comentario no está al principio del archivo) el programa será anulado.
  • Debe ser poder llamado desde la consola, especificando además, el nombre de un archivo de texto simple como argumento.
  • Como salida, debe imprimir el número de colores utilizados para colorear el grafo
  • Los programas cuyo tiempo de ejecución supere los 10 minutos serán automáticamente invalidados.

La entrada

Los grafos de entrada para el programa se encuentran en el formato estándar utilizado por el Centro de Matemáticas Discretas y Ciencia de la Computación Teórica (Center for Discrete Mathematics and Theoretical Computer Science, DIMACS) que puede ser encontrado en detalle haciendo click aquí.
A grandes rasgos, el formato tiene las siguientes características:

  • Los vértices del grafo están numerados desde 1,2, ... , n
  • Los archivos de entrada son uniformes y consistentes: cada identificador es válido, cada nodo está inequívocamente definido, exactamente m aristas son definidas, etc.
  • Cada línea del archivo comienza con un caracter que indica el contenido de la línea:
    • Comentarios: Estas líneas contienen información para los usuarios, y deben ser ignoradas por los programas. Pueden aparecer en cualquier lugar del archivo. Cada línea de comentario empieza con un caracter c minúscula.
    • Definición del problema: Solo existe una línea de este tipo en el archivo. Esta línea debe aparecer antes de cualquier descriptor de arista, y tiene el siguiente formato:
      p FORMAT NODES EDGES
      La letra p minúscula significa que es la línea de definición del problema. FORMAT es el tipo de formato utilizado en el desafío, en este caso siempre tomará el valor EDGE. El campo NODES contiene un valor entero especificando el número de vértices del grafo n. El campo EDGES contiene un valor entero especificando el número de aristas del grafo m.
    • Descriptor de arista: Hay un descriptor de arista por cada arista del grafo, cada una con el siguiente formato:
      e W V
      La letra e minúscula significa que es una línea descriptor de arista. Por cada arista (w, v) del grafo, los campos W V son enteros que especifican los componentes de la arista.
    La sección ejemplos muestra un ejemplo de grafo definido en el format DIMACS.
  • Los grafos se encuentran definidos en archivos de texto simples con la extensión '.col'
  • El programa será llamado sobre un conjunto de 18 grafos de prueba.
  • Los grafos de entrada serán suministrados al programa de uno en uno, especificando como argumento el nombre del archivo en donde se encuentra la definición del grafo. Por ejemplo: java gcoloring ejemplo.col
    llama al programa escrito en java gcoloring para decirle que coloree el grafo ubicado en el archivo ejemplo.col

La salida

  • Como salida, el programa debe mostrar un único valor: un entero indicando el número de colores que utilizó para colorear el grafo proporcionado.
  • Cualquier otra clase de salida, como mensajes, errores, o excepciones harán que se invalide el resultado.
  • Si durante la ejecución del programa ocurre cualquier clase de excepción, o si el resultado es invalidado por el punto anterior, el resultado para dicho grafo se considerará como 264.
  • La puntuación total del participante será la suma de los resultados individuales obtenidos al colorear cada grafo.

Los ejemplos

A continuación, se muestra la definición del grafo de ejemplo mostrado en la parte superior en el formato DIMACS. Esta definición también puede ser descargada haciendo click aquí.

c ejemplo.col
c
c Estas líneas son comentarios
c Tu programa debe ignorarlos
c
c Nuestro grafo de ejemplo tiene 6 vertices
c y 7 aristas
p EDGE 6 7
c Los comentarios pueden aparecer en cualquier parte
e 1 2
e 1 5
e 2 3
c Observa que no hay comas entre los descriptores de aristas
e 2 5
e 3 4
e 4 5
e 4 6
c Observa que también hay un descriptor de arista por cada arista del grafo

También puedes descargar uno de los grafos que serán usados como prueba para que te des una idea del desafío que tienes delante haciendo click aquí. ¡No te desanimes por su tamaño!

Las dudas

Cualquier duda o comentario que tengas acerca del desafío, puedes escribirme a mi dirección de correo electrónico jc.aguilar1308@gmail.com, o enviarme un tweet a mi cuenta @jose_knepa, con mucho gusto te ayudaré a resolverlas.

Para más información acerca del desafío, no te pierdas la plática "Rompiendo los Límites de la Intratabilidad" que un servidor impartirá este jueves 26 de mayo a las 9:00 AM, en el marco de las actividades de la Semana de Ingeniería 2016. ¡Ahí tendrás la respuesta a esta y a muchas más incógnitas!

Actualización: Puedes descargar la presentación utilizada en la plática haciendo click en este enlace.

¡Buena suerte a todos! Y que el viento sople a su favor