Principios Esenciales de la Teoría de Grafos: Apareamientos, Planaridad y Coloración

Introducción a los Grafos Bipartidos y Planos

En la teoría de grafos, existen conceptos fundamentales que nos permiten entender la estructura y las propiedades de diversas redes. A continuación, exploraremos definiciones clave relacionadas con los apareamientos, la planaridad y la coloración de grafos.

Condición de Diversidad para Apareamientos

Si G = (V, E) es un grafo bipartido con V = V' ∪ V'', G tiene un apareamiento de V' a V'' si y solo si k vértices en V' (donde k = 1, 2, ..., |V'|) son adyacentes con al menos k vértices en V'' (es decir, hay al menos k vértices en V'' adyacentes con alguno de los k vértices de V').

Condición Suficiente de Apareamiento

Si G = (V, E) es un grafo bipartido con V = V' ∪ V'' y existe t > 0 tal que:

1. Cada vértice de V' tiene al menos t aristas incidentes.
2. Cada vértice en V'' tiene a lo más t aristas incidentes.

Entonces, existe un apareamiento de V' a V''.

Grafo Bipartido Completo (K_n,m)

Se denota por K_n,m al grafo bipartido completo con n y m vértices, que contiene todas las aristas posibles entre los dos conjuntos de vértices.

Cruces en Grafos

Se llama cruce de un grafo a una intersección de aristas que no es un vértice.

Grafos Planos y No Planos

Un grafo plano es un grafo que puede dibujarse en el plano sin cruces. En caso contrario, se dice que el grafo es no plano. El grafo completo pentagonal (K₅) y el grafo bipartido completo (K_3,3) son ejemplos de grafos no planos.

Propiedades de los Grafos Planos

Fórmula de Euler para Grafos Planares

Si G es un (n,m)-grafo poligonal con k caras, entonces n - m + k = 2.

También existe una relación entre el número de vértices (n) de un grafo plano (G) y el número de aristas (E).

Corolario: Relación entre Vértices y Aristas en Grafos Planos

Si G es un grafo plano con n vértices (donde n ≥ 3) y con E aristas, entonces E ≤ 3n - 6.

Demostración

En efecto, supongamos que G es plano y que todas sus caras, digamos R, son triángulos. Como cada arista es borde de dos caras, 3R = 2E. Por la Fórmula de Euler, n - E + R = 2. Multiplicando por 3, obtenemos 3n - 3E + 3R = 6. Sustituyendo 3R = 2E, tenemos 3n - 3E + 2E = 6, lo que simplifica a 3n - E = 6. Como todo grafo plano puede convertirse en triangular añadiendo aristas, se deduce que E ≤ 3n - 6. ■

Grafos Duales y Coloración

Grafo Dual de un Grafo Poligonal

Se llama grafo dual de un grafo poligonal G al grafo construido del siguiente modo: A cada cara F_i de G le asignamos un vértice f_i en el grafo dual. Y a cada arista que sea común entre dos caras F_i y F_j en G, le asignamos una arista {f_i, f_j} en el dual. Es, por tanto, otro grafo poligonal. Si un grafo coincide con su dual, se dice que es autodual.

Teorema de los Cuatro Colores (Appel-Haken, 1976)

Todo grafo poligonal puede ser coloreado con a lo sumo 4 colores distintos, de modo que ningún par de caras adyacentes (incluida la infinita) tengan el mismo color.

La necesidad de 4 colores se prueba fácilmente considerando el grafo completo de 4 vértices (K₄). En grafos sencillos, no es necesario usar ningún algoritmo; basta con el sentido común a la hora de colorear de la forma deseada.

Coloración Propia y Número Cromático

También se puede colorear un grafo de forma que vértices adyacentes tengan colores distintos, obteniéndose una coloración propia del grafo. Se llama número cromático de G, denotado por χ(G), al número mínimo de colores necesarios para obtener una coloración propia de G. Para colorear algunos grafos no planos se necesitan más de 4 colores. En general, el cálculo de χ(G) es complicado.