Vértices, aristas, grados, caminos y ciclos.
La teoría de gráficas es el estudio de estructuras que sirven para modelar relaciones por pares entre objetos. Una gráfica $G = (V, E)$ consiste en un conjunto de vértices $V$ (puntos o nodos) y un conjunto de aristas $E$ (líneas que conectan pares de vértices). En las matemáticas de olimpiada, la teoría de gráficas te da un lenguaje muy potente para abstraer y resolver problemas combinatorios que involucran conexiones, como redes sociales, redes de transporte o transiciones de estados. Al traducir un problema a vértices y aristas, las restricciones complejas muchas veces se simplifican en propiedades estructurales como la conexidad o el ser bipartita.
Los bloques fundamentales para analizar gráficas son los grados, los caminos y los ciclos. El grado de un vértice es el número de aristas conectadas a él. Un camino es una secuencia de aristas distintas que conecta una secuencia de vértices, mientras que un ciclo es un camino que empieza y termina en el mismo vértice. Entender la relación entre el número de vértices, aristas y grados es crucial. Por ejemplo, el "Handshaking Lemma" relaciona las propiedades locales de los vértices (grados) con el conteo global de aristas, y te sirve como una herramienta principal para argumentos de paridad en problemas de nivel AIME.
Hay clases especiales de gráficas que aparecen seguido en las competencias. Los árboles son gráficas conexas sin ciclos, y representan la estructura de conexión mínima. Las gráficas bipartitas son gráficas donde puedes dividir los vértices en dos conjuntos ajenos de tal forma que cada arista conecte un vértice de un conjunto con uno del otro; estas son equivalentes a las gráficas que no tienen ciclos impares. Las gráficas completas ($K_n$) son aquellas donde cada par de vértices distintos está conectado por una arista única. Dominar estas estructuras específicas te permite aplicar fórmulas especializadas sobre el conteo de aristas y la transitabilidad.
1. El Handshaking Lemma (Fórmula de la Suma de Grados) Para cualquier gráfica $G = (V, E)$, la suma de los grados de los vértices es igual al doble del número de aristas: $$ \sum_{v \in V} \deg(v) = 2|E| $$ Corolario: En cualquier gráfica, el número de vértices con grado impar es par.
2. Propiedades de los Árboles Para un árbol $T$ con $n$ vértices y $e$ aristas, lo siguiente es equivalente:
3. Gráficas Completas ($K_n$) Una gráfica completa con $n$ vértices tiene el máximo número posible de aristas para una gráfica simple: $$ |E| = \binom{n}{2} = \frac{n(n-1)}{2} $$
4. Gráficas Bipartitas Una gráfica es bipartita si y solo si no contiene ciclos de longitud impar. Para una gráfica bipartita con particiones de tamaño $m$ y $n$, el máximo número de aristas es $mn$. Por el Teorema de Turán, una gráfica sin triángulos con $v$ vértices tiene a lo más $\lfloor v^2/4 \rfloor$ aristas (que es una gráfica bipartita completa).
5. Componentes Conexas Una gráfica con $n$ vértices y $k$ componentes conexas tiene al menos $n-k$ aristas. Para garantizar que una gráfica con $n$ vértices sea conexa, debe tener al menos $\binom{n-1}{2} + 1$ aristas.
Teorema: El Handshaking Lemma
Sea $G = (V, E)$ una gráfica finita no dirigida. Lo que hay que demostrar es que la suma de los grados de los vértices es igual al doble del número de aristas.
Demostración:
La idea es usar la técnica de doble conteo (contar la misma cantidad de dos formas distintas) sobre el conjunto de incidencias entre vértices y aristas. Define una incidencia como un par $(v, e)$ donde el vértice $v$ es un extremo de la arista $e$.
Paso 1: Contar por Vértices Considera la suma de los grados de todos los vértices: $$ S = \sum_{v \in V} \deg(v) $$ Por definición, $\deg(v)$ es el número de aristas incidentes al vértice $v$. Por lo tanto, la suma $S$ cuenta el número total de extremos de aristas en la gráfica.
Paso 2: Contar por Aristas Toma una arista arbitraria $e \in E$. Como $G$ es una gráfica no dirigida, cada arista conecta exactamente dos vértices (digamos, $u$ y $w$). Cuando calculas la suma $S$, la arista $e$ aporta exactamente $1$ al término $\deg(u)$ y exactamente $1$ al término $\deg(w)$. Por consecuencia, cada arista $e \in E$ se cuenta exactamente dos veces en la suma $S$.
Paso 3: Conclusión Como cada arista aporta exactamente 2 a la suma total de grados, la suma debe ser igual al doble del número total de aristas. $$ \sum_{v \in V} \deg(v) = 2|E| $$
Demostración del Corolario (El Teorema del Número Impar): Sea $V_{odd}$ el conjunto de vértices con grado impar y $V_{even}$ el conjunto de vértices con grado par. Puedes separar la suma: $$ \sum_{v \in V_{odd}} \deg(v) + \sum_{v \in V_{even}} \deg(v) = 2|E| $$ El lado derecho ($2|E|$) es un número par. El segundo término de la izquierda ($\sum_{v \in V_{even}} \deg(v)$) es una suma de enteros pares, así que tiene que ser par. Por lo tanto, el primer término $\sum_{v \in V_{odd}} \deg(v)$ también debe ser par. Para que una suma de enteros impares resulte en un número par, debe haber una cantidad par de términos. Así que $|V_{odd}|$ es par.
$\square$