Hispanopedia Wiki
Articulo de referencia

Gráfico de Poussin

[[Planar graph|Planar]]"}},"i":0}}]}"> Cadenas de Kempe enredadas en el grafo de Poussin. Las adyacencias entre las regiones de este mapa forman el grafo de Poussin, parcialment...

Hispanopedia WikiContenido en espanolLectura gratuita
Cadenas de Kempe enredadas en el grafo de Poussin. Las adyacencias entre las regiones de este mapa forman el grafo de Poussin, parcialmente coloreado con cuatro colores, con la región exterior sin color. Las cadenas de Kempe azul-amarillo y azul-verde (líneas amarillas y verdes) conectan los vecinos de la región exterior, por lo que Kempe intercambiaría los colores en la cadena roja-amarilla izquierda y la cadena roja-verde derecha (líneas rojas), permitiendo que la región exterior sea roja. A medida que las cadenas azul-amarillo y azul-verde se cruzan, este intercambio de colores haría que las regiones amarilla y verde superiores se volvieran rojas, produciendo una coloración inválida.

En teoría de grafos, el grafo de Poussin es un grafo planar con 15 vértices y 39 aristas. Recibe su nombre de Charles Jean de la Vallée-Poussin .

Historia

En 1879, Alfred Kempe publicó una demostración del teorema de los cuatro colores , una de las grandes conjeturas de la teoría de grafos . [ 1 ] Si bien el teorema es cierto, la demostración de Kempe es incorrecta. Percy John Heawood la ilustró en 1890 [ 2 ] con un contraejemplo, y de la Vallée-Poussin llegó a la misma conclusión en 1896 con el grafo de Poussin . [ 3 ]

La demostración (incorrecta) de Kempe se basa en cadenas alternas , y dado que estas cadenas resultan útiles en la teoría de grafos, los matemáticos siguen interesados ​​en tales contraejemplos. Posteriormente se encontraron más: primero, el grafo de Errera en 1921, [ 4 ] [ 5 ] luego el grafo de Kittell en 1935, con 23 vértices, [ 6 ] y finalmente dos contraejemplos mínimos (el grafo de Soifer en 1997 y el grafo de Fritsch en 1998, ambos de orden 9). [ 7 ] [ 8 ] [ 9 ]

Referencias

  1. ↑ Kempe, AB "Sobre el problema geográfico de los cuatro colores." Amer. J. Math. 2, 193–200, 1879.
  2. ↑ PJ Heawood, "Teorema del color de los mapas", Quart. J. Pure Appl. Math. 24 (1890), 332–338.
  3. ↑ RA Wilson, Graphs, colourings and the four-colour theorem, Oxford University Press, Oxford, 2002. MR 1888337 Zbl 1007.05002 .  
  4. ^ Errera, A. "Du coloriage des cartes et de quelques questions d'analysis situs". Doctor en Filosofía. tesis. 1921.
  5. ↑ Peter Heinig. Demostración de que el grafo de Errera es un impasse de Kempe estrecho . 2007.
  6. ↑ Kittell, I. "Un grupo de operaciones en un mapa parcialmente coloreado." Bull. Amer. Math. Soc. 41, 407–413, 1935.
  7. ↑ A. Soifer, “Coloración de mapas en la época victoriana: problemas e historia”, Mathematics Competitions 10 (1997), 20–31.
  8. ↑ R. Fritsch y G. Fritsch, El teorema de los cuatro colores, Springer, Nueva York, 1998. MR 1633950 . 
  9. ↑ Gethner, E. y Springer, WM II. « ¿ Qué tan falsa es la demostración de Kempe del teorema de los cuatro colores? » Congr. Numer. 164, 159–175, 2003.
Lecturas relacionadas
6 articulos
Cadena KempeCadena KempeEn matemáticas , una cadena de Kempe es una herramienta utilizada principalmente en el estudio del teorema de los cuatro colores . Intuitivamente, ...Gráfico planarGráfico planarEn teoría de grafos , un grafo plano es un grafo que se puede incrustar en el plano , es decir, se puede dibujar en el plano de tal manera que sus ...Charles Jean de la Vallée PoussinCharles-Jean Étienne Gustave Nicolas, barón de la Vallée Poussin ( pronunciación francesa: [ʃaʁl ʒɑ̃ etjɛn ɡystav nikɔla baʁɔ̃ də la vale pusɛ̃] ; ...Alfred KempeAlfred KempeSir Alfred Bray Kempe FRS (6 de julio de 1849 - 21 de abril de 1922) fue un matemático mejor conocido por su trabajo sobre enlaces y el teorema de ...Teorema de los cuatro coloresEjemplo de un mapa de cuatro colores Un mapa de cuatro colores de los estados de los Estados Unidos (ignorando lagos y océanos) En matemáticas , el...Teoría de grafosTeoría de grafosEn matemáticas , la teoría de grafos es el estudio de los grafos , que son estructuras matemáticas utilizadas para modelar relaciones por pares ent...