Sobre la fórmula c+v-a=2

Bienvenidos al Escritorio de Enrique. Antes de nada, si queréis descargaros en pdf el contenido de esta entrada podéis pinchar en este enlace post6. En esta entrada vamos a utilizar la famosa Fórmula de Euler para poliedros, (donde es el número de caras, es el número de vértices y es el número de aristas), como motivación para conocer la Teoría de Grafos.

Leonard Euler es una de esas grandes figuras de las Matemáticas, los libros de texto de matemáticas y física de cientos de miles de estudiantes están llenos de teoremas, lemas y fórmulas con su nombre, ¡incluso una de las constantes más famosas de las matemáticas, se le debe a él! Nació en Suiza en 1707 y murió en 1783 en Rusia habiéndose mantenido en activo hasta el último día, a pesar de haberse quedado ciego sus últimos años. Durante unos años vivió en Prusia. Allí le llegó un problema que los habitantes de Königsberg (actual Kaliningrado) no lograban resolver. Königsberg era una ciudad que atravesaba el río Pregel. Para cruzar de un lugar a otro de la ciudad se habían construido 7 puentes, como se muestra en la imagen.

El problema consistía en encontrar un camino partiendo de cualquier lugar que recorriera todos los puentes y volviera al punto de partida pasando solo una vez por cada puente. Si quieres, tómate un momento para intentar encontrar un camino.

Euler consiguió resolver este problema, aunque quizás la respuesta no te agrade: es imposible tal camino. Para ello desarrolló una nueva área de las Matemáticas: la Teoría de Grafos. Lo primero en lo que se fijó Euler fue en que dan igual las distancias que hay que recorrer, al igual que da igual la disposición de los puentes mientras conecten las mismas áreas (A, B, C, D). Así, transformó esa representación en esta:

Lo importante son las áreas que tenemos en Königsberg y los puentes que las conectan. Esto es un grafo. Más concretamente, un grafo es un par de la forma , donde es un conjunto no vacío, llamado conjunto de vértices (o nodos), y es un conjunto de parejas de vértices de (de la forma ), llamado conjunto de aristas. En el ejemplo de los puentes de Königsberg, , y . Los grafos son una de las herramientas matemáticas más útiles en estos tiempos, pues sirven para modelizar problemas de muchísimas áreas: logística, informática, neurobiología… Para no sobresaturar de información esta entrada, no voy a explicar el procedimiento que utilizó Euler para el problema de los puentes, pero si te interesa, déjamelo en los comentarios y escribiré otra entrada dedicada a ello.

Hay grafos de muchos tipos. Las dos grandes clasificaciones de grafos son: dirigidos y no dirigidos. Un grafo dirigido es aquel en el que importa el sentido en el que se recorren los vértices. Un ejemplo, dos personas se encuentran por la calle, una lleva mascarilla y la otra no. Las mascarillas sirven para no contagiar a los demás, pero no para evitar contagiarte. Por tanto, el único contagio posible sería de la persona sin mascarilla a la persona con mascarilla, como representa el esquema de nuestro ejemplo.

Los grafos dirigidos se representan utilizando flechas, desde el vértice de salida, hasta el vértice de llegada . En este caso, la arista que los une se escribe .

Los grafos no dirigidos son aquellos grafos en los que simplemente interesa saber si dos vértices están conectados. No se habla de vértices de salida ni de llegada, y una arista que une los vértices y se puede escribir o , lo mismo da. El ejemplo de Königsberg nos sirve para ilustrarlo. Los planos de metro también son ejemplos de grafos no dirigidos. Las estaciones son los vértices, y las líneas de metro son las aristas que unen las estaciones.

De ahora en adelante, todos los grafos que vamos a considerar son no dirigidos. Dados dos vértices , se dice que hay un camino entre ellos (si el grafo es dirigido habría que decir «hay un camino del primer vértice al segundo», pero como he dicho más arriba, no voy a entrar más en ello) si podemos llegar de uno al otro recorriendo aristas del grafo. Más concreto, tendríamos que encontrar un conjunto de vértices de forma que existen las aristas . Si este es el mínimo número de aristas, se dice que el camino tiene longitud (hay aristas). Ejemplo:

Si para este grafo calculamos el camino mínimo que une y , obtenemos , y tiene longitud (aunque hay más caminos que unen estos vértices, este es el mínimo).

Un grafo se dice que es conexo si para todo par de vértices , existe un camino que los une. En el anterior ejemplo, el grafo es conexo. Además, un grafo se dice que es simple si hay como mucho una arista que une dos vértices y no hay bucles (es decir, aristas que van de un vértice a ese mismo vértice).

Vamos a entrar en el asunto que nos ocupa, la Fórmula de Euler. La definición clásica de poliedro es la de un cuerpo geométrico (tridimensional) cuyas caras son planas y encierran un volumen finito. Recordemos algunos ejemplos de poliedros: prisma, cubo, tetraedro, icosaedro. Vamos a tener en mente en lo que queda la imagen de un cubo, aunque teniendo en cuenta que lo que vamos a hacer es válido para cualquier poliedro (regular o no). Un cubo tiene 6 caras, todas ellas son cuadrados. Tiene 8 vértices y 12 aristas.

Un pequeño inciso. Hay grafos cuyas aristas se cortan al dibujarlos. Por ejemplo:

Sin embargo, podemos hacer lo siguiente:

Hay grafos que, nos pongamos como nos pongamos, no podemos evitar el corte de aristas, por ejemplo:

En general, decimos que un grafo es plano si puede dibujarse en el plano sin que ninguna arista se corte. Los poliedros son ejemplos de grafos planos, solo que tenemos que redefinir el concepto de «cara». Diremos que en un grafo plano, una cara es una región cerrada del plano delimitada por aristas, o una región no acotada del plano (esto se basa en un resultado muy fácil de entender pero complicado de demostrar. Se llama Teorema de la Curva Cerrada de Jordan, y dice que en el plano, una curva cerrada, por ejemplo una circunferencia, divide el plano en dos regiones disjuntas). Veamos por ejemplo cómo representar el cubo de antes en el plano sin que se corten sus aristas.

El Teorema de Euler dice lo siguiente: en un grafo plano, simple y conexo , se cumple la fórmula . Y, en efecto, los poliedros también son simples y conexos, por lo que la fórmula es válida para poliedros. La demostración es por inducción sobre el número de aristas y por construcción (esto es, vamos a construir el objeto que queremos). Consideremos el grafo que tiene vértices, arista y cara (todo el plano, es una región no acotada). Los vértices y la arista de pertenecen a . Aquí, la fórmula es . Se cumple (este es el caso base de la inducción). Nuestro propósito es construir el grafo a partir de añadiendo vértices y aristas de la siguiente manera: construimos añadiendo una arista. Como tiene solo dos vértices, la arista que añadimos no puede ir a ninguno de los vértices que ya hay, por lo tanto, tiene que ir a otro vértice de distinto de los que ya hay en , así, tiene vértices, aristas y cara. Siguiendo con este proceso, vamos a construir los grafos . Para asegurarnos de que siempre se cumple la fórmula tenemos que aplicar el paso inductivo (ya hemos tirado la primera ficha de dominó en el caso base, ahora tenemos que ver que si cae la ficha , también va a caer la ficha ). Así que supongamos que la fórmula es válida para el grafo , que tiene vértices, aristas y caras, es decir, . Tenemos que probar que también se cumple para el grafo . Este grafo se construye añadiendo una arista a , y pueden ocurrir dos cosas. Si la arista nueva (que sale de un vértice de ) llega a otro vértice de , entonces el número de vértices es (no hay vértices nuevos), el número de aristas es (porque tenemos una arista nueva) y el número de caras es . Ver que hay una cara más es más complicado, pero puedes imaginarlo, porque si hemos añadido una nueva arista que conecta dos vértices que ya estaban en el grafo es porque no había arista entre ellos y solo faltaba esa arista para «cerrar» una cara. Ponte el ejemplo del grafo plano del cubo y trata de construirlo paso a paso, ya verás cómo esto cobra sentido. La fórmula en este caso se sigue cumpliendo, utilizando que sabemos que se cumple en el paso anterior, . Ya solo falta ver el caso en el que la arista nueva va a un nuevo vértice. En este caso tenemos vértices, aristas y caras. Ahora no cambia el número de caras. La razón es la misma que la que hemos expuesto para . Por tanto, la fórmula es, utilizando que se cumple para el paso anterior, . Y con esto concluye la demostración por inducción, porque hemos visto que si tiramos la primera ficha y caen las fichas hasta un paso cualquiera, la siguiente ficha también cae. Además, hemos sabido construir el grafo paso a paso de forma que siempre se cumplía la fórmula.

Es una fórmula preciosa, elegante. El número de caras más el número de vértices menos el número de aristas siempre es el mismo, 2. Precioso. Es de esas fórmulas que desde que la vi en la escuela me apasionó. Para poder demostrarla hemos aprendido lo que son los grafos, hemos descubierto propiedades muy interesantes y hemos vislumbrado aplicaciones muy útiles. Aún así, todavía queda la sensación de que nos falta mucho por aprender. Si queréis que trate en otra entrada más cuestiones sobre grafos, dejádmelo en los comentarios. ¡Hasta la próxima!