Árboles y caminos

Conexidad y caminos

Un camino en un grafo es una secuencia de vértices $v_0, v_1, \ldots, v_k$ tal que $\{v_{i-1}, v_i\}$ es una arista para cada $i$ y todos los vértices son distintos. La longitud del camino es el número de aristas $k$.

Un ciclo es una secuencia de vértices $v_0, v_1, \ldots, v_k = v_0$ con $k \ge 3$, todos distintos salvo el primero y el último, y donde cada par consecutivo está unido por una arista.

Un grafo es conexo si para todo par de vértices $u, v$ existe un camino de $u$ a $v$. Un grafo no conexo se divide en componentes conexas, cada una es un subgrafo conexo maximal.

Definición y caracterización de árbol

Un árbol es un grafo conexo sin ciclos. Esta definición concisa esconde varias propiedades equivalentes que son convenientes conocer para competencia:

Las siguientes afirmaciones son equivalentes para un grafo $G$ con $n$ vértices:

(i) $G$ es un árbol (conexo y acíclico). (ii) $G$ es conexo y tiene exactamente $n-1$ aristas. (iii) $G$ es acíclico y tiene exactamente $n-1$ aristas. (iv) Todo par de vértices está unido por exactamente un camino simple.

La equivalencia más útil en olimpiadas es la (ii): **un árbol con $n$ vértices tiene $n-1$ aristas**.

Prueba: árbol con $n$ vértices tiene $n-1$ aristas

Procedemos por inducción sobre $n$. Para $n = 1$: el único grafo conexo y acíclico en un vértice tiene 0 aristas, y $1 - 1 = 0$. Correcto.

Supongamos que todo árbol con $n-1$ vértices tiene $n-2$ aristas ($n \ge 2$). Sea $T$ un árbol con $n$ vértices. Afirmamos que $T$ tiene al menos una hoja (vértice de grado 1).

En efecto, si todos los vértices tuviesen grado $\ge 2$, podríamos construir un camino que nunca se repite indefinidamente: al llegar a cualquier vértice podemos salir por una arista distinta a la de entrada; como $V$ es finito, el camino eventualmente revisita un vértice, formando un ciclo, contradiciendo que $T$ es acíclico.

Sea $v$ una hoja de $T$. El grafo $T - v$ (obtenido eliminando $v$ y su única arista) sigue siendo conexo y acíclico, es decir, es un árbol con $n-1$ vértices. Por hipótesis inductiva, tiene $(n-1)-1 = n-2$ aristas. Sumando la arista eliminada: $T$ tiene $n-1$ aristas.

Circuitos eulerianos: el problema de los puentes de Königsberg

Un circuito euleriano en un grafo es un circuito (camino cerrado) que recorre cada arista exactamente una vez. La pregunta de cuándo existe un circuito así fue respondida por Euler en 1736, estudiando los puentes de Königsberg.

Teorema de Euler: Un grafo conexo tiene un circuito euleriano si y solo si todo vértice tiene grado par.

La necesidad es fácil: en un circuito euleriano, cada vez que el recorrido pasa por un vértice usa una arista para entrar y otra para salir, contribuyendo 2 al grado. Como cada arista se usa exactamente una vez, el grado de cada vértice es el número de veces que el circuito pasa por él multiplicado por 2, que es par.

Corolario: un grafo conexo tiene un camino euleriano (que recorre cada arista exactamente una vez pero no necesariamente cierra) si y solo si tiene exactamente dos vértices de grado impar; el camino comienza en uno y termina en el otro.

Bosques y componentes

Un bosque es un grafo acíclico (no necesariamente conexo). Cada componente conexa de un bosque es un árbol. Si un bosque tiene $n$ vértices y $k$ componentes conexas, entonces tiene exactamente $n - k$ aristas.

Esta fórmula generaliza la de los árboles: si $k = 1$ (conexo), recuperamos $n - 1$ aristas.

Aplicación en conteo: si un grafo tiene $n$ vértices, $m$ aristas y es acíclico, el número de componentes conexas es $n - m$. Este dato se usa para verificar si un conjunto de aristas forma un árbol o bosque.