Teoría de grafos: problemas de práctica con soluciones paso a paso

1Vértices, aristas y grados

Un grafo consta de vértices (puntos) y aristas (líneas entre dos vértices). En un grafo simple no hay lazos ni aristas dobles.

El grado de un vértice es el número de aristas que inciden en él. Cada arista tiene dos extremos, así que suma 1 al grado de cada uno. Eso da el lema del apretón de manos:

Dos consecuencias: la suma de los grados es siempre par, y el número de vértices de grado impar también es par.

• El grafo completo K_n une cada par de vértices: n(n − 1)/2 aristas.
• El grafo bipartito completo K_m,n une cada vértice de un lado con cada vértice del otro: m·n aristas.
• Un grafo k-regular de n vértices tiene n·k/2 aristas.

La matriz de adyacencia tiene un 1 en (i, j) cuando i y j están unidos. En un grafo no dirigido es simétrica, la suma de una fila es un grado, y la entrada (i, j) de Mᴸ cuenta los recorridos de longitud L de i a j.

2Euler y Hamilton

Un circuito euleriano usa cada arista exactamente una vez y vuelve al inicio. Un camino euleriano usa cada arista una vez pero puede terminar en otro lugar. Para un grafo conexo:

• todos los grados pares: existe un circuito euleriano;
• exactamente dos grados impares: existe un camino euleriano, de un vértice impar al otro;
• más de dos grados impares: ninguno de los dos.

Un circuito hamiltoniano visita cada vértice exactamente una vez. No existe un criterio sencillo de grados para él. En K_n hay (n − 1)!/2 circuitos hamiltonianos distintos: se fija el inicio, se ordenan los otros n − 1 vértices y se divide entre 2 por los dos sentidos.

3Árboles

Un árbol es un grafo conexo sin ciclos. Todo árbol con n vértices tiene exactamente n − 1 aristas. Añadir cualquier arista crea un ciclo; quitar cualquier arista lo desconecta.

Un bosque de c árboles con n vértices tiene n − c aristas. Un grafo conexo con m aristas conserva un árbol generador tras quitarle m − n + 1 aristas.

El lema del apretón de manos cuenta las hojas: Σ gr = 2(n − 1). Una forma breve es L = 2 + Σ (d − 2) sobre los vértices de grado d ≥ 3. Un árbol con dos vértices de grado 3 y el resto hojas tiene 2 + 1 + 1 = 4 hojas.

4Dijkstra y árboles generadores mínimos

El algoritmo de Dijkstra halla las distancias más cortas desde un vértice inicial en un grafo con pesos no negativos.

1. Da al inicio la distancia 0 y a todos los demás vértices ∞.
2. Fija el vértice no fijado de menor distancia; su distancia ya es definitiva.
3. Para cada vecino v, actualiza d(v) = min(d(v), d(u) + w(u, v)).
4. Repite hasta que se fije el destino.

Un árbol generador mínimo conecta todos los vértices con el menor peso total. Kruskal ordena las aristas de la más ligera a la más pesada y toma cada una salvo que cierre un ciclo. Prim hace crecer un único árbol desde un vértice inicial, añadiendo siempre la arista más ligera que sale de él. Ambos se detienen tras n − 1 aristas.

5Errores frecuentes

• Olvidar dividir la suma de grados entre 2 para obtener el número de aristas.
• Comprobar si hay un circuito euleriano sin verificar que el grafo sea conexo.
• Fijar un vértice en Dijkstra antes de que tenga la menor distancia provisional.
• Tomar las n − 1 aristas más ligeras sin comprobar si forman ciclos.
• Contar los circuitos de Hamilton de K_n como n! en lugar de (n − 1)!/2.

6Cómo son las preguntas de examen

• Fácil: grados y aristas. Usas el lema del apretón de manos, cuentas las aristas de K_n, K_m,n, grafos regulares y árboles, lees una matriz de adyacencia o haces clic en el vértice con un grado dado.
• Medio: caminos eulerianos y árboles. Decides si un grafo tiene un circuito o un camino euleriano, cuentas las hojas de un árbol, cuentas las aristas que hay que quitar para obtener un árbol generador o cuentas los circuitos de Hamilton en K_n.
• Difícil: caminos mínimos y árboles generadores. Ejecutas el algoritmo de Dijkstra, hallas el vértice fijado en una ronda dada, hallas el peso de un árbol generador mínimo, haces clic en la arista que Kruskal o Prim añade a continuación o cuentas recorridos con la matriz de adyacencia.