Graph Theory. A lifestyle.

(ortografía corregida. Ustedes disculpen)
Siempre he creído que las matemáticas bonitas son aquellas que no necesitan de teoría demasiado desarrollada para poder entenderse y que sin embargo los problemas que puedan presentarse no sean triviales. Es decir, no es tan interesante decir "mira como mato moscas usando esta bazooka" como lo sería decir "mira como mato bazookas con esta mosca".

Generalmente, cuando a las personas que no estudian matemáticas les digo que lo que a mi me gusta es la Teoría de Gráficas, se imaginan que me la paso dibujando las gráficas de las funciones  que a uno le presentan en la prepa o haciendo estadística.

Aunque a muchos les cueste creerlo, la teoría de gráficas tiene una base mucho más sencilla que la definición de función. Tan sencilla que muchos problemas de teoría de gráficas se pueden traducir de manera que les parecen divertidos a los chicos de primaria y secundaria. El nacimiento de la teoría de gráficas se considera a partir del artículo de Euler sobre los 7 puentes de Köninsberg, el cual, fue escrito en 1736. Es decir, que la Teoría de Gráficas son matemáticas ya no tan jóvenes. Bueno, comparada con la Geometría Euclidiana aún anda en pañales, pero recordemos que las matemáticas estuvieron congeladas por mucho tiempo y fue hasta el siglo XVII que se volvieron a desarrollar de manera importante. Si lo vemos así, la Teoría de Gráficas ha existido durante 3 de las 4 siglos de la nueva era de las matemáticas.

La idea básica sobre una gráfica se remonta a nuestras primeras clase de dibujo en el kinder. Palitos y bolitas. Y eso es en esencia todo lo que se necesita saber. Una gráfica no es más que un montón de puntitos (bolitas), a los que llamamos vértices, y líneas (palitos) que unen a algunos de ellos a las que llamamos aristas. Por ejemplo:

Les sorprendería la cantidad inmensa de aplicaciones que esta idea tan básica tiene. Por ejemplo, podrían pensar que cada puntito es una persona y, si existe línea entre ellos, entonces esas personas se conocen. O podrían pensar que cada puntito es una computadora y las líneas significan "visibilidad" o conexión entre ellas. O que cada puntito es un país y las líneas representen si existe red de narcotráfico entre ellos. O que cada puntito es una página de internet y las líneas representan si puedes llegar a una desde la otra (en este caso para que tengan sentido  nuestras definiciones tendría que poderse llegar a una desde la otra, y desde la otra a la primera, pero también existen otras versiones de gráficas que representan mejor esta situación). O que cada puntito es una materia que quieran tomar y las líneas entre ellas signifique "lo siento cuate(a), estas materias son a la misma hora" (mal-chiste local). En lenguaje de matemáticas, podemos resumir que una gráfica es una relación simétrica definida en un conjunto finito (esto lo dije sin mucho formalismo, si algún conocedor está leyendo, por favor no me pegue).

Sus aplicaciones son la cosa más cotidiana del mundo y muy seguramente muchas veces ni nos enteramos en donde están metidas. Usando teoría de gráficas es que Google+ o Facebook (tal vez a este último no lo recuerden, pero fue bueno en su tiempo) te sugieren a tus amistades. Usando teoría de gráficas es que los semáforos inteligentes distribuyen el flujo del tráfico en las calles (obviamente esto es algo que no sucede en Morelia). Usando teoría de gráficas es que tu computadora se conecta a internet. Usando teoría de gráficas es que Google arroja resultados en cada búsqueda. Usando teoría de gráficas es que last.fm te sugiere música después de conocer un poquito tus gustos (y vaya que sugiere cosas buenas). Incluso, usando teoría de gráficas algunos controles de versiones pueden recuperar versiones antiguas de tus códigos. La Teoría de Gráficas también tiene su lugarcito en inteligencia artificial (¿Apoco no Google por sí solo les parece ya suficientemente inteligente con las respuestas que les ofrece en cada búsqueda?).

Posiblemente este estilo de comentarios en los que uno dice cosas como "ni siquiera te das cuenta de lo mucho que lo usas" se vuelven cada vez más comunes (incluso tal vez uno ni siquiera se da cuenta de lo mucho que lo dice). Lo que es aquí muy notable es la sencillez de la idea base. A diferencia de muchas otras matemáticas (álgebra, teoría de números, ecuaciones diferenciales, geometría... ) donde las ideas "básicas" requieren de una madurez matemática remarcable. Ideas tan fáciles de entender que muchos se han atrevido a decir que se trata de matemáticas de juguete. Sin embargo, tan fáciles de entender que las aplicaciones directas son prácticamente obvias. Es decir, si alguien te platica un problema de Teoría de Gráficas enmascarado de otra cosa, es fácil darse cuenta de que ver el problema como una gráfica sería útil.

A pesar de la sencillez de la definición de una gráfica, los problemas que se llegan a presentar son de talla grande. No he investigado mucho sobre problemas abiertos viejos, pero al menos puedo decirles que existe uno con más de 120 años (recuerden que el último teorema de Fermat tardó más de 200 años en resolverse y se considera que tomó mucho tiempo resolverlo). Lo increíble, es que los problemas generalmente son muy fáciles de entender (con un poco de paciencia en menos de una hora un niño de secundaria podría entender cual es el problema) aunque su solución no lo es tanto. Muchas veces, el ingenio necesario para resolver un buen problema de gráficas es asombroso (incluso se hace investigación sobre métodos que se han usado).

Además, la Teoría de Gráficas tiene lugar para cada tipo de matemáticos. Existen cosas que se pueden resolver después de haberse desayunado un diccionario de teoremas, y, también existen problemas donde la gente puede divertirse un muy buen rato atacándolos algorítmicamente (constructivamente).