Grafi e retiMaps

Abbiamo già usato la teoria dei grafi con alcune mappe. Rimpicciolendo una mappa, si nota che le singole strade e i ponti non sono più visibile, mentre vediamo il contorno di interi Paesi.

Quando si colora una mappa - o qualsiasi altro disegno costituito da regioni distinte - i Paesi adiacenti sono colorati con colori diversi. Potremmo anche voler usare il minor numero possibile di colori. Alcune semplici "mappe", come una scacchiera, richiedono solo due colori (bianco e nero), ma la maggior parte delle mappe complesse ha bisogno di più colori.