Coloriamo le mappe

[martinof]

è da un po' che sto lavorando ad una nuova dimostrazione per il teorema dei quattro colori, avevo già postato qualcosa, ma ho dovuto rivedere il tutto, ma prima di postarla (è nella fase “ultimi ritocchi”), volevo anticipare il metodo per assegnare in modo esplicito ad ogni regione della mappa il giusto colore per giungere ad una corretta colorazione, sia per ricevere critiche, domande, consigli o quant'altro (modi di presentarla, scambio di idee con qualcuno che ci sta lavorando, ecc.)
Assumendo che, bene o male, tutti sappiamo di cosa si parla,in questa spiegazione si assume che:
data una configurazione con k regioni, ogni regione (o zona) sarà contrassegnata da una lettera (A, B, C, ... k). Dati 4 colori blu (b), giallo (y), rosso (r) e verde (g), si assegneranno alle zone con la seguente notazione [b= A, y= B, r= C, g= D], o, compattificando: [A,B,C,D], intendendo che il medesimo “posto” assegna il medesimo colore, cioè scrivendo [A,B,C,D] e [E,F,G,H], A ed E, saranno entrambe blu; B ed F entrambe gialle e così via.
Si procede scegliendo una qualunque zona, le si assegna un colore e poi si passa a considerare un'altra zona a questa adiacente assegnandole un altro colore, considerando una successiva zona che:
- sia adiacente ad una già colorata;
- sia noto a quali zone già colorate è adiacente.
per le prime due zone si dovrebbe scrivere:
[A,B,-,-], o [A,-,B,-], o [A,-,-,B], o [B,A,-,-], o [-,A,B,-], o [-,A,-,B],... per un totale di 12 modi diversi. Ma noi “siamo furbi” perché si può assegnare una colorazione “base” di partenza, così facendo non si troveranno tutte (ma proprio tutte) le possibili corrette colorazioni perché per le prime zone non si “ruotano” i colori, ma comunque ne risulterà almeno una.
Per indicare le varie combinazioni di colori, adottiamo la notazione Kn, dove:
-K è il nome della “nuova” zona aggiunta;
-n, è il numero dei possibili modi di combinare i colori che include quella zona.
Ad esempio scelte A, B, C reciprocamente adiacenti, si avrà: [A,B,C,-],
se D è adiacente a tutte e tre, si potrà avere solo: D1=[A,B,C,D], altrimenti, ad esempio, se fosse adiacente solo ad A e C si avrebbe:
D1=[A,D,C,-] e D2=[A,-,C,D], cioè si avranno due “scenari” differenti con cui continuare.
Senza voler ora specificare i vari casi, la regola generale è di riscrivere tutti gli “scenari” che contengono le zone adiacenti omettendo però di scrivere le zone non adiacenti. Da ognuno di questi “nasceranno” 1, 2 o 3 nuovi scenari (o nuove ramificazioni) a seconda dei “posti liberi”.
Ricapitolando:
passo 1: si assegnano (furbescamente) tre colori di “partenza” a tre zone reciprocamente adiacenti tra loro e si scrive [A,B,C,-];
passo 2: considerando ogni successiva zona, si scrive un nuovo scenario con (ovviamente nello stesso posto) le zone a cui è adiacente la “nuova” zona, scrivendo quest'ultima nel posto lasciato libero dall'eventuale zona non adiacente. Se lo scenario precedente consente di assegnare 2 o 3 colori alla nuova zona, si scriveranno i 2 o 3 nuovi scenari con la nuova zona riportata ogni volta in uno dei posti possibili. Ripetere per ogni precedente scenario esistente.

Si dimostra che è sempre possibile scrivere un successivo scenario e che tutte le zone sono “comprese” nella corretta colorazione.

Un esempio. Magari la descrizione è poco chiara, un piccolo esempio forse chiarisce meglio, si utilizza “//” per indicare “adiacente a” .
partenza: [A,B,C,-]
D // (B, C): D1=[D,B,C,-]; D2=[-,B,C,D];
E // (A, C): da D1 deriverà: E1=[A,E,C,-]; E2=[A,-,C,E]
da D2 deriverà: E3=[A,E,C,-]; E4=[A,-,C,E], sembrerebbero gli stessi scenari, ma in realtà le colorazioni risultanti differiscono per la zona D, cioè risulterebbe:
per E1: blu=A,D; giallo=B,E; rosso=C; verde=--;
per E2: blu=A,D; giallo=B, ; rosso=C; verde= E;
per E3: blu=A, ; giallo=B,E; rosso=C; verde= D;
per E4: blu=A, ; giallo=B, ; rosso=C; verde= E, D;

F // (A, B): dalla linea di discendenza di E1 deriverà: F1=[A,B,F,-], F2=[A,B,-,F],
dalla linea di discendenza di E2 deriverà F3[A,B,F,-] e F4[A,B,-,F], da E3 seguiranno F5[A,B,F,-], F6[A,B,-,F] e da E4 seguiranno F7[A,B,F,-] e F8[A,B,-,F], come prima, gli scenari veri sono solo due, mentre le 8 differenti colorazioni differiscono per i colori assegnati anche a D ed E;
In questo tipo di configurazione dove le zone sono adiacenti ad una o due altre zone in effetti si hanno più modi di assegnare i colori, continuando si avrà:
G // (B): G1= [G,B,-,-], G2= [-,B,G,-], G3= [-,B,-,G] per ogni F1,F2,...F8 per un totale di 24 diverse combinazioni;

ma consideriamo ora:
H // (A,B,C,D,E,F,G): per lo scenario di partenza si può avere solo H1[-,-,-,H] che “arriverà” a G2 passando da: D1, E1 (ma non E3 perché derivava da D2 che non può essere buono), F1 (ma non F3, F5 ed F7).
Quindi si avrà che i colori da assegnare sono:

blu= A, D, G; giallo= B, E; rosso= C, F; verde= H.
Si è passati da 24 possibili modi a solo uno (anche se in realtà A,B e C possono “ruotare” così come pure i gruppi di colore in blocco).

Come detto si dimostra che esisterà sempre la possibilità di aggiungere una (k+1)-esima zona e continuare ad avere una corretta colorazione della mappa.

Una domanda che ci si può porre è: “ma se all'inizio ci fosse stata una situazione del tipo [A,B,C,D], ad H che colore si assegnava?” la risposta è semplice, infatti si dimostra che se quattro zone sono tutte adiacenti, almeno una non potrà essere adiacente ad altre zone, ciò vuol dire che H non può essere adiacente ad A,B,C,D se queste possono essere colorate solo con quattro colori.
Se qualcuno ha altre domande...

Spero quanto prima di postare la dimostrazione completa (una decina di pagine)
Grazie a chi ha voluto dedicare un po' di tempo alle mie parole.
p.s. mi sono accorto dopo di essere stato un po' troppo lungo... sorry...

[martinof]

si, ma anche li, ci vuole un computer, ci sono 633 confugurazioni, insomma, da come ho capito migliora solo in parte il precedente lavoro di Appel-Haken, ed i motivi che gli autori dicono di non soddisfacenza di quel lavoro sono l'uso del computer, che anche loro usano e la verifica manuale "noiosa", che anche loro propongono, quindi anche la loro dimostrazione sarebbe "per definizione" non completamente soddisfacente...
ma ovviamente io cerco di portare l'acqua al mio mulino!!!
per la dimostrazione dovrei riuscire a pubblicarla entro domani (anche se non credo di trovare un buon traduttore "da cartografico a grafi", mi spiace).

p.s. a proposito di quel link, nel fare l'esempio sopra avevo davanti quella proprio mappa ed ho posto A=wyoming, B=colorado; C= nebraska, D=kansas, E=south dakota, F= utah, G=new messico e per la H ho dovuto far invadere al texas tutti gli altri stati altrimenti bastavano solo 3 colori...

[Rggb1]

Bentornato. Io - confesso - sono un po' in crisi con tutte queste notazioni "cartografiche" e preferisco parlare di grafi colorabili (del resto mi par di ricordare che per te valeva l'opposto).

Comunque a quanto ho capito dimostri che l'algoritmo è corretto e termina sempre, ovvio che la dimostrazione mi interessa.

PS. Ma questa
http://people.math.gatech.edu/~thomas/FC/fourcolor.html
l'avevi letta o no?