El método de descarga es una técnica utilizada para probar lemas en la teoría de grafos estructurales . La descarga es más 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 cada gráfico de una determinada clase contiene algún subgráfico de una lista específica. La presencia del subgrafo deseado se usa a menudo para probar un resultado de coloración .
Más comúnmente, la descarga se aplica a gráficos planos . Inicialmente, se asigna una carga a cada cara y a cada vértice del gráfico. Los cargos se asignan de modo que sumen un pequeño número positivo. Durante la fase de descargala carga en 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 los cargos. Las reglas están diseñadas para 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. Muchos argumentos de descarga utilizan una de las pocas funciones de carga inicial estándar (se enumeran a continuación). La aplicación exitosa del método de descarga requiere un diseño creativo de las reglas de descarga.
Un ejemplo
En 1904, Wernicke introdujo el método de descarga para demostrar el siguiente teorema, que era parte de un intento de demostrar el teorema de los cuatro colores.
Teorema: si un gráfico plano tiene un grado mínimo de 5, entonces tiene una arista con puntos finales tanto de grado 5 como una con puntos finales de grados 5 y 6.
Prueba: usamos, , y para denotar los conjuntos de vértices, caras y aristas, respectivamente. Llamamos luz de borde si sus puntos finales son ambos de grado 5 o de grados 5 y 6. Incruste el gráfico en el plano. Para probar el teorema, es suficiente considerar solo triangulaciones planas (porque, si se mantiene en una triangulación, al eliminar nodos para volver al gráfico original, ninguno de los dos lados del borde deseado puede eliminarse sin reducir el grado mínimo del gráfico siguiente 5). Agregamos aristas arbitrariamente al gráfico hasta que se convierte en una triangulación. Dado que el gráfico original tenía un grado mínimo de 5, cada punto final de un nuevo borde tiene un grado de al menos 6. Por lo tanto, ninguno de los nuevos bordes es claro. Por lo tanto, si la triangulación contiene un borde claro, entonces ese borde debe haber estado en el gráfico original.
Le damos la carga a cada vértice y la carga a cada cara , dónde denota el grado de un vértice y la longitud de una cara. (Dado que la gráfica es una triangulación, la carga en cada cara es 0.) Recuerde que la suma de todos los grados en la gráfica 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 todos los cargos es 12:
Usamos una sola regla de descarga:
- Cada vértice de grado 5 da una carga de 1/5 a cada vecino.
Consideramos qué vértices podrían tener 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. Entonces, a cada vértice se le da una carga total de como máximo. La carga inicial de cada vértice v es. Entonces, la carga final de cada vértice es como máximo. Por lo tanto, un vértice solo puede tener carga final positiva si tiene un grado como máximo 7. Ahora mostramos que cada vértice con carga final positiva es adyacente a un punto final de un borde ligero.
Si un vértice tiene grado 5 o 6 y tiene carga final positiva, entonces recibió carga de un vértice de grado 5 adyacente , así que borde es ligero. Si un vértice tiene grado 7 y tiene carga final positiva, entonces recibió carga de al menos 6 vértices adyacentes de grado 5. Dado que la gráfica es una triangulación, los vértices adyacentes adebe 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 dedeben estar adyacentes entre sí en este ciclo. Esto produce el borde de la luz.
Referencias
- Appel, Kenneth ; Haken, Wolfgang (1977), "Cada mapa plano tiene cuatro colores. I. Descarga", Illinois Journal of Mathematics , 21 : 429–490, doi : 10.1215 / ijm / 1256049011.
- Appel, Kenneth ; Haken, Wolfgang (1977), "Cada mapa plano tiene cuatro colores. II. Reducibilidad", Illinois Journal of Mathematics , 21 : 491–567, doi : 10.1215 / ijm / 1256049012.
- Hliněný, Petr (2000), Técnica de descarga en la práctica. (Texto de la conferencia para la Escuela de Primavera de Combinatoria).
- Robertson, Neil ; Sanders, Daniel P .; Seymour, Paul ; Thomas, Robin (1997), "El teorema de los cuatro colores", Journal of Combinatorial Theory, Serie B , 70 : 2-44, doi : 10.1006 / jctb.1997.1750.
- Wernicke, P. (1904), "Über den kartographischen Vierfarbensatz" (PDF) , Matemáticas. Ana. (en alemán), 58 (3): 413–426, doi : 10.1007 / bf01444968.