Applicazioni della teoria dei grafi
Grafici planari
Si dice che un grafico G è planare se può essere rappresentato su un piano in modo tale che i vertici sono tutti punti distinti, i bordi sono curve semplici e non vi sono due bordi che si incontrano se non ai loro terminali. Ad esempio, K 4, il grafico completo su quattro vertici, è planare, come mostra la Figura 4A.
Si dice che due grafici siano omeomorfi se entrambi possono essere ottenuti dallo stesso grafico mediante suddivisioni dei bordi. Ad esempio, i grafici nella Figura 4A e nella Figura 4B sono omeomorfi.
Il grafico K m, n è un grafico per il quale l'insieme di vertici può essere diviso in due sottoinsiemi, uno con m vertici e l'altro con n vertici. Eventuali due vertici dello stesso sottoinsieme non sono adiacenti, mentre due vertici di diversi sottoinsiemi sono adiacenti. Il matematico polacco Kazimierz Kuratowski nel 1930 dimostrò il seguente famoso teorema:
Una condizione necessaria e sufficiente affinché un grafico G sia planare è che non contiene un sottografo omeomorfo a K 5 o K 3,3 mostrato in Figura 5.
Una contrazione elementare di un grafico G è una trasformazione di G in un nuovo grafico G 1, in modo tale che due vertici adiacenti u e ù di G siano sostituiti da un nuovo vertice w in G 1 e w sia adiacente in G 1 a tutti i vertici in che o tu o u sei adiacente in G. Si dice che un grafico G * è una contrazione di G se G * può essere ottenuto da G mediante una sequenza di contrazioni elementari. Quella che segue è un'altra caratterizzazione di un grafico planare dovuta al matematico tedesco K. Wagner nel 1937.
Un grafico è planare se e solo se non è contrattabile a K 5 o K 3,3.
Il problema della mappa a quattro colori
Per più di un secolo la soluzione del problema della mappa a quattro colori sfuggì a tutti gli analisti che lo tentarono. Il problema potrebbe aver attirato l'attenzione di Möbius, ma il primo riferimento scritto ad esso sembra essere una lettera di Francis Guthrie a suo fratello, uno studente di Augustus De Morgan, nel 1852.
Il problema riguarda le mappe planari, ovvero le suddivisioni del piano in regioni non sovrapposte delimitate da semplici curve chiuse. Nelle mappe geografiche è stato osservato empiricamente, in tutti i casi speciali che sono stati provati, che al massimo sono necessari quattro colori per colorare le regioni in modo che due regioni che condividono un confine comune siano sempre colorate in modo diverso, e in alcuni casi in cui sono necessari almeno quattro colori. (Le regioni che si incontrano solo ad un certo punto, come gli stati del Colorado e dell'Arizona negli Stati Uniti, non sono considerate avere un confine comune). Una formalizzazione di questa osservazione empirica costituisce ciò che viene chiamato "teorema dei quattro colori". Il problema è dimostrare o confutare l'affermazione che questo è il caso di ogni mappa planare. Che tre colori non saranno sufficienti è facilmente dimostrato, mentre la sufficienza di cinque colori fu dimostrata nel 1890 dal matematico britannico PJ Heawood.
Nel 1879 AB Kempe, un inglese, propose una soluzione al problema dei quattro colori. Sebbene Heawood mostrasse che l'argomentazione di Kempe era errata, due dei suoi concetti si rivelarono fruttuosi nelle successive indagini. Uno di questi, chiamato inevitabilità, afferma correttamente l'impossibilità di costruire una mappa in cui ciascuna delle quattro configurazioni è assente (queste configurazioni sono costituite da una regione con due vicini, uno con tre, uno con quattro e uno con cinque). Il secondo concetto, quello della riducibilità, prende il nome dalla valida prova di Kempe che se esiste una mappa che richiede almeno cinque colori e che contiene una regione con quattro (o tre o due) vicini, allora deve esserci una mappa che richiede cinque colori per un numero minore di regioni. Il tentativo di Kempe di dimostrare la riducibilità di una mappa contenente una regione con cinque vicini era errato, ma fu corretto in una prova pubblicata nel 1976 da Kenneth Appel e Wolfgang Haken degli Stati Uniti. La loro prova ha suscitato alcune critiche perché ha richiesto la valutazione di 1.936 casi distinti, ciascuno dei quali coinvolge fino a 500.000 operazioni logiche. Appel, Haken e i loro collaboratori hanno ideato programmi che permettevano a un grande computer digitale di gestire questi dettagli. Il computer ha richiesto più di 1.000 ore per eseguire l'operazione e la prova formale risultante è lunga diverse centinaia di pagine.
Cicli euleriani e problema del ponte di Königsberg
Una multigrafo G è costituita da un insieme non vuoto V (G) di vertici e da un sottoinsieme E (G) dell'insieme di coppie non ordinate di elementi distinti di V (G) con una frequenza f ≥ 1 attaccata a ciascuna coppia. Se la coppia (x 1, x 2) con frequenza f appartiene a E (G), i vertici x 1 e x 2 sono uniti da bordi f.
Un ciclo euleriano di una multigrafo G è una catena chiusa in cui ogni bordo appare esattamente una volta. Eulero mostrò che una multigrafo possiede un ciclo euleriano se e solo se è collegato (a parte punti isolati) e il numero di vertici di grado dispari è zero o due.
Questo problema è emerso innanzitutto nel modo seguente. Il fiume Pregel, formato dalla confluenza dei suoi due rami, attraversa la città di Königsberg e scorre su entrambi i lati dell'isola di Kneiphof. C'erano sette ponti, come mostrato nella Figura 6A. I cittadini si chiedevano se fosse possibile fare una passeggiata e attraversare ogni ponte una sola volta. Ciò equivale a trovare un ciclo euleriano per la multigrafo nella Figura 6B. Eulero mostrò che era impossibile perché ci sono quattro vertici di ordine dispari.
