Coloriamo le mappe
è 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...
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...
Risposte
"Martino":
Wow, sembra una dimostrazione per autorita'
è una delle 52 possibili quindi vale!!! (le hai lette? sono bellissime)
ok, torniamo quasi-seri.
in effetti hai ragione, c'è un certo delta tra quello che penso, quello che scrivo, quello che gli altri capiscono, quello che scrivono, quello che capisco ecc. e mi rendo conto che ci si incasina sempre di più
provo a spiegarmi un'ultima volta anche perchè non mi fa di fare quello che si incaponise sulle cse e non vuol sentire ragioni, come detto parlare senza capirsi non serve a nulla...
quello che volgio dire è che si può concludere la colorazione in modo corretto se ragiono così:
data una mappa cancello tutte le zone tranne una:
considero una prima zona:
quale colore posso darle? i quattro disponbili
perchè? nessuna di quelle adiacenti ha quei colori
ho una buona colorazione? si, ne ho 4 diverse
spunta fuori e considero una seconda zona, mi ritrovo con 4 scenari di "partenza":
quale colore posso darle? 3 per ogni scenario di partenza
perchè? è adicente ad una zona colorata e non può avere lo stesso colore
ho una buona colorazione? si, ne ho 4*3=12 diverse
cioè, perchè DEVO scegliere di non accettare più soluzioni per il mio problema? il succo (magari non ci sono riuscitoa dimostrarlo, ma è il modo che ho provato a seguire) è che tra le possibili soluzioni alla k-esima zona, ce n'è una che consente di avere per (k+1): una corretta colorazione ed il bordo con tre colori
ora ho poco tempo, ma volevo almeno dire queste due cose, prometto di concludere quanto prima...
"Martino":
Avevo scritto: Io per "zona circondata" intendo insieme di regioni tutte circondate e tutte dello stesso colore
Insomma, per me "zona circondata" e' diverso da "regione circondata". Il concetto di "regione circondata" e' inutile ai fini di questa discussione. Una zona circondata e' un insieme di regioni (anche non confinanti!) tutte (prese singolarmente) circondate e tutte dello stesso colore. Una zona circondata determina cioe' un "colore circondato".
Allora c'è un classico "misunderstood". Io chiamavo zona quella che tu chiami regione e viceversa.
Però non ho capito dove entrava in gioco quel di cui parli nella ipotetica dimostrazione di martinof... boh, come detto ci lavorerò ancora un po' su, tutto sommato ormai ho ancora un paio di giorni un po' più leggeri (a parte i pargoli malati a casa
)."Martino":
2) Hai provato a parlare della tua dimostrazione con qualcuno competente? Non hai idea di quanto sia difficile spiegarsi scrivendo. Ci sono alcune cose su cui possiamo discutere pagine intere quando magari c'e' un equivoco alla base che a parole verrebbe immediatamente chiarito. Se non l'hai ancora fatto te lo consiglio: discuti della tua dimostrazione con un matematico. Penso che tu ne conosca.
Quoto.
[edit]
@martinof
Infatti come ho detto, sto facendo molta fatica a "tradurre" in senso matematico la cosa, cosa che mi permetterebbe (forse) di stabilire più facilmente come funziona l'algoritmo e se termina sempre in una configurazione corretta. Ne approfitto per indicare questi due passaggi fondamentali, visto che la tua ipotetica dimostrazione è per l'appunto algoritmica; se vuoi dimostrare che è valida devi:
- dimostrare che l'algoritmo produce sempre il risultato voluto (in soldoni, "funziona sempre");
- dimostrare che l'algoritmo termina.
"Rggb":Avevo scritto:
@Martino:
Scusa questa non l'ho capita
Stando a tale punto (b) mi sembra di capire che comunque una "regola" c'e': assegnare alla nuova regione il colore di una zona circondata. Ma nessuno assicura che tale zona circondata esista.
E' una considerazione generale o ti riferisci a qualcosa dello scritto di martinof? Perché mi sembra ovvio che, se hai $k>=4$ zone, ce ne sia una circondata (equivalentemente: $K_4$ è planare, è un suo sottografo, e nella rappresentazione planare un suo vertice è interno).
"Martino":Insomma, per me "zona circondata" e' diverso da "regione circondata". Il concetto di "regione circondata" e' inutile ai fini di questa discussione. Una zona circondata e' un insieme di regioni (anche non confinanti!) tutte (prese singolarmente) circondate e tutte dello stesso colore. Una zona circondata determina cioe' un "colore circondato".
Io per "zona circondata" intendo insieme di regioni tutte circondate e tutte dello stesso colore
Inutile dire che questo processo a priori ti puo' portare a scartare tutti i percorsi.Wow, sembra una dimostrazione per autorita'
INVECE, ALMENO UNO RESTA
---------------
Ti faccio un esempio con la mia figura.
Io ragiono cosi', dimmi dove mi discosto dal tuo procedimento.
H=1 per forza dato che confina con 2,3,4.
Ora scelgo di colorare M. M ha 1 o 3, ma se voglio che le regioni esterne siano colorate con al piu' tre colori (**) devo mettere M=1.
Siccome ho una regione esterna 2, ora scegliendo di colorare D devo mettere D=2.
Scelgo di colorare O. Per (**) devo mettere O=4.
Scelgo di colorare C. L'unica scelta e' C=3.
Nella figura che ottengo le regioni di bordo sono colorate con 4 colori, quindi ho fallito.
Ho fallito nel senso che se ora ci fosse una regione confinante con tutte quelle esterne dovrei colorarla con un quinto colore.
Ne segue che non ho scelto le regioni da colorare in una sequenza adeguata. E non capisco quale sia il tuo criterio per scegliere ogni volta una regione adeguata da colorare.
------------
martinof, ti faccio un paio (tre) di osservazioni.
1) Non ti riesco a seguire molto perche' tu continui a parlare di casi particolari e secondo me dovresti trattare il caso generale: come fai ad essere sicuro che esiste una colorazione corretta? Riesci a rispondere in modo chiaro a questa domanda? Leggendo pagina 10 della tua dimostrazione (tra parentesi: la dimostrazione e' lunga 11 pagine e a pagina 10 stai ancora trattando esempi con quattro o cinque regioni: questo mi risulta un po' strano, a dire il vero) vedo che verso meta' affermi che nel caso 3 dell'esempio di figura 5 la zona B diventa una nuova z.c. Ma e' chiaro che questo succede dato il particolare caso che hai preso, perche' c'e' una sola regione colorata col colore di B. Ma se ci fossero piu' regioni col colore di B? Non puoi dirmi che non e' possibile dato che essendo la regione C una zona circondata ci puo' benissimo essere una zona del colore di B confinante solo con le regioni A e D.
2) Hai provato a parlare della tua dimostrazione con qualcuno competente? Non hai idea di quanto sia difficile spiegarsi scrivendo. Ci sono alcune cose su cui possiamo discutere pagine intere quando magari c'e' un equivoco alla base che a parole verrebbe immediatamente chiarito. Se non l'hai ancora fatto te lo consiglio: discuti della tua dimostrazione con un matematico. Penso che tu ne conosca.
3) Quando ti ho chiesto di descrivermi il tuo procedimento relativamente alla mia figura grande hai iniziato a scrivere tutti i modi possibili di colorare le zone. Anziche' fare cosi' potevi dirmi "considera l'insieme di tutti i percorsi". Ok, ce l'ho in mente. Ma ora non mi puoi dire che scartando quelli cattivi ottengo quelli buoni, perche' a priori non ce ne sono di buoni. Tu dici che ce ne sono, e sempre a pagina 10 affermi che questo vale perche' esiste sempre un percorso in cui ad ogni tappa c'e' un colore circondato. Solo che non lo dimostri.
"Rggb":
Un suggerimento: prova ad eliminare dalla tua dimostrazione alcune cose, per iniziare dai cd. "pdc" (che non ti servono, direi), e cerca di concentrarti sul dimostrare (se riesci) che il procedimento ha sempre soluzione. Era anche un po' la discussione dell'altra volta, se ben ricordo: se funziona sempre, sarà pure giusto; ma è necessario dimostrare che funziona sempre.
a parte che sono "ldc" o "pdu", proverò a riguardare, ma non mi sembrano del tutto inutili, anzi, visto che sono in vena di confidenze... andando nello spazio (3D) per cercare un teorema equivalente si ha che le "linee di confine" diventano "superfici di confine" ed i "punti d'unione" diventano "linee di unione" con quasi le stesse proprietà per quest'ultime cioè che in una linea d'unione possono essere adicenti solo tre "zone^3" ma crescono più velocemente e con pochi passaggi si dimostra che è sempre possibile che esistano tutte le "zone^3" reciprocamente adiacenti, cioè che non esiste un teorema simile a quello dei 4 colori in 3D, ma questa è un'altra storia e si dovrà raccontare un'altra volta (citazione).
Del fiume d'inchiosrto che ho versato tra le varie pagine scritte, parte ha preso la forma della parola "DOMANDONE" ed in seguito la domanda "come faccio a dimostrare che colorando una (k+1)-esima zona questa non è adiacente ad una di bordo che ha lo stesso colore?" ovvero "che posso mantenere una 3-colorazione per il bordo?" credevo di aver dato una risposta ma non è così, mi sono accorto che dovevo riformulare la risposta, se sono stato fortunato è bastata un po' di logica.
Allora, poniamoci nella condizione di non aver avuto "problemi" possiamo assumere di essere alle prime quattro zone della configurazione ma non sarebbe un caso interessante, anche per quello che intede il mio omonimo, quindi poniamo che ci siano svariate zone già colorate correttamente ed una situazione del tipo (cioè non proprio quella ma con le tre zone disposte in modo simile con una adiacente a tutte e tre) quella delle zone M, D, I e 4 della figura di prima dove le prime tre sono di bordo ad hanno rispettivamente i colori 1, 2, 3.
La prima domanda che ci poniamo è "perchè 1 e 3 (che non sembrano essere adiacenti) non possono essere 1 e 1, o 3 e 3?"
le risposte possibili sono 2: o, in realtà, sono adiacenti, o per altri motivi "indipendenti", cioè, per proseguire bisogna poi trovare una configurazione che le costringa ad avere colori differenti. Se fosse vera la seconda ipotesi per procedere si dovrebbe ricadere nella dimostrazione di Appel-Haken o di Robertson, Sanders, Seymour, Thomas, il che non ha senso per una dimostrazione "alternativa".
Consideriamo però l'ipotesi che siano, in realtà, adiacenti, ad esempio immaginiamo che la zona "I" si allunghi come un barbapapà (scusate ma in questo periodo i miei piccoli non guardano altro) abbracciando comunque un qualsivoglia numero di altre zone già colorate ed arrivi ad essere adiacente ad M.
Si nota che anche se M e D o tra D e I ci fossero altre zone di bordo (sempre colorate con 1, 2 e 3) la cosa non farebbe differenza. E vorrei evidenziare questa cosa chiamandola "punto A".
In questa situazione consideriamo una (k+1)-esima zona che nella figura di prima sia data da (L+O), eventualmente adiacente anche alle altre zone ipotizzate nel "punto A" (N.B. (L+O) non può essere adiacente a zone interne altrimenti M o I non sarebbero di bordo).
In queste condizioni tutte le zone abbracciate da I che "chiude" su M e la (L+O) formano una porzione di mappa "isolata" dove M, I e (L+O) sono di bordo.
Per chi non ci ha fatto caso, una banale proprietà della colorazione è che in una mappa si possono scambiare due colori (ad esempio tutte le zone che hanno 1 possono prendere il 4 se tutte le zone che hanno 4 prendono 1), quindi, posso assegnare a (L+O) il 2 (in teoria doveva avere il 4 ma poi se c'erano altre zone di bordo "fuori mappina" col 2 non era più 3-colorabile) e, SOLO IN QUELLA PORZIONE DI MAPPA scambiare il 2 col 4 alle altre zone (DA NOTARE CHE SE "M" e "I" SONO ADIACENTI QUESTI SCENARI ESISTONO GIÀ).
In conclusione se M e I sono adiacenti ho la soluzione. (primo pezzo della risposta, aspettate a dire "si, ma se non sono adiacenti?")
Altra domanda che posso pormi è: "ma per la zona D è ammissibile una sola colorazione?" anche qui sono due le risposte possibili: si o no.
Se la risposta è si, allora deve esistere una zona circondata. essendo adiacente a M, I e 4 per definizione ed essendo M, D, I di bordo per definizione si deve ammettere che è 4 la zona circondata, ma allora M e D sono adiacenti ed abbiamo appena visto che se sono adiacenti abbiamo una soluzione.
Se la risposta è no, cioè D ammette almeno un'altra colorazione ed essendo adiacente a M ed I che sono di bordo e devono avere quindi il colore 1 e 3 o perchè adiacenti, o per qualunque altro motivo (che non vogliamo neanche sapere per non doverlo chiedere ai 6 signori di prima, in ogni caso siamo "coperti"), dobbiamo ammettere che l'altro colore disponibile sia il 4, cioè che esiste lo scenario che permette di scambiare il colore tra D e la zona "4", e quindi abbiamo una soluzione.
Ora qualcuno può chiedere ma se (L+O) è adiacente ad altre zone "2"? La risposta è semplice: se le zone "2" sono interne alla "mappina" allora diventano "4" e non sono un problema, di esterna ne può essere solo una adiacente a (L+O) basta allora fare copia/incolla con quanto scritto sopra cambiando il 2 col 3, perchè la "I" sarebbe una delle zone ipotizzate nel "punto A", cioè (L+O) prenderebbe il "3" e nella mappina si scambiano "3" e "4".
Allora, poniamoci nella condizione di non aver avuto "problemi" possiamo assumere di essere alle prime quattro zone della configurazione ma non sarebbe un caso interessante, anche per quello che intede il mio omonimo, quindi poniamo che ci siano svariate zone già colorate correttamente ed una situazione del tipo (cioè non proprio quella ma con le tre zone disposte in modo simile con una adiacente a tutte e tre) quella delle zone M, D, I e 4 della figura di prima dove le prime tre sono di bordo ad hanno rispettivamente i colori 1, 2, 3.
La prima domanda che ci poniamo è "perchè 1 e 3 (che non sembrano essere adiacenti) non possono essere 1 e 1, o 3 e 3?"
le risposte possibili sono 2: o, in realtà, sono adiacenti, o per altri motivi "indipendenti", cioè, per proseguire bisogna poi trovare una configurazione che le costringa ad avere colori differenti. Se fosse vera la seconda ipotesi per procedere si dovrebbe ricadere nella dimostrazione di Appel-Haken o di Robertson, Sanders, Seymour, Thomas, il che non ha senso per una dimostrazione "alternativa".
Consideriamo però l'ipotesi che siano, in realtà, adiacenti, ad esempio immaginiamo che la zona "I" si allunghi come un barbapapà (scusate ma in questo periodo i miei piccoli non guardano altro) abbracciando comunque un qualsivoglia numero di altre zone già colorate ed arrivi ad essere adiacente ad M.
Si nota che anche se M e D o tra D e I ci fossero altre zone di bordo (sempre colorate con 1, 2 e 3) la cosa non farebbe differenza. E vorrei evidenziare questa cosa chiamandola "punto A".
In questa situazione consideriamo una (k+1)-esima zona che nella figura di prima sia data da (L+O), eventualmente adiacente anche alle altre zone ipotizzate nel "punto A" (N.B. (L+O) non può essere adiacente a zone interne altrimenti M o I non sarebbero di bordo).
In queste condizioni tutte le zone abbracciate da I che "chiude" su M e la (L+O) formano una porzione di mappa "isolata" dove M, I e (L+O) sono di bordo.
Per chi non ci ha fatto caso, una banale proprietà della colorazione è che in una mappa si possono scambiare due colori (ad esempio tutte le zone che hanno 1 possono prendere il 4 se tutte le zone che hanno 4 prendono 1), quindi, posso assegnare a (L+O) il 2 (in teoria doveva avere il 4 ma poi se c'erano altre zone di bordo "fuori mappina" col 2 non era più 3-colorabile) e, SOLO IN QUELLA PORZIONE DI MAPPA scambiare il 2 col 4 alle altre zone (DA NOTARE CHE SE "M" e "I" SONO ADIACENTI QUESTI SCENARI ESISTONO GIÀ).
In conclusione se M e I sono adiacenti ho la soluzione. (primo pezzo della risposta, aspettate a dire "si, ma se non sono adiacenti?")
Altra domanda che posso pormi è: "ma per la zona D è ammissibile una sola colorazione?" anche qui sono due le risposte possibili: si o no.
Se la risposta è si, allora deve esistere una zona circondata. essendo adiacente a M, I e 4 per definizione ed essendo M, D, I di bordo per definizione si deve ammettere che è 4 la zona circondata, ma allora M e D sono adiacenti ed abbiamo appena visto che se sono adiacenti abbiamo una soluzione.
Se la risposta è no, cioè D ammette almeno un'altra colorazione ed essendo adiacente a M ed I che sono di bordo e devono avere quindi il colore 1 e 3 o perchè adiacenti, o per qualunque altro motivo (che non vogliamo neanche sapere per non doverlo chiedere ai 6 signori di prima, in ogni caso siamo "coperti"), dobbiamo ammettere che l'altro colore disponibile sia il 4, cioè che esiste lo scenario che permette di scambiare il colore tra D e la zona "4", e quindi abbiamo una soluzione.
Ora qualcuno può chiedere ma se (L+O) è adiacente ad altre zone "2"? La risposta è semplice: se le zone "2" sono interne alla "mappina" allora diventano "4" e non sono un problema, di esterna ne può essere solo una adiacente a (L+O) basta allora fare copia/incolla con quanto scritto sopra cambiando il 2 col 3, perchè la "I" sarebbe una delle zone ipotizzate nel "punto A", cioè (L+O) prenderebbe il "3" e nella mappina si scambiano "3" e "4".
@martinof:
Stando a quanto ho capito - magari domattina ricontrollo - devo dire che le considerazioni di Martino sono corrette. Non sono riuscito a trovare la dimostrazione della correttezza; intuisco che il procedimento di colorazione funziona, ma questo però non è sufficiente. Magari mi sbaglio, se pensi sia così fammi capire.
Un suggerimento: prova ad eliminare dalla tua dimostrazione alcune cose, per iniziare dai cd. "pdc" (che non ti servono, direi), e cerca di concentrarti sul dimostrare (se riesci) che il procedimento ha sempre soluzione. Era anche un po' la discussione dell'altra volta, se ben ricordo: se funziona sempre, sarà pure giusto; ma è necessario dimostrare che funziona sempre.
@Martino:
Scusa questa non l'ho capita
E' una considerazione generale o ti riferisci a qualcosa dello scritto di martinof? Perché mi sembra ovvio che, se hai $k>=4$ zone, ce ne sia una circondata (equivalentemente: $K_4$ è planare, è un suo sottografo, e nella rappresentazione planare un suo vertice è interno).
Stando a quanto ho capito - magari domattina ricontrollo - devo dire che le considerazioni di Martino sono corrette. Non sono riuscito a trovare la dimostrazione della correttezza; intuisco che il procedimento di colorazione funziona, ma questo però non è sufficiente. Magari mi sbaglio, se pensi sia così fammi capire.
Un suggerimento: prova ad eliminare dalla tua dimostrazione alcune cose, per iniziare dai cd. "pdc" (che non ti servono, direi), e cerca di concentrarti sul dimostrare (se riesci) che il procedimento ha sempre soluzione. Era anche un po' la discussione dell'altra volta, se ben ricordo: se funziona sempre, sarà pure giusto; ma è necessario dimostrare che funziona sempre.
@Martino:
Scusa questa non l'ho capita
Stando a tale punto (b) mi sembra di capire che comunque una "regola" c'e': assegnare alla nuova regione il colore di una zona circondata. Ma nessuno assicura che tale zona circondata esista.
E' una considerazione generale o ti riferisci a qualcosa dello scritto di martinof? Perché mi sembra ovvio che, se hai $k>=4$ zone, ce ne sia una circondata (equivalentemente: $K_4$ è planare, è un suo sottografo, e nella rappresentazione planare un suo vertice è interno).
"Martino":
Va bene, in pratica quello che ho capito e' che il tuo non e' un approccio algoritmico: semplicemente consideri tutti i percorsi [tex]\sigma[/tex] possibili ed affermi di poter dimostrare che almeno uno porta ad una colorazione corretta.
Stando a quanto dici a pagina 10 (parte sotto) della tua dimostrazione, il principio che usi e': coloriamo una (k+1)-esima regione usando il colore di una zona circondata, e tale zona circondata deve esistere per ipotesi induttiva dato che al passo k le regioni esterne sono colorate con al piu' tre colori. Quello che non spieghi pero' e' come mai puoi colorare una (k+1)-esima regione in modo che poi le regioni esterne siano colorate con al piu' tre colori.
VEDRÒ DI SPIEGARE MEGLIO
Inoltre al punto (b) dici che se dai alla regione k+1 il colore di una zona circondata allora compare una nuova zona circondata. Ma questo e' falso, per esempio se partendo dalla mia figura assegno M=1 poi non ci sono zone circondate. Io per "zona circondata" intendo insieme di regioni tutte circondate e tutte dello stesso colore (anche tu, immagino).
Stando a tale punto (b) mi sembra di capire che comunque una "regola" c'e': assegnare alla nuova regione il colore di una zona circondata. Ma nessuno assicura che tale zona circondata esista.
NO, IO DICO CHE SI È COSTRETTI AD ASSEGNARE IL COLORE DELLA ZONA CIRCONDATA, AD "M" PUOI DARE ANCHE 3, CASO DIVERSO SE NON AVESSI POTUTO DARLE 3 PERCHÈ ANCHE A QUESTA ADIACENTE, MA ALLORA O 2 O 4 DIVENTEREBBERO ZONE CIRCONDATE
Un'altra cosa: io trovo che sia strano che nel discutere il mio esempio tu non abbia mai parlato di zone circondate, dato che le consideri cosi' importanti nella dimostrazione. Sembra quasi che tu invece dica di considerare tutti i percorsi possibili (quelli che tu chiami [tex]\sigma[/tex]) e poi scartare quelli non buoni.
LA ZONA CIRCONDATA (SE MI FOSSI SPIEGATO MEGLIO AL PUNTO b DA TE CITATO) SERVE SOLO PER DIMOSTRARE CHE POI È POSSIBILE ASSEGNARE ALMENO UN COLORE, MA NON OCCORRE ESPLICITARLA DURANTE "L'ASSEGNAZIONE DEI COLORI". TALE ZONA, TANTO PER INTENDERCI È LA PARTE CENTRALE DEL SIMBOLO DI "GOOGLE CROME", CIOÈ CIRCONDATA DA 3 ZONE MUTUAMENTE ADIACENTI
Inutile dire che questo processo a priori ti puo' portare a scartare tutti i percorsi.
INVECE, ALMENO UNO RESTA
...tra le righe
Va bene, in pratica quello che ho capito e' che il tuo non e' un approccio algoritmico: semplicemente consideri tutti i percorsi [tex]\sigma[/tex] possibili ed affermi di poter dimostrare che almeno uno porta ad una colorazione corretta.
Stando a quanto dici a pagina 10 (parte sotto) della tua dimostrazione, il principio che usi e': coloriamo una (k+1)-esima regione usando il colore di una zona circondata, e tale zona circondata deve esistere per ipotesi induttiva dato che al passo k le regioni esterne sono colorate con al piu' tre colori. Quello che non spieghi pero' e' come mai puoi colorare una (k+1)-esima regione in modo che poi le regioni esterne siano colorate con al piu' tre colori.
Inoltre al punto (b) dici che se dai alla regione k+1 il colore di una zona circondata allora compare una nuova zona circondata. Ma questo e' falso, per esempio se partendo dalla mia figura assegno M=1 poi non ci sono zone circondate. Io per "zona circondata" intendo insieme di regioni tutte circondate e tutte dello stesso colore (anche tu, immagino).
Stando a tale punto (b) mi sembra di capire che comunque una "regola" c'e': assegnare alla nuova regione il colore di una zona circondata. Ma nessuno assicura che tale zona circondata esista.
Un'altra cosa: io trovo che sia strano che nel discutere il mio esempio tu non abbia mai parlato di zone circondate, dato che le consideri cosi' importanti nella dimostrazione. Sembra quasi che tu invece dica di considerare tutti i percorsi possibili (quelli che tu chiami [tex]\sigma[/tex]) e poi scartare quelli non buoni. Inutile dire che questo processo a priori ti puo' portare a scartare tutti i percorsi.
Stando a quanto dici a pagina 10 (parte sotto) della tua dimostrazione, il principio che usi e': coloriamo una (k+1)-esima regione usando il colore di una zona circondata, e tale zona circondata deve esistere per ipotesi induttiva dato che al passo k le regioni esterne sono colorate con al piu' tre colori. Quello che non spieghi pero' e' come mai puoi colorare una (k+1)-esima regione in modo che poi le regioni esterne siano colorate con al piu' tre colori.
Inoltre al punto (b) dici che se dai alla regione k+1 il colore di una zona circondata allora compare una nuova zona circondata. Ma questo e' falso, per esempio se partendo dalla mia figura assegno M=1 poi non ci sono zone circondate. Io per "zona circondata" intendo insieme di regioni tutte circondate e tutte dello stesso colore (anche tu, immagino).
Stando a tale punto (b) mi sembra di capire che comunque una "regola" c'e': assegnare alla nuova regione il colore di una zona circondata. Ma nessuno assicura che tale zona circondata esista.
Un'altra cosa: io trovo che sia strano che nel discutere il mio esempio tu non abbia mai parlato di zone circondate, dato che le consideri cosi' importanti nella dimostrazione. Sembra quasi che tu invece dica di considerare tutti i percorsi possibili (quelli che tu chiami [tex]\sigma[/tex]) e poi scartare quelli non buoni. Inutile dire che questo processo a priori ti puo' portare a scartare tutti i percorsi.
(aggiunto dopo) ovviamente non credo che ci sia confusione sul fatto che "ingenuo" è comunque corretto, cioè se posso assegnare tre colori ad una zona, sono tre colorazioni corrette, al limite 1 o 2 diventano "ingenue" dopo, ma prima di considerare un'altra zona non c'è modo di sapere quale colorazione risulterà essere poi stata ingenua, anche perchè io "non conosco" neanche il numero il zone che compone la configurazione, per come la intendi tu (dare una colorazione univoca) non si può fare perchè non si hanno informazioni, ma d'altro canto si è liberi di aggiungere altre zone a piacimento, cioè io ti dico quali 4-colorazioni sono possibili e risulta che almeno una è sempre possibile (fine aggiunto dopo)
il punto è che il procedimento si basa proprio su colorazioni "ingenue" che poi verranno scartate proprio perchè non c'è uno studio a priori della mappa, ma si dimostra che per una successiva zona, tra le colorazioni ingenue almeno una non lo è, quindi anche se ho una mappa con 1000 zone, so già che alla 999-esima avrò un certo numero di colorazioni ingenue tra cui quella che mi consente di colorare la 1000-esima mappa.
considerando ogni successiva zona i passi da fare sono: considero il primo "scenario" della precedente zona, se è possibile scrivo un nuovo scenario "diiscendente" da quello, ponendo la nuova zona nelle posizioni "possibili" scrivendo n nuovi scenari possibili (da 1 a 3 perchè la zona è stata scelta adiacente ad almeno una). le posizioni "possibili" sono quelle dove in quel "ramo di discendenza" non risultano zone adiacenti. una volta scritti i nuovi scenari passo a considerare una nuova zona.
passiamo all'esempio.
procedo in ordine alfabetico perchè è la prima cosa che mi venuto in mente, avrei potuto sceglere dalla zona più a nord a quella più a sud, da quella più estesa a quella meno estesa, ma scelgo l'ordine alfabetico, ricordano le due condizioni (adiacente ad una già colorata e di "bordo") l'ordine reale è B, D, H, C, F, I, L, A, E, M, N, O, P, G, (altrimenti, ad esempio la P non sarebbe di bordo se la colorassi prima della G), ricordo che ogni "posto" tra le parentesi è il colore assegnato.
partenza(1,2,3,4), considero B adiacente a 4, avrò 3 possibili modi di assegnare i colori e risulterà:
B1(B,2,3,4), B2(1,B,3,4), B3(1,2,B,4)
considero D adiacente alla zona colorata col 4,
da B1 avrò: D1(D,2,3,4), D2(1,D,3,4), D3(1,2,D,4), da B2 e B3 si avranno le stesse colorazioni per D (D1=D4,D7; D2=D5,D8; D3=D6,D9), un totale di 9 possibili colorazioni perchè B e D sono "indipendenti".
consideriamo H adiacente a: B, 2, 3 e 4.
da D1, D2 e D3 è impossibile proseguire perchè non ci sono posti buoni per H e vengono quindi scartati, da D4 si ha:
H1(H,2,3,4), qui D ha l'1 e B il 2, ed è l'unico possibile,
da D5 si ha solo H2(H,D,3,4)
da D6 si ha H3(H,2,D,4)
da D7 si ha H4(H,2,3,4)
da D8 si ha H5(H,D,3,4)
da D9 si ha H6(H,2,D,4)
considerando C adiacente a B, H e 2, si avrà:
da H1 si ha C1(H,2,C,4) e C2(H,2,3,C)
da H2 si ha C3(H,D,C,4) e C4(H,D,3,C)
da H3 si ha C5(H,2,C,4) e C6(H,2,D,C)
da H4 si ha C7(H,2,3,C) in H4 B ha il terzo colore che non può quindi andare a C
da H5 si ha C8(H,D,3,C)
da H6 non si può proseguire perchè deriva da D9 che deriva da B3 quindi tutti i posti sono occupati da zone adiacenti a C.
dovrei proseguire con la F ma avrei un totale di 24 scenari poco "interessanti" se permetti, per velocizzare un po', considero ora la M e poi la O
da C1 si ha M1(H,2,M,4)
da C2 si ha M2(H,2,M,C)
da C3 si ha M3(M,D,C,4) e M4(H,D,M,4)
da C4 si ha M5(M,D,3,C) e M6(H,D,M,4)
da C5 si ha M7(M,2,C,4)
da C6 si ha M8(M,2,D,C)
da C7 si ha M9(H,2,M,C)
da C8 si ha M10(H,D,M,C)
considero ora O adiacente a: D,M, 2, C.
da M1 si ha O1(H2M4)
da M2 non si può proseguire
da M3 si ha O2(M,D,C,O)
da M4 si ha O3(O,D,M,4) e O4(H,D,M,O)
da M5 si ha O5(M,D,O,C)
da M6 si ha O6(O,D,M,4)
da M7 si ha O7(M,2,C,O)
da M8 non si può proseguire
da M9 si ha O8(O,D,M,C)
ovviamente ogni scenario è corretto solo in quella "linea di discendenza" cioè scegliendo O7, il quarto colore lo posso dare ad O se rispetto i vari M7, C5, H3, D3, B1, nella linea di discendenza di O6 sarebbe impossibile perchè c'è C4 dove il quarto posto è occupato da C che è adiacente ad O.
poi si continua con le altre zone, ora il tempo stringe...
spero di essere stato più chiaro questa volta!
il punto è che il procedimento si basa proprio su colorazioni "ingenue" che poi verranno scartate proprio perchè non c'è uno studio a priori della mappa, ma si dimostra che per una successiva zona, tra le colorazioni ingenue almeno una non lo è, quindi anche se ho una mappa con 1000 zone, so già che alla 999-esima avrò un certo numero di colorazioni ingenue tra cui quella che mi consente di colorare la 1000-esima mappa.
considerando ogni successiva zona i passi da fare sono: considero il primo "scenario" della precedente zona, se è possibile scrivo un nuovo scenario "diiscendente" da quello, ponendo la nuova zona nelle posizioni "possibili" scrivendo n nuovi scenari possibili (da 1 a 3 perchè la zona è stata scelta adiacente ad almeno una). le posizioni "possibili" sono quelle dove in quel "ramo di discendenza" non risultano zone adiacenti. una volta scritti i nuovi scenari passo a considerare una nuova zona.
passiamo all'esempio.
procedo in ordine alfabetico perchè è la prima cosa che mi venuto in mente, avrei potuto sceglere dalla zona più a nord a quella più a sud, da quella più estesa a quella meno estesa, ma scelgo l'ordine alfabetico, ricordano le due condizioni (adiacente ad una già colorata e di "bordo") l'ordine reale è B, D, H, C, F, I, L, A, E, M, N, O, P, G, (altrimenti, ad esempio la P non sarebbe di bordo se la colorassi prima della G), ricordo che ogni "posto" tra le parentesi è il colore assegnato.
partenza(1,2,3,4), considero B adiacente a 4, avrò 3 possibili modi di assegnare i colori e risulterà:
B1(B,2,3,4), B2(1,B,3,4), B3(1,2,B,4)
considero D adiacente alla zona colorata col 4,
da B1 avrò: D1(D,2,3,4), D2(1,D,3,4), D3(1,2,D,4), da B2 e B3 si avranno le stesse colorazioni per D (D1=D4,D7; D2=D5,D8; D3=D6,D9), un totale di 9 possibili colorazioni perchè B e D sono "indipendenti".
consideriamo H adiacente a: B, 2, 3 e 4.
da D1, D2 e D3 è impossibile proseguire perchè non ci sono posti buoni per H e vengono quindi scartati, da D4 si ha:
H1(H,2,3,4), qui D ha l'1 e B il 2, ed è l'unico possibile,
da D5 si ha solo H2(H,D,3,4)
da D6 si ha H3(H,2,D,4)
da D7 si ha H4(H,2,3,4)
da D8 si ha H5(H,D,3,4)
da D9 si ha H6(H,2,D,4)
considerando C adiacente a B, H e 2, si avrà:
da H1 si ha C1(H,2,C,4) e C2(H,2,3,C)
da H2 si ha C3(H,D,C,4) e C4(H,D,3,C)
da H3 si ha C5(H,2,C,4) e C6(H,2,D,C)
da H4 si ha C7(H,2,3,C) in H4 B ha il terzo colore che non può quindi andare a C
da H5 si ha C8(H,D,3,C)
da H6 non si può proseguire perchè deriva da D9 che deriva da B3 quindi tutti i posti sono occupati da zone adiacenti a C.
dovrei proseguire con la F ma avrei un totale di 24 scenari poco "interessanti" se permetti, per velocizzare un po', considero ora la M e poi la O
da C1 si ha M1(H,2,M,4)
da C2 si ha M2(H,2,M,C)
da C3 si ha M3(M,D,C,4) e M4(H,D,M,4)
da C4 si ha M5(M,D,3,C) e M6(H,D,M,4)
da C5 si ha M7(M,2,C,4)
da C6 si ha M8(M,2,D,C)
da C7 si ha M9(H,2,M,C)
da C8 si ha M10(H,D,M,C)
considero ora O adiacente a: D,M, 2, C.
da M1 si ha O1(H2M4)
da M2 non si può proseguire
da M3 si ha O2(M,D,C,O)
da M4 si ha O3(O,D,M,4) e O4(H,D,M,O)
da M5 si ha O5(M,D,O,C)
da M6 si ha O6(O,D,M,4)
da M7 si ha O7(M,2,C,O)
da M8 non si può proseguire
da M9 si ha O8(O,D,M,C)
ovviamente ogni scenario è corretto solo in quella "linea di discendenza" cioè scegliendo O7, il quarto colore lo posso dare ad O se rispetto i vari M7, C5, H3, D3, B1, nella linea di discendenza di O6 sarebbe impossibile perchè c'è C4 dove il quarto posto è occupato da C che è adiacente ad O.
poi si continua con le altre zone, ora il tempo stringe...
spero di essere stato più chiaro questa volta!
ok, mi prendo qualche minuto e ti rispondo (per fortuna che ho la mattina libera!)
Intanto se uno fa dei passaggi ingenui non potrebbe dimostrare nulla in matematica...Cosa significa!?
penso che tu capisca cosa intendo. Nel corso del tuo algoritmo sei vincolato a basarti sulle zone gia' colorate quindi non hai una visione globale della mappa. Ne segue che ogni tua colorazione non univocamente determinata e' potenzialmente "ingenua".Mi sembra che tu stia risolvendo il caso particolare che ti ho proposto ragionando "globalmente". Chiaro che puoi fornire una colorazione corretta in modo che ogni volta le zone esterne siano colorate con al piu' tre colori (altrimenti il teorema dei quattro colori sarebbe falso), ma io sostengo che il tuo procedimento ha ben poco di algoritmico.
Ho indicato con le lettere da A a P le zone ancora da colorare. Ho colorato le quattro zone indicate coi numeri da 1 a 4. Ti chiederei di spiegarmi ora come procedi esattamente col tuo algoritmo per colorare la mappa. Quale zona scegli di colorare per prima, con che colore e perche'? Quale zona colori poi, con che colore e perche'? Eccetera. Ti ricordo che ogni scelta deve essere univoca e la sua motivazione ben precisa.
Ti ricordo inoltre che e' inutile che mi fornisci la colorazione corretta da sola, non me ne faccio niente: so che esiste
quello che voglio capire e' il tuo procedimento algoritmico.
"Rggb":
@martinof
Ho dato una scorsa, ma faccio un po' fatica a seguire il tuo metodo (anche se l'idea mi pare buona). Ci sono alcuni refusi, ma il punto debole del malloppoè che a volte non dimostri i passaggi cd. "autoevidenti", ma ti accontenti del "sembra vero" con uno schema grafico; devi essere più rigoroso, altrimenti una dimostrazione non è tale. Cercherò comunque di venirne a capo..
(tra l'altro era proprio il tipo d'aiuto che mi serviva) se mi dici quali punti ti sembrano "deboli" (anche se ho già qualche presentimento...) forse è la mia formazione da fisico che mi fa "sorvolare" su alcuni punti...
ho riletto ciò che hai scritto dandogli un'altra interpretazione, cioè uno può anche dare dei colori che poi risultano "sbagliati" ma tra quelli che ha dato c'è anche quello che "contemporaneamente" a tutte le altre zone è giusto, è più o meno quello che dicevo quando parlavo del fatto che poi "alcuni scenari" sarebbero diventati (dopo aver considerato altre zone) impossibili, proprio perchè si procede in modo del tutto arbitrario...
Intanto se uno fa dei passaggi ingenui non potrebbe dimostrare nulla in matematica...
Comunque la cosa che si nota per le tre zone piccole da colorare è che delle "piccole" quella più in basso non può,in nessun modo, essere adiacente alla zona colorata con 1, mentre la più grande di tutte non può essere adiacente a quella colorata col 3, le tre due più piccole dall'alto in basso rispettivamente 2 ed 1, come puoi notare le zone più esterne mantengono solo tre colori. se vuoi che la prima zona a cui ho dato 1 (quella vicino al 3) sia esterna, tentando di avere 4 colori "esterni", allora devi ammettere che l'ulima zona 3 (che le ho assegnato io) non è più adiacente alla 4 e può quindi prendere quel colore continuando ad avere solo 3 colori "esterni"
il fatto di colorare una zona confinante col massimo numero di zone già colorate non è necessario, ma serve solo per "velocizzare" la colorazione.
se poi ci sono più alternative per colorare la mappa credo sia un "bene", o non ho capito ciò che hai scritto.
Comunque la cosa che si nota per le tre zone piccole da colorare è che delle "piccole" quella più in basso non può,in nessun modo, essere adiacente alla zona colorata con 1, mentre la più grande di tutte non può essere adiacente a quella colorata col 3, le tre due più piccole dall'alto in basso rispettivamente 2 ed 1, come puoi notare le zone più esterne mantengono solo tre colori. se vuoi che la prima zona a cui ho dato 1 (quella vicino al 3) sia esterna, tentando di avere 4 colori "esterni", allora devi ammettere che l'ulima zona 3 (che le ho assegnato io) non è più adiacente alla 4 e può quindi prendere quel colore continuando ad avere solo 3 colori "esterni"
il fatto di colorare una zona confinante col massimo numero di zone già colorate non è necessario, ma serve solo per "velocizzare" la colorazione.
se poi ci sono più alternative per colorare la mappa credo sia un "bene", o non ho capito ciò che hai scritto.
Mi sembra di capire che tu affermi di poter colorare una mappa partendo da una zona "centrale" che consiste di quattro zone mutuamente confinanti in modo tale che ogni volta le zone esterne siano colorate con al piu' tre colori. Ma fatico a capire come la cosa possa essere algoritmica. Considera la figura seguente per esempio.
Qui se uno ingenuamente colora prima le tre zone piccole (delle quattro non ancora colorate) basandosi solo su quello che ha gia' colorato puo' incorrere in un errore. E non credo nemmeno che si possa decidere di colorare ogni volta una zona confinante col massimo numero di zone gia' colorate, perche' ci possono essere piu' scelte a priori tutte valide.
Attendo riscontro prima di argomentare ancora.
Qui se uno ingenuamente colora prima le tre zone piccole (delle quattro non ancora colorate) basandosi solo su quello che ha gia' colorato puo' incorrere in un errore. E non credo nemmeno che si possa decidere di colorare ogni volta una zona confinante col massimo numero di zone gia' colorate, perche' ci possono essere piu' scelte a priori tutte valide.
Attendo riscontro prima di argomentare ancora.
@martinof
Ho dato una scorsa, ma faccio un po' fatica a seguire il tuo metodo (anche se l'idea mi pare buona). Ci sono alcuni refusi, ma il punto debole del malloppo è che a volte non dimostri i passaggi cd. "autoevidenti", ma ti accontenti del "sembra vero" con uno schema grafico; devi essere più rigoroso, altrimenti una dimostrazione non è tale. Cercherò comunque di venirne a capo..
@Martino
Credo di averlo un po' aizzato io perché quel che diceva mi aveva incuriosito.
https://www.matematicamente.it/forum/ma- ... 51290.html
Ho dato una scorsa, ma faccio un po' fatica a seguire il tuo metodo (anche se l'idea mi pare buona). Ci sono alcuni refusi, ma il punto debole del malloppo
è che a volte non dimostri i passaggi cd. "autoevidenti", ma ti accontenti del "sembra vero" con uno schema grafico; devi essere più rigoroso, altrimenti una dimostrazione non è tale. Cercherò comunque di venirne a capo..@Martino
Credo di averlo un po' aizzato io
perché quel che diceva mi aveva incuriosito.https://www.matematicamente.it/forum/ma- ... 51290.html
hai dimenticato "centinaia tra le più eccelse menti matematiche"...
scherzi a parte, si tratta solo di un'altro punto di vista, tutto qui.
buona lettura, omonimo!
scherzi a parte, si tratta solo di un'altro punto di vista, tutto qui.
buona lettura, omonimo!
"martinof":Ah ma per "pubblicarla" intendevi qui nel forum
per la dimostrazione dovrei riuscire a pubblicarla entro domani
Interessante che tu dica di essere riuscito a risolvere un problema a cui hanno pensato un centinaio d'anni e che non sono riusciti a risolvere senza l'ausilio del computer. Daro' un'occhiata alla tua dimostrazione.
se me ne proponi qualcuna sarò lieto di inviarla li, visto che come mi è giustamente fatto notare non è questo il posto per proporre dimostrazioni.
ringrazio anticipatamente.
ringrazio anticipatamente.
"martinof":
per la dimostrazione dovrei riuscire a pubblicarla entro domani
Accettata da qualche rivista?
Quale, nel caso?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo