Gráficos y RedesMaps

Ya hemos usado la teoría de grafos con ciertos mapas. A medida que nos alejamos, desaparecen carreteras y puentes individuales y en su lugar vemos el contorno de países enteros.

Al colorear un mapa, o cualquier otro dibujo que conste de regiones distintas, los países adyacentes no pueden tener el mismo color. También podríamos querer usar la menor cantidad posible de colores diferentes.

Algunos "mapas" simples, como un tablero de ajedrez, solo necesitan dos colores (blanco y negro), pero la mayoría de los mapas complejos necesitan más.