Qué es un grafo en informática

Los puntos son cosas

Un grafo empieza con puntos. Cada punto es una cosa: una estación, una persona, una página web, lo que sea.
A cada punto le ponemos un nombre para saber cuál es.
Todavía no hay líneas, solo puntos sueltos.

Toca un lugar vacío para colocar un punto. Cada punto es una cosa. (punto = nodo)

Cuantos más puntos colocas, más cosas hay. Pero solo con puntos, no son más que granitos dispersos.
Es como tener estaciones sueltas, que no forman un mapa del metro. Falta cómo se conectan los puntos entre sí.
Esas conexiones las trazamos a continuación.

Las líneas son relaciones

Ahora vamos a unir los puntos. Unir dos puntos con una línea significa «estos dos están relacionados».
Hay una vía entre dos estaciones, dos personas son amigas, esta página web enlaza a aquella. Cada línea es una relación.
Cuando se juntan puntos y líneas, se forma un grafo.

Toca un punto y luego otro, y aparece una línea. Cada línea es una relación. (línea = arista)

A medida que trazas líneas, los puntos se van entretejiendo, y los puntos sueltos por fin se convierten en un mapa del metro.
Los puntos son cosas; las líneas, relaciones. Solo con esto se pueden dibujar innumerables cosas del mundo.
Entre ellas se esconde una forma que ya conocemos.

Un árbol es un grafo especial

Un grafo puede tener ciclos. Si sales del punto A, sigues las líneas y vuelves a A, eso es un ciclo.
Un grafo sin ningún ciclo es justamente un árbol: una forma que solo se ramifica hacia fuera, sin camino de vuelta.
Así que un árbol es un tipo de grafo.

Toca la línea que cierra el ciclo para cortarla. Sin el ciclo, se convierte en un árbol. Árbol ⊂ grafo.

Al cortar un ciclo, desapareció el camino de vuelta, y el grafo que parecía enredado se convirtió en un árbol ordenado.
Las carpetas y los árboles genealógicos que vimos antes eran árboles justo así.
Un árbol es un caso especial de grafo; dicho de otro modo, el grafo es el paraguas más grande.

Los grafos están en todas partes

Con las gafas de puntos y líneas, el mundo se ve distinto.
El metro son estaciones (puntos) y recorridos (líneas); una red de amigos, personas (puntos) y amistades (líneas); la web, páginas (puntos) y enlaces (líneas).
Cosas que parecían totalmente distintas eran en realidad el mismo dibujo. Por eso, al resolver una, se resuelven también las demás.

Toca un ejemplo para cambiarlo. Metro, red de amigos, web: todos son los mismos puntos y líneas.

Al cambiar de ejemplo, el esqueleto del dibujo sigue igual: los puntos son cosas, las líneas son relaciones, y solo cambian las etiquetas.
Por eso mismo los grafos son tan útiles: con una sola herramienta se pueden dibujar innumerables problemas del mundo.

Resumen

En una línea: los puntos son cosas, las líneas son relaciones, y un dibujo hecho con puntos y líneas es un grafo. Un grafo especial sin ciclos es un árbol.
El metro, una red de amigos y la web se pueden dibujar con puntos y líneas.
Ahora que los puntos y las líneas están puestos, queda una sola pregunta: ¿cómo nos movemos entre estos puntos?

Toca los puntos clave en orden para repasarlos. (punto = cosa → línea = relación → grafo → un árbol es un grafo sin ciclos)

Ahora que sabes dibujar grafos, empieza lo divertido de verdad.
Salir de un punto y seguir las líneas para visitar todos los puntos se llama recorrido de grafos, y encontrar el camino más corto viene después.
En la próxima lección veremos cómo moverse por puntos y líneas.