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, c + v - a = 2 (donde c es el número de caras, v es el número de vértices y a 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, e = 2,718281828\ldots 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 G = (V,\; A), donde V es un conjunto no vacío, llamado conjunto de vértices (o nodos), y A es un conjunto de parejas de vértices de V (de la forma (v,\; v')), llamado conjunto de aristas. En el ejemplo de los puentes de Königsberg, V = \{A,\; B,\; C,\; D \}, y A = \{(A,\; B),\; (A,\; B),\; (A,\; C),\; (B,\; C),\; (C,\; D) \}. 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.

NM es la persona que no lleva mascarilla, M es la persona que lleva mascarilla. La flecha representa la posibilidad de contagio de una persona a otra.

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

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 v y v' se puede escribir (v,\; v') o (v',\; v), 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 v,\; v', 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 \{v_{1},\; \ldots ,\; v_{n-1} \} de forma que existen las aristas (v,\; v_{1}),\; (v_{1},\; v_{2}),\; \ldots ,\; (v_{n-2},\; v_{n-1}),\; (v_{n-1},\; v'). Si este es el mínimo número de aristas, se dice que el camino tiene longitud n (hay n aristas). Ejemplo:

Obsérvese que v2 tiene una arista que le une consigo mismo, esto no es un problema.

Si para este grafo calculamos el camino mínimo que une v_{0} y v_{5}, obtenemos (v_{0},\; v_{1})(v_{1},\;v_{2})(v_{2},v_{5}), y tiene longitud 3 (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 v,\; v', 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:

Movemos el vértice v3 y evitamos el corte.

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.

Representa el mismo grafo que el cubo, porque sigue teniendo 8 vértices, 12 aristas y 6 caras, 5 son regiones cerradas y una es no acotada (lo que está fuera del cuadrado ABCD). Además es plano, porque no se corta ninguna arista. Con el resto de poliedros se puede hacer de la misma forma.

El Teorema de Euler dice lo siguiente: en un grafo plano, simple y conexo G, se cumple la fórmula c + v - a = 2. 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 G_{1} el grafo que tiene v_{1} = 2 vértices, a_{1} = 1 arista y c_{1} = 1 cara (todo el plano, es una región no acotada). Los vértices y la arista de G_{1} pertenecen a G. Aquí, la fórmula es c_{1} + v_{1} - a_{1} = 1 + 2 - 1 = 2. Se cumple (este es el caso base de la inducción). Nuestro propósito es construir el grafo G a partir de G_{1} añadiendo vértices y aristas de la siguiente manera: construimos G_{2} añadiendo una arista. Como G_{1} 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 G distinto de los que ya hay en G_{1}, así, G_{2} tiene v_{2} = 3 vértices, a_{2} = 2 aristas y c_{2} = 1 cara. Siguiendo con este proceso, vamos a construir los grafos G_{1},\; G_{2},\; \ldots ,\; G_{n},\; \ldots ,\; G. 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 n-1, también va a caer la ficha n). Así que supongamos que la fórmula es válida para el grafo G_{n-1}, que tiene v_{n-1} vértices, a_{n-1} aristas y c_{n-1} caras, es decir, c_{n-1} + v_{n-1} - a_{n-1} = 2. Tenemos que probar que también se cumple para el grafo G_{n}. Este grafo se construye añadiendo una arista a G_{n-1}, y pueden ocurrir dos cosas. Si la arista nueva (que sale de un vértice de G_{n-1}) llega a otro vértice de G_{n-1}, entonces el número de vértices es v_{n-1} (no hay vértices nuevos), el número de aristas es a_{n} = a_{n-1} + 1 (porque tenemos una arista nueva) y el número de caras es c_{n} = c_{n-1} + 1. 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, c_{n} + v_{n} - a_{n} = c_{n-1} + 1 + v_{n-1} - (a_{n-1} + 1) = c_{n-1} + v_{n-1} - a_{n-1} = 2. Ya solo falta ver el caso en el que la arista nueva va a un nuevo vértice. En este caso tenemos v_{n} = v_{n-1} + 1 vértices, a_{n} = a_{n-1} + 1 aristas y c_{n} = c_{n-1} caras. Ahora no cambia el número de caras. La razón es la misma que la que hemos expuesto para G_{2}. Por tanto, la fórmula es, utilizando que se cumple para el paso anterior, c_{n} + v_{n} - a_{n} = c_{n-1} + v_{n-1} + 1 - (a_{n-1} + 1) = c_{n-1} + v_{n-1} - a_{n-1} = 2. 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 G 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!

Autor: Enrique Ferres

Soy matemático por la Universidad Complutense de Madrid especializado en Ciencias de la Computación. Como divulgador soy miembro de Scenio y he impartido conferencias en la UCM para el proyecto La Conciencia Social es la Vacuna y en la UCJC. He sido mentor durante dos años en el proyecto PiMat de integración en la universidad y un año community manager del proyecto.

3 comentarios en “Sobre la fórmula c+v-a=2”

  1. Interesante artículo. Un solo punto: dice que las mascarillas no sirven para evitar el contagio de fuera adentro. Entonces, ¿por qué los sanitarios y la policía no hacen más que pedir que les den mascarillas? Se supone que no están contagiados, y que desean protegerse de posibles contagios como los del grafo del artículo. ¿Es que los sanitarios no saben de sanidad? Yo no haría mucho caso de lo que dice el Ministerio de Sanidad, que efectivamente afirma que “las de tipo quirúrgico, en personas sanas, no evitan el contagio”.

    Me gusta

    1. Supongo que si el Ministerio de Sanidad está en lo cierto, que era mi humilde suposición en ese ejemplo inocente, los sanitarios y la gente en general necesitan sentirse seguros bajo el efecto placebo. Otra opción puede ser que, como los síntomas no aparecen hasta varios días después del contagio, la mascarilla sirva para prevenir el contagio de los demás y así evitar una propagación descontrolada.

      Me gusta

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Salir /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Salir /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Salir /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Salir /  Cambiar )

Conectando a %s