Método de descarga (matemáticas discretas)

El método de descarga es una técnica utilizada para demostrar lemas en la teoría estructural de grafos . ^{[ 1 ]} La descarga es especialmente conocida por su papel central en la demostración del teorema de los cuatro colores . El método de descarga se utiliza para demostrar que todo grafo de una clase determinada contiene algún subgrafo de una lista específica. La presencia del subgrafo deseado se utiliza a menudo para demostrar un resultado de coloración . ^{[ 1 ]}

La descarga se aplica generalmente a grafos planares . ^{[ 2 ]} Inicialmente, se asigna una carga a cada cara y a cada vértice del grafo. Las cargas se asignan de manera que su suma sea un número positivo pequeño. Durante la fase de descarga, la carga de cada cara o vértice puede redistribuirse a caras y vértices cercanos, según lo requiera un conjunto de reglas de descarga. Sin embargo, cada regla de descarga mantiene la suma de las cargas. Las reglas están diseñadas de manera que, después de la fase de descarga, cada cara o vértice con carga positiva se encuentre en uno de los subgrafos deseados. Dado que la suma de las cargas es positiva, alguna cara o vértice debe tener una carga positiva.

Un ejemplo conocido del método de descarga se encuentra en las demostraciones del teorema de los cuatro colores para grafos planares, donde se utilizó para obtener ciertas "configuraciones inevitables" cuya existencia impide que todos los grafos planares sean contraejemplos mínimos del teorema. ^{[ 2 ]} Un análisis de casos muy complejo y basado en computadora para este método, a partir de la demostración original de Kenneth Appel y Wolfgang Haken , ^{[ 3 ] [ 4 ]} fue simplificado posteriormente por Neil Robertson , Daniel P. Sanders , Paul Seymour y Robin Thomas , ^{[ 5 ]} pero la demostración simplificada sigue siendo compleja, con "muchas configuraciones y reglas". ^{[ 2 ]}

En 1904, Wernicke introdujo el método de descarga para demostrar el siguiente teorema, que formaba parte de un intento de demostrar el teorema de los cuatro colores. ^{[ 6 ]}

Teorema: Si un grafo planar tiene grado mínimo 5, entonces tiene una arista con extremos de grado 5 o una con extremos de grados 5 y 6. ^{[ 6 ]}

Prueba: Usamos${\displaystyle V}$,${\displaystyle F}$, y${\displaystyle E}$para denotar los conjuntos de vértices, caras y aristas, respectivamente. Llamamos a una arista ligera si sus extremos son ambos de grado 5 o son de grados 5 y 6. Incrustamos el grafo en el plano. Para demostrar el teorema, basta con considerar únicamente triangulaciones planas (porque, si se cumple en una triangulación, al eliminar nodos para volver al grafo original, no se puede eliminar ningún nodo a ninguno de los lados de la arista deseada sin reducir el grado mínimo del grafo por debajo de 5). Añadimos aristas arbitrariamente al grafo hasta que sea una triangulación. Dado que el grafo original tenía un grado mínimo de 5, cada extremo de una nueva arista tiene un grado de al menos 6. Por lo tanto, ninguna de las nuevas aristas es ligera. Así pues, si la triangulación contiene una arista ligera, entonces esa arista debe haber estado en el grafo original. ^{[ 6 ]}

Damos el cargo${\displaystyle 6-d(v)}$a cada vértice${\displaystyle v}$y el cargo${\displaystyle 6-2d(f)}$a cada cara${\displaystyle f}$, dónde${\displaystyle d(x)}$denota el grado de un vértice y la longitud de una cara. (Como el grafo es una triangulación, la carga en cada cara es 0). Recordemos que la suma de todos los grados en el grafo es igual al doble del número de aristas; de manera similar, la suma de todas las longitudes de las caras es igual al doble del número de aristas. Usando la fórmula de Euler , es fácil ver que la suma de todas las cargas es 12: ^{[ 6 ]}

${\displaystyle {\begin{aligned}\sum _{f\in F}6-2d(f)+\sum _{v\in V}6-d(v)=&\\6|F|-2(2|E|)+6|V|-2|E|=&\\6(|F|-|E|+|V|)=&&12.\end{aligned}}}$

Utilizamos una única regla de descarga: cada vértice de grado 5 otorga una carga de 1/5 a cada vecino. ^{[ 6 ]} La suma de las cargas no cambia y, por lo tanto, es 12. Dado que la suma de las cargas de las caras es 0, la suma de las cargas de los vértices es 12, por lo que deben existir algunos vértices con carga positiva.

Consideramos qué vértices podrían tener una carga final positiva. Los únicos vértices con carga inicial positiva son los vértices de grado 5. Cada vértice de grado 5 da una carga de 1/5 a cada vecino. Por lo tanto, a cada vértice se le da una carga total de como máximo${\displaystyle d(v)/5}$. La carga inicial de cada vértice v es${\displaystyle 6-d(v)}$. Por lo tanto, la carga final de cada vértice es como máximo${\displaystyle 6-4d(v)/5}$Por lo tanto, un vértice solo puede tener carga final positiva si su grado es como máximo 7. Ahora mostramos que cada vértice con carga final positiva es adyacente a un extremo de una arista ligera. ^{[ 6 ]}

Si un vértice${\displaystyle v}$tiene grado 5 o 6 y tiene carga final positiva, entonces${\displaystyle v}$recibió carga de un vértice adyacente de grado 5${\displaystyle u}$, por lo tanto borde${\displaystyle uv}$es ligero. Si un vértice${\displaystyle v}$tiene grado 7 y tiene carga final positiva, entonces${\displaystyle v}$recibió carga de al menos 6 vértices adyacentes de grado 5. Dado que el grafo es una triangulación, los vértices adyacentes a${\displaystyle v}$debe formar un ciclo, y dado que solo tiene grado 7, los vecinos de grado 5 no pueden estar todos separados por vértices de grado superior; al menos dos de los vecinos de grado 5 de${\displaystyle v}$deben estar adyacentes entre sí en este ciclo. Esto produce el borde claro. ^{[ 6 ]}