Tome un papel y dibuje en él unos cuantos puntos gordos*. ¿Está ya? Ahora una cada uno de estos puntos con algunos otros de esos puntos. Bien, pues eso que tiene dibujado es un grafo.

Los matemáticos dicen que un grafo está formado por un conjunto de nodos (nuestros puntos gordos) y un conjunto de aristas (las rayas que unen pares de nodos). Cada nodo tiene que tener un nombre, para poderlos distinguir, así que escriba una letra junto a cada nodo: A, B, C… Las aristas no tienen nombre, porque no lo necesitan: cada arista se designa por los dos nodos que une; así, tenemos la arista AB, la arista EP y la arista RA.

En ese grafo que tiene dibujado puede (seguramente) llegar de un nodo hasta otro, recorriendo varias aristas. La secuencia de aristas que tiene que recorrer se llama camino. A veces, en algunos grafos, las aristas no son rayas, sino flechas; esto indica que esa arista sólo se puede recorrer en un sentido, y el grafo pasa a llamarse grafo dirigido. Un camino que empieza y termina en el mismo nodo sin pasar dos veces por la misma arista (típico pasatiempo) se llama circuito.

También a veces, cada arista tiene asociado un número, que indica un “peso” o un “valor” de la arista; el grafo que tiene estas aristas se llama grafo etiquetado, o grafo ponderado. Normalmente, la etiqueta de una arista tiene que ver con el “coste” que supone recorrer esa arista, o la “longitud” de la arista.

Los matemáticos han descubierto muchas propiedades interesantes de los grafos, y han inventado (o descubierto, que con estas cosas no se sabe muy bien…) unos algoritmos estupendos para hacer un montón de cosas con ellos. Ya que los grafos se dejan manejar tan bien, los informáticos abstraen muchas cosas y las tratan como si fueran grafos. Por ejemplo, suelen representar las “máquinas de estados” como grafos: cada nodo, un estado; cada arista, una transición entre estados.

Otro día les hablaré de mi algoritmo favorito, que está relacionado con los grafos, pero es que la historia de hoy ya me está quedando demasiado larga…

* Teorema del punto gordo: dos rectas paralelas sólo se unen en un punto gordo.