El mundo dibujado con puntos y líneas: los grafos

Un punto es una cosa

Un grafo empieza con puntos.
Un punto es una cosa.
Una estación, una persona, una página web,
cualquier cosa puede ser un punto.
A cada punto le damos un nombre.
Así sabemos cuál es cuál.
Aún no hay líneas.
Solo puntos, dispersos.

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

Cuantos más puntos pusiste,
más cosas había.
Pero solo puntos
son motas dispersas.
Estaciones por separado
no son un mapa de rutas.
Falta cómo
se conectan los puntos entre sí.
Dibujemos esa conexión enseguida.

Una línea es una relación

Ahora unamos los puntos.
Juntar dos puntos con una línea
significa "estos dos están relacionados."
Hay un camino entre dos estaciones,
dos personas son amigas,
esta página web enlaza a aquella.
Una línea es una relación.
Puntos y líneas juntos hacen un grafo.

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

Cuantas más líneas dibujaste,
más se entretejieron los puntos.
Los puntos dispersos
por fin fueron un mapa de rutas.
Puntos son cosas, líneas son relaciones.
Con solo estos dos
puedes dibujar incontables cosas del mundo.
Y entre ellas se esconde una forma que conocemos.

Un árbol es un grafo especial

Un grafo puede formar un ciclo.
Empieza en el punto A,
sigue las líneas,
y si vuelves a A, eso es un ciclo.
Un grafo sin ningún ciclo,
eso es justamente un árbol.
Sin camino de vuelta,
solo ramificándose como ramas.
Así que un árbol es un tipo de grafo.

Toca la línea que forma el ciclo para cortarla. Quita el ciclo y se vuelve un árbol. árbol es parte de grafo.

Corta un ciclo
y el camino de vuelta desaparece.
El grafo que parecía enredado
se volvió un árbol limpio.
Las carpetas y árboles genealógicos que vimos antes
eran árboles justo así.
Un árbol es el caso especial de un grafo,
es decir, el grafo es el paraguas más grande.

Los grafos están en todas partes

Ponte las gafas de puntos y líneas
y el mundo se ve distinto.
Un metro es estaciones (puntos) y vías (líneas),
una red de amigos es personas (puntos) y amistad (líneas).
La web es páginas (puntos) y enlaces (líneas).
Cosas que parecen muy distintas
eran en realidad el mismo dibujo.
Así que resuelve uno
y el resto se resuelve también.

Toca para cambiar de ejemplo. Metro, red de amigos, web, todos los mismos puntos y líneas.

Aunque cambie el ejemplo,
el esqueleto del dibujo sigue igual.
Puntos son cosas, líneas son relaciones.
Solo cambian las etiquetas.
Justo por eso
los grafos son de veras útiles.
Con una sola herramienta
puedes dibujar incontables problemas del mundo.

Resumamos

Reunido en una línea, es esto.
Puntos son cosas, líneas son relaciones.
Un dibujo hecho con puntos y líneas es un grafo.
Un grafo especial sin ciclo es un árbol.
Metro, redes de amigos, la web,
todo se puede dibujar con puntos y líneas.
Ahora que los puntos y líneas están puestos,
queda una pregunta.
¿Cómo nos movemos entre estos puntos?

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

Ahora que sabes dibujar un grafo,
la diversión de verdad empieza aquí.
Cómo partir de un punto
y visitar cada punto por las líneas,
cómo encontrar el punto más cercano.
Eso se llama recorrido de grafos.
En la próxima lección, sigamos juntos
cómo recorremos los puntos y las líneas.