Introducción a grafos: vértices, aristas

Una idea que aparece en todas partes

Imagina cinco ciudades conectadas por carreteras. ¿Cuántas formas hay de ir de la ciudad $A$ a la ciudad $E$ sin repetir ciudad? ¿Existe una ruta que pase por todas las ciudades exactamente una vez? ¿Y una que recorra todas las carreteras exactamente una vez?

Estas tres preguntas suenan muy distintas, pero se responden con la misma herramienta: un grafo. Los grafos son el lenguaje que usan matemáticos, informáticos y olimpiadores para modelar conexiones. En la ONEM regional aparecen en problemas de conteo de caminos, coloraciones y circuitos.

Definición formal

Un grafo $G = (V, E)$ consta de un conjunto finito $V$ de vértices y un conjunto $E$ de aristas, donde cada arista es un par no ordenado $\{u, v\}$ con $u, v \in V$ y $u \ne v$.

Decimos que la arista $\{u, v\}$ une a $u$ con $v$, y que $u$ y $v$ son adyacentes (o vecinos). El número de vértices $|V|$ es el orden del grafo y el número de aristas $|E|$ es su tamaño.

En un grafo simple no hay aristas repetidas ni lazos ($\{v,v\}$). La mayoría de los problemas de olimpiada trabajan con grafos simples; cuando se permiten aristas múltiples entre el mismo par, se habla de multigrafo.

Grado de un vértice

El grado de un vértice $v$, escrito $\deg(v)$, es el número de aristas que inciden en $v$, es decir, el número de vecinos de $v$.

Ejemplo: en el grafo completo $K_4$ (cuatro vértices, cada par unido por una arista) cada vértice tiene grado 3, y hay $\binom{4}{2} = 6$ aristas.

Un vértice de grado 0 se llama vértice aislado. Un vértice de grado 1 se llama hoja (o colgante). Estos nombres aparecen con frecuencia en problemas sobre árboles.

El lema del apretón de manos

Sea $G = (V, E)$ un grafo. Entonces:

$$\sum_{v \in V} \deg(v) = 2|E|$$

Demostración: cada arista $\{u,v\}$ contribuye exactamente 1 al grado de $u$ y exactamente 1 al grado de $v$, esto es, contribuye 2 en total a la suma de grados. Sumando sobre todas las $|E|$ aristas obtenemos $2|E|$.

Este lema tiene una consecuencia fundamental: la suma de los grados es siempre par, luego el número de vértices de grado impar es par. En otras palabras, en todo grafo existe un número par de vértices de grado impar (posiblemente cero).

Aplicación directa: si en un grupo de personas cada una conoce a un número impar de las demás, el número total de personas debe ser par.

Tipos especiales de grafos

Los siguientes grafos tienen nombres propios y aparecen con frecuencia en problemas:

**Grafo completo $K_n$:** $n$ vértices, toda pareja de vértices está unida por una arista. Tiene $\binom{n}{2}$ aristas y cada vértice tiene grado $n-1$.

Grafo bipartito: el conjunto de vértices se divide en dos partes $A$ y $B$, y las aristas solo van de $A$ a $B$ (no hay aristas dentro de $A$ ni dentro de $B$). Un grafo bipartito completo $K_{m,n}$ tiene $m \cdot n$ aristas.

**Ciclo $C_n$:** $n$ vértices dispuestos en círculo, cada uno conectado solo a sus dos vecinos. Todo vértice tiene grado 2 y hay $n$ aristas.

**Camino $P_n$:** $n$ vértices en fila, cada uno conectado al siguiente. Los dos extremos tienen grado 1 y los demás grado 2. Tiene $n-1$ aristas.