Teoría de grafos
Puntos y líneas entre ellos: eso es todo lo que es un grafo. Sin embargo, el mismo dibujo describe un mapa de carreteras, una red de amigos, una molécula e internet, y las preguntas que se le pueden hacer, desde cuántos colores necesita hasta si se puede recorrer de un solo trazo, mantienen ocupados a los matemáticos desde 1736.
Vértices y aristas
Un grafo tiene vértices, también llamados nodos, y aristas, cada una de las cuales une dos vértices. No importa dónde se dibujen los vértices, solo qué pares están unidos, así que el mismo grafo puede verse muy distinto sobre el papel. Los grafos del laboratorio son simples: ninguna arista va de un vértice a sí mismo y entre dos vértices hay como mucho una arista. Con n vértices puede haber como mucho n(n − 1) / 2 aristas; un grafo que las tiene todas se llama completo, y K5 es el grafo completo de cinco vértices.
Grados y el lema del apretón de manos
El grado de un vértice es el número de aristas que llegan a él. Si sumas todos los grados obtienes exactamente el doble del número de aristas, porque cada arista tiene dos extremos y se cuenta una vez en cada uno. Es el lema del apretón de manos: en cualquier grupo, los apretones de manos contados persona por persona suman el doble del número de apretones. También significa que el número de vértices de grado impar siempre es par. Un grafo en el que todos los vértices tienen el mismo grado k se llama k-regular.
Grafos conexos, árboles y ciclos
Un grafo es conexo cuando se puede ir de cualquier vértice a cualquier otro siguiendo las aristas; si no, se divide en partes llamadas componentes. Un ciclo es un viaje de ida y vuelta que regresa a su inicio sin pasar dos veces por el mismo vértice, y la longitud del más corto es la cintura. Un grafo conexo sin ciclos es un árbol, y un árbol con n vértices siempre tiene exactamente n − 1 aristas: con una menos se divide, con una más tiene un ciclo. Todo grafo conexo contiene un árbol generador, un árbol que llega a todos los vértices usando solo algunas de las aristas.
Grafos bipartitos y coloración
Colorea los vértices de modo que ninguna arista una dos vértices del mismo color. La menor cantidad de colores con la que se consigue es el número cromático. Un solo color basta únicamente si no hay aristas. Dos colores bastan exactamente cuando el grafo es bipartito: sus vértices se dividen en dos lados y todas las aristas van de uno al otro. Dénes Kőnig demostró en 1936 que esto equivale a no tener ciclos de longitud impar, porque un ciclo impar no puede alternar entre dos colores. Para tres colores o más no se conoce ninguna prueba tan sencilla: decidir si bastan tres colores es un problema NP-completo, así que los programas buscan, como hace el laboratorio.
Un ejemplo: el grafo de Petersen
Toma un pentágono A–B–C–D–E y una estrella de cinco puntas F–H–J–G–I dentro de él, y une cada esquina del pentágono con una punta de la estrella: A–F, B–G, C–H, D–I y E–J. Ese es el grafo de Petersen, con 10 vértices y 15 aristas. Todos los vértices tienen grado 3, así que los grados suman 30, el doble de 15. Su ciclo más corto tiene longitud 5, así que no tiene triángulos, pero el pentágono es un ciclo impar, así que no es bipartito y necesita 3 colores. Dos vértices cualesquiera están como mucho a 2 aristas de distancia, así que su diámetro es 2. Los diez grados son impares, así que no tiene recorrido euleriano, y no se puede dibujar sin cruces.
Caminos eulerianos y los puentes de Königsberg
La ciudad de Königsberg tenía siete puentes que unían cuatro zonas de tierra, y la gente se preguntaba si era posible cruzar cada puente exactamente una vez. En 1736 Leonhard Euler demostró que no, y así nació la teoría de grafos. Cada vez que un paseo pasa por una zona de tierra usa dos puentes, así que solo el inicio y el final pueden tener un número impar de ellos, y las cuatro zonas de Königsberg tenían un número impar. Un recorrido que usa cada arista una vez se llama hoy camino euleriano, o circuito euleriano cuando termina donde empezó. Carl Hierholzer demostró en 1873 que la condición también es suficiente: si todas las aristas están en una sola parte y como mucho dos grados son impares, el recorrido existe, y su método de ir encadenando viajes de ida y vuelta todavía sirve para encontrarlo.
Distancia, diámetro y complemento
La distancia entre dos vértices es el menor número de aristas de un camino entre ellos, y el diámetro es la mayor distancia del grafo; en un grafo no conexo es infinito. Las redes sociales tienen diámetros pequeños, la idea detrás de los seis grados de separación. El complemento de un grafo tiene los mismos vértices y une exactamente los pares que no estaban unidos. De un grafo y su complemento, al menos uno siempre es conexo.
Explóralo
El laboratorio se abre con el grafo de Petersen coloreado en tres colores. Haz clic en Grados y comprueba el lema del apretón de manos, haz clic en Bipartito para ver un ciclo impar, y luego carga el cubo y observa cómo aparecen los dos lados. Carga la casa y haz clic en Recorrido euleriano para ver dónde tiene que empezar el trazo. Dibuja tu propio grafo y añade las aristas de una en una: observa cómo se acorta el ciclo más corto, cómo baja el diámetro y cómo sube el número cromático cuando entra la última arista de un K4.
Preguntas frecuentes
¿Qué diferencia hay entre un camino, un recorrido y un paseo?
Un paseo es cualquier sucesión de vértices unidos por aristas, y puede repetir ambos. Un recorrido puede repetir vértices pero no aristas, y por eso un recorrido euleriano puede pasar varias veces por el mismo vértice. Un camino no repite ni lo uno ni lo otro.
¿Qué es el teorema de los cuatro colores?
Dice que todo grafo que se puede dibujar sobre el papel sin que se crucen aristas se puede colorear con cuatro colores como mucho, así que ningún mapa necesita más de cuatro. Lo demostraron en 1976 Kenneth Appel y Wolfgang Haken con ayuda de un ordenador: fue el primer gran teorema demostrado así.
¿Qué es un ciclo hamiltoniano?
Un ciclo que visita cada vértice exactamente una vez, en lugar de cada arista. Se parece a la pregunta de Euler, pero no se conoce ninguna prueba sencilla: decidir si un grafo tiene uno es un problema NP-completo. El grafo de Petersen tiene un camino hamiltoniano, pero no un ciclo hamiltoniano.
¿Dónde se usa la teoría de grafos?
Los planificadores de rutas buscan en grafos de carreteras, los buscadores ordenan las páginas web por sus enlaces, los compiladores colorean grafos para repartir los registros del procesador, los horarios evitan coincidencias coloreando un grafo de conflictos, los químicos cuentan moléculas como grafos, y las redes de ordenadores, las redes eléctricas y las redes de amigos se estudian como grafos.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Abrir el laboratorio de teoría de grafos