15.3: Colorear Mapa

Última actualización
Guardar como PDF

Page ID: 114445

Joy Morris
University of Lethbridge

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

Supongamos que tenemos un mapa de una isla que ha sido dividida en estados.

$clipboard_eba8864abf3246bcc6391879904aac345.png$

Tradicionalmente, los creadores de mapas colorean los diferentes estados para asegurar que si dos estados comparten una frontera, no se coloquen con el mismo color. (Esto facilita la distinción de las fronteras.) Si dos estados simplemente se encuentran en una esquina, entonces pueden ser coloreados con el mismo color.

Usando colores adicionales utilizados para agregar al costo de producción del mapa. Además, si hay demasiados colores se vuelven cada vez más difíciles de distinguir entre ellos. La pregunta es, sin saber de antemano cómo será el mapa, ¿hay algún límite sobre cuántos colores se requerirán para colorearlo? Si es así, ¿qué es eso atado? En otras palabras, ¿cuál es el mayor número de colores que podrían requerirse para colorear algún mapa?

Hace más de un siglo, los matemáticos observaron que nunca pareció requerir más que$4$ colores para colorear un mapa. El mapa que se muestra arriba sí requiere$4$ colores, ya que el estado rectangular central (marcado con un asterisco) y los tres estados que lo rodean deben recibir colores diferentes (cada uno comparte un borde con cada uno de los otros). Desafortunadamente, no pudieron probar que nunca se requeriría más, aunque se publicaron una serie de supuestas pruebas y posteriormente se encontró que tenían errores.

Aunque el límite de$4$ eludió muchos intentos de prueba, en$1890$ Percy John Heawood demostró con éxito que$5$ los colores son suficientes para colorear cualquier mapa. (Su método se basó en una prueba incorrecta del Teorema de los Cuatro Colores de Kempe, de$1879$.) Este resultado se conoce como el Teorema de los Cinco Colores. Su prueba es ligeramente técnica pero no difícil, y la daremos en un momento. Primero, daremos una prueba muy breve de que los$6$ colores son suficientes.

Observe que si convertimos el mapa en una gráfica colocando un vértice donde se encuentren los bordes, y un borde donde haya un borde, este problema equivale a encontrar una coloración de vértice adecuada del doble plano de esta gráfica. Así, lo que en realidad demostraremos es que los vértices de cualquier gráfica plana pueden ser coloreados correctamente usando$6$ (o en el resultado posterior,$5$) colores. Hay un detalle que estamos hojeando aquí: el dual planar podría tener bucles, lo que haría imposible colorear la gráfica. Sin embargo, esto sólo puede suceder si hay una cara del mapa original que se encuentra a lo largo de una frontera, lo que nunca sucedería en un mapa. El doble plano también podría tener múltiples bordes, pero esto no afecta el número de colores requeridos para colorear correctamente la gráfica, por lo que podemos eliminar cualquier multiborde y asumir que estamos tratando con una gráfica plana simple.

Proposición$\PageIndex{1}$

Cada gráfico plano es correctamente$6$ coloreable.

Prueba

Hacia una contradicción, supongamos que existe una gráfica plana que no es correctamente$6$ -coloreable. Al eliminar aristas y vértices, podemos encontrar un subgrafo$G$ que es un gráfico plano$7$ -crítico.

Por Corolario 15.2.3, debemos tener$δ(G) ≤ 5$ ya que$G$ es planar. Pero por el Teorema 14.3.1, debemos tener

\[δ(G) ≥ 7 − 1 = 6\]

ya que$G$ es$7$ -crítico. Esta contradicción sirve para demostrar que cada gráfica plana es correctamente$6$ coloreable.

Teorema$\PageIndex{1}$: Five Colour Theorem

Cada gráfico plano es correctamente$5$ coloreable.

Prueba

Hacia una contradicción, supongamos que existe una gráfica plana que no es correctamente$5$ -coloreable. Al eliminar aristas y vértices, podemos encontrar un subgrafo$G$ que es un gráfico plano$6$ -crítico. Ya que$G$ es planar, eso nos dice Corolario 15.2.3$δ(G) ≤ 5$. También sabemos por el Teorema 14.3.1 que$δ(G) ≥ 6−1 = 5$ ya que$G$ es$6$ -crítico. Que v sea un vértice de valencia$δ(G) = 5$.

Por la definición de una gráfica$k$ -crítica,$G \setminus \{v\}$ puede ser correctamente$5$ -coloreada. Dado que$G$ en sí mismo no puede ser adecuadamente$5$ coloreado, a los vecinos de todos se les$v$ debe haber asignado diferentes colores en la$5$ coloración adecuada de$G \setminus \{v\}$. Etiquetemos a los vecinos de$v$ como$v_1$,,,$v_2$$v_3$$v_4$, y$v_5$ como aparecen en el sentido de las agujas del reloj$v$. Llamaremos al color$v_1$ azul, al color$v_2$ púrpura, al color$v_3$ amarillo y al color$v_4$ verde, como se muestra en la imagen. Aquí hay una imagen (donde, debido a que este texto está impreso en blanco y negro, hemos puesto la primera letra de un color en un vértice, en lugar de colorear realmente el vértice).

$clipboard_ec6fe8f1ed3009fd368ca4b9b537dbb3f.png$

Considera la subgráfica que consiste en los vértices coloreados de azul o amarillo (y todos los bordes entre dichos vértices). Si$v_1$ y no$v_3$ están en el mismo componente conectado de esta subgrafía, entonces en el componente conectado que contiene$v_1$, podríamos intercambiar los colores amarillo y azul. Ya que estamos haciendo esto a todo en un componente conectado del subgrafo amarillo-azul, el resultado seguirá siendo una coloración adecuada, pero$v_1$ ahora tiene color amarillo, por lo que se$v$ puede colorear con azul. Esto contradice el hecho de que$G$ es$6$ -crítico, por lo que debe darse el caso de que$v_1$ y$v_3$ estén en el mismo componente conectado de la subgrafía amarillo-azul. En particular, hay un paseo desde$v_1$ hasta$v_3$ que utiliza únicamente vértices amarillos y azules. Por la Proposición 12.3.1, de hecho hay un camino de$v_1$ a$v_3$ que usa solo vértices amarillos y azules.

De igual manera, si consideramos la subgráfica que consiste en los vértices coloreados púrpura o verde (y todos los bordes entre dichos vértices), vemos que debe haber un camino de$v_2$ a$v_4$ que utilice únicamente vértices morados o verdes.

No hay manera de dibujar el camino amarillo-azul de$v_1$ a$v_3$ y el camino verde púrpura de$v_2$ a$v_4$, sin que los dos caminos se crucen entre sí. Dado que la gráfica es plana, deben cruzarse entre sí en un vértice,$u$. Ya que$u$ está en el camino amarillo-azul, debe ser de color amarillo o azul. Ya que$u$ está en el camino púrpura-verde, debe ser de color púrpura o verde. No es posible satisfacer ambas condiciones en el color de$u$. Esta contradicción sirve para demostrar que no existe una gráfica plana$6$ crítica, por lo que cada gráfica plana es correctamente$5$ coloreable.

De hecho, Appel y Haken probaron el Teorema de los Cuatro Colores en$1976$.

Teorema$\PageIndex{2}$: Four Colour Theorem

Cada gráfico plano es correctamente$4$ coloreable.

Prueba

Su prueba consistió en considerar un número muy grande de casos —tantos que usaron una computadora para analizarlos todos. Aunque las computadoras se utilizan a menudo en el trabajo matemático ahora, esta fue la primera prueba que razonablemente no pudo verificarse a mano. Fue visto con sospecha durante mucho tiempo, pero ahora es generalmente aceptado.

Uno de los métodos por los cuales los matemáticos intentaron sin éxito probar el Teorema de los Cuatro Colores parecía particularmente prometedor, y ha llevado a una gran cantidad de trabajo interesante por derecho propio. Requerimos un par de definiciones para explicar la conexión.

Definición: Cubic Graph

Una gráfica cúbica es una gráfica para la que todos los vértices tienen valencia$3$.

Definición: Bridge

Un puente en una gráfica conectada es una arista cuya eliminación desconecta la gráfica.

Teorema$\PageIndex{3}$

El problema de$4$ -colorear una gráfica plana es equivalente al problema de$3$ -colorear bordes una gráfica cúbica que no tiene puentes.

Prueba

Demostraremos una dirección de la equivalencia señalada en este teorema; la otra dirección es un poco más complicada.

Supongamos que cada gráfico plano puede ser correctamente$4$ coloreado, y ese$G$ es un gráfico cúbico (simple) sin puente, incrustado en el plano. Demostraremos que hay una$3$ coloración adecuada de los bordes de$G$. Ya que$G$ es sin puente, no nos encontramos con el problema de un bucle en el dual planar, por lo que el Teorema de Cuatro Colores se aplica a las caras de$G$. Colorea correctamente las caras$G$ con los colores rojo, verde, amarillo y negro. Cada borde$G$ se encuentra entre caras de dos colores distintos, por la definición de una coloración adecuada de un mapa. Colorea los bordes de$G$ acuerdo con la siguiente tabla: si los colores de las caras separadas por el borde$e$ son los colores enumerados en la columna de la izquierda, entonces usa el color que aparece en la columna derecha para colorear$e$.

Colores de cara	Color de borde
verde, negro	discontinua
amarillo, negro	punteado
rojo, negro	sólido
verde, amarillo	sólido
verde, rojo	punteado
rojo, amarillo	discontinua

Que$v$ sea un vértice arbitrario. Mostraremos que los tres bordes incidentes con$v$ deben recibir todos colores diferentes. Dado que$3$ los bordes se encuentran en$v$, tres caras también se encuentran en$v$, y cada par de estas caras comparten un borde. Así, las tres caras que se encuentran en absoluto$v$ deben recibir diferentes colores. Hay cuatro casos diferentes, dependiendo de qué color no se utilice para una cara en$v$. Mostramos lo que sucede en la siguiente imagen, usando$R$,$G$$Y$, y$B$ para indicar los colores de las caras, y coloreando los bordes de acuerdo con la tabla anterior en cada caso.

$clipboard_e21b16d747cb3169a8baa7bcf8f53c44c.png$

En cada caso, a los tres bordes incidentes$v$ se les asignan diferentes colores, por lo que esta es una coloración adecuada de los$3$ bordes$G$.

Este teorema fue probado por Tait en$1880$; pensó que toda gráfica cúbica sin puentes debe ser$3$ -borde-coloreable, y así que había probado el Teorema de los Cuatro Colores. De hecho, el Teorema de Vizing nos dice que cualquier gráfica cúbica puede ser de$4$ color de borde, por$1$ lo que solo necesitaríamos reducir el número de colores para poder probar el Teorema de los Cuatro Colores. El problema, por lo tanto, se reduce a demostrar que no hay gráficas cúbicas planas sin puente que sean de clase dos.

En$1881$, Petersen publicó la gráfica de Petersen que vimos anteriormente en el Ejemplo 14.3.4.

$clipboard_e344e5b311f3550ecaec3e214d2f339ba.png$

Esta gráfica es cúbica y no tiene puentes, pero no es$3$ colorable por bordes (esto se puede probar mediante un análisis caso por caso). Así, ¡existen gráficas cúbicas sin puente que son clase dos! Mucha gente ha tratado de encontrar otros ejemplos, ya que clasificarlos podría proporcionar una prueba del Teorema de los Cuatro Colores.

Durante muchos años, Martin Gardner escribió una columna en el Scientific American sobre interesantes problemas matemáticos y acertijos. Como el Teorema de los Cuatro Colores es fácil de explicar sin lenguaje técnico, fue un tema sobre el que escribió. Al escribir sobre la importancia de las gráficas de clase dos cúbicas sin puente, decidió que necesitaban un nombre más atractivo. Como parecían raros y esquivos, los llamó gruñidos, después del poema de Lewis Carroll “La caza del Snark”. El nombre se ha pegado.

Definición: Snark

Un snark es una gráfica cúbica de clase dos sin puente.

Se conocen dos familias infinitas y una serie de gruñidos individuales. No hay razón para creer que estos son todos los gruñidos que existen. Por el Teorema de los Cuatro Colores, sabemos que no hay gruñidos planos; si pudiéramos encontrar una prueba directa de que no hay gruñidos planos, esto proporcionaría una nueva prueba del Teorema de los Cuatro Colores.

Ejercicio$\PageIndex{1}$

1) Demostrar que si una gráfica cúbica$G$ tiene un ciclo Hamilton, entonces$G$ es una gráfica de clase uno.

2) Correctamente$4$ -colorea las caras del mapa dado al inicio de esta sección.

3) El mapa dado al inicio de esta sección se puede convertir en una gráfica cúbica, colocando un vértice en todas partes donde se encuentren dos fronteras (incluyendo la costa como frontera) y bordes donde haya fronteras. Usa el método de la prueba del Teorema 15.3.3 para$3$ -colorar adecuadamente esta gráfica cúbica, usando tu$4$ -coloración de las caras.

4) Demostrar que una gráfica$G$ que admite una incrustación plana tiene un recorrido de Euler si y solo si cada dual planar de$G$ es bipartito.

5) Demostrar que si una gráfica$G$ que admite una incrustación plana en la que cada cara está rodeada de$3$ bordes exactamente,$G$ es$3$ -coloreable si y solo si tiene un recorrido por Euler.

Search

Text Color

Text Size

Margin Size

Font Type