Hola

A

ntes de espantar a los posibles lectores de este artículo al mencionar la palabra "Matemáticas" recordemos que hay ramas de las Matemáticas, como la Matemática Discreta, que tienen aplicaciones directas en la vida cotidiana, constituyendo también parte de las bases de las ciencias de la computación.


¿Como podemos organizar el horario de proyección de las películas de un festival de cinede tal modo que aquellos interesados en distintos tipo de películas puedan asistir a todas ellas sin que las películas dentro del mismo tipo no se solapen? ¿Cuántos sudokus hay? ¿Cuántas maneras hay de colorear los países de mapa mundi? Vamos a ver que la Teoría de grafos trata de contestar a estas preguntas.


Muchos de estos problemas se pueden representar mediante un grafo. Un grafo sepuede dibujar como una serie de puntos, denominados vértices, unidos por líneas llamadas aristas. La forma del grafo no es importante, así como la longitud de las aristas, aunque se puede asociar un peso a cada una de ellas. En los programas informáticos los grafos se representan mediante matrices, de esta manera es mucho más fácil su manipulación y más sencillo el efectuar operaciones sobre ellos.A diferencia de la mayoría de teoremas clásicos de las Matemáticas, muchos de los algoritmos que resuelven de manera eficiente problemas implementados sobre grafos se descubrieron hace relativamente poco tiempo, en el pasado siglo. Así tenemos el algoritmos de Dijkstra (de 1959) que permite, por ejemplo, calcular el camino más corto entre dos ciudades sobre un mapa de carreteras, o el deKruskal (de 1957) que permite, por ejemplo, saber el trazado de líneas telefónicas que interconecten distintos usuarios al menor costo gracias a que halla el árbol recubridor de peso mínimo.


Hay otros problemas más clásicos como el de los puedes de Königsberg, ya analizado por Euler, que tuvieron solución hace tiempo gracias al algoritmo de Fleury. Este algoritmo nos permite, cuando es posible,resolver los típicos problemas de trazar un dibujo sin levantar el lápiz de papel y sin pasar más de una vez por el mismo sitio.


Pero hay otros problemas como el del viajante (que consiste en salir de la sede de la empresa y volver a ella visitando todas las ciudades una sola vez con el menor camino posible) que básicamente para el cual no hay un algoritmo que lo resuelva de manera eficiente.Aquí se entiende por "eficiente" el que sea resoluble en un tiempo polinómico. Es decir, que el tiempo de resolución en relación al tamaño del problema (en nuestro caso al número de vértices de nuestro grafo) crezca polinómicamente y no exponencialmente. Aunque hay muchos algoritmos que encuentran una buena aproximación al problema del viajante no existe ninguno que sea eficiente y que a la vez déla mejor solución posible. La única manera de encontrar la mejor solución consiste básicamente en enumerar todas las posibilidades y escoger la mejor, algo sumamente ineficiente. Se sospecha que algunos de estos problemas nunca tendrán una solución eficiente (problemas NP y NP completos).


Los problemas relativos a la organización de horarios en festivales de cine, a posibles sudokus o a mapasdel mundo se pueden intentar representar por grafos que tiene los vértices coloreados. En cada caso o problema los "colores" representan o simbolizan algo distinto y no necesariamente son literalmente colores.
En el ejemplo del mapa podemos asociar cada país a un vértice de un grafo y unirlos con una arista si tienen frontera en común. Dentro de las posibles coloraciones, las coloraciones propiasson las más interesantes y consisten en que los vértices unidos por una arista no tengan el mismo color. En nuestro ejemplo pintar dos países vecinos con el mismo color no es una buena idea si los queremos distinguir en el mapa.


Saber cuantas coloraciones propias distintas con "q" colores se pueden obtener o el mínimo número de colores (número cromático) para colorear propiamente un grafo...