Breve Introducción a la Teoría de Grafos

Una vez vistas las diferencias entre las matemáticas continuas y las matemáticas discretas, nos vamos a ir adentrando en una rama perteneciente a esta última: Teoría de Grafos. En esta entrada encontraréis definiciones y conceptos básicos para iniciaros en este campo.

Antes que nada…¿Qué es un grafo?

Podríamos definir un grafo como un objeto o una herramienta matemática compuesta por dos tipos de elementos: vértices/nodos y aristas. Formalmente, se dice que los nodos son elementos de un conjunto, y las aristas representan subconjuntos (“relaciones”) entre estos elementos. Gráficamente se representan como puntos unidos por segmentos (o flechas). Presentan múltiples utilidades y su flexibilidad nos permite solucionar muchos problemas cotidianos. Además, tienen la ventaja de que, a pesar de tener una rama completa de las matemáticas dedicada a ellos (lo que denominamos Teoría de Grafos), sus conceptos más básicos son de una sencillez notable, y se pueden llegar a comprender con apenas un poco de “intuición matemática”.

Conceptos importantes

• Orden de un grafo: número de nodos de un grafo.
• Valencia/Grado de un vértice: número de aristas conectadas a él (que “salen” de él).
• Camino: sucesión de nodos que están conectados sin pasar dos veces por un mismo vértice.
• Ciclo: sucesión de nodos conectados en la que el nodo inicial es también el nodo final (en lenguaje cotidiano: un camino “cerrado”).
• Vértices adyacentes: vértices conectados por una arista.

Clasificación de grafos

Aunque podríamos distinguir los grafos según muchas características (grafos eulerianos, bipartitos, hamiltonianos, etc.), he aquí una pequeña selección de las clasificaciones más básicas y esenciales:

Grafos dirigidos/Digrafos (o no dirigidos)	Si sus aristas presentan sentido (indicado por una flecha) será un digrafo; si no presentan dirección (las aristas serán segmentos), se tratará de un grafo no dirigido.
Completos (o incompletos)	Si todos los nodos del grafo están unidos entre sí (todos con todos) será un grafo completo. Si se trata de un grafo dirigido completo todos los vértices estarán unidos en ambos sentidos.
Ponderados (o no ponderados)	Llamaremos grafo ponderado a aquel cuyas aristas tenga asociada una etiqueta con una información (p.ej: un valor, que se denomina peso, longitud o costo).

Fuentes de información recomendadas

A continuación incluiré una serie de lugares de gran utilidad para comenzar a aprender sobre grafos. El primero es un vídeo del canal de divulgación Derivando:

También encontraréis explicaciones detalladas en los siguientes enlaces de la Universidad de Granada y de la Universidad de Pamplona, respectivamente: Grafos (UGR) y Teoría de Grafos.