Ma vale come dimostrazione?

martinof
premetto che non sono un matematico (ma studio fisica), in breve i fatti sono questi:
qualche tempo fa mi sono imbatutto nel teorema dei quattro colori (credo che tutti qui sappano di cosa sto parlando, quindi non lo enuncio) ed incuriosito dal fatto che è tanto semplice l'enunciato quant'è complicata la dimostrazione, mi sono messo alla ricerca di una dimostrazione più semplice.
dopo qualche tempo (e notti insonni) ho trovato una pseudo-dimostrazione, da cui ho ricavato un metodo per colorare correttamente le mappe.
ora vi chiedo, visto che il metodo di colorazione ricavato dalla dimostrazione ottengo una colorazione corretta, la dimostrazione è valida?
grazie a chi vorrà rispondere.

Risposte
martinof
c'è un però...
visto che sono giunto alle mie conclusioni senza l'utilizzo della teoria dei grafi, può anche darsi che la teoria dei grafi non sia sufficiente per "tradurre" il tutto, ma non voglio peccare di presunzione, sono convinto comunque che si tratta solo di chiamare le stesse cose con nomi diversi.

se io chiamo "punto" quello che può essere chiamato "nodo", "vertice" o in qualunque altro modo, credo che una volta mostrato con un disegno quello che voglio dire, starà ad ogniuno "vederlo" com'è abituato a vedere le cose, nel senso che, per chi conosce la teoria dei grafi, sarà un "nodo", per chi non la conosce, sarà un punto, l'importante è che si dimostri, ad esempio, che quel punto potrà appartenere solo a quelle che io chiamo "linee di confine" che delimitano, al massimo, 3 regioni ogniuna confinante con le altre due, e se in quel punto passeranno altri "confini" le regioni delimitate da quelle linee non potranno essere tutte confinanti tra loro.

poi è ovvio che, se una volta che avrò mostrato tutta la dimostrazione, qualcuno mi dice: "guarda hai fatto un lavoro inutile perchè queste cose qui le potevi dire così, e queste altre in quest'altro modo", io sarò ben felice di imparare qualcosa di nuovo.

Rggb1
"martinof":
potrei studiarla, è vero (ma oltre al lavoro, 2 figli, la meccanica quantistica da studiare, gli esami da preparare devo anche mangiare e dormire), non so proprio dove trovare il tempo...

Come ti capisco, anche se dovrei sostituire il termine "meccanica quantistica" con qualcos'altro :-D
Fatti vivo appena puoi.

martinof
il problema di usare la teoria dei grafi è che non la conosco così bene da poterla usare con "disinvoltura", quindi mi riconduco ad un linguaggio più terra terra, potrei studiarla, è vero (ma oltre al lavoro, 2 figli, la meccanica quantistica da studiare, gli esami da preparare devo anche mangiare e dormire), non so proprio dove trovare il tempo...
magari, una volta fatte le figure, sarà più facile capirsi e tradurre il tutto in un linguaggio più matematico...

Rggb1
Ti ci sei buttato a capofitto, eh? ;)
"martinof":
il teorema dei quattro colori.
brevemente si enuncia dicendo che, per colorare una qualunque mappa geografica, volendo assegnare ad ogni stato un colore, sono sufficienti solo 4 colori, con un paio di logiche limitazioni (due stati si considerano adiacenti solo se hanno un tratto di confine in comune e non solo punti; i territori di ogni stato dovranno essere tutti all'interno del “confine”). è vero che uno stato può confinare con molti altri stati, pensando ad una torta divisa a spicchi con un cerchio al centro, ovviamente questo può confinare con un numero qualsiasi di spicchi, ma questi non saranno tutti confinanti tra loro.

Cerca di passare ad un linguaggio più matematico. Suggerimento: usa la teoria dei grafi.
"martinof":
-il primo è quello di “gruppo d'adiacenza”, definito come l'insieme degli stati tra loro tutti confinanti, nell'esempio della torta un “gruppo” sarà formato dallo stato centrale e due soli spicchi alla volta, perché prendendo un terzo spicchio, non sarà adiacente agli altri due, ma solo ad uno, e formerà un altro “gruppo” con lo stato centrale e questo spicchio. si avrà che lo “stato” centrale apparterrà a tutti i “gruppi” e che ogni spicchio apparterrà a due gruppi.

Ovvero: tutti i sottografi connessi (di almeno due nodi?) in cui ogni cammino da qualunque nodo a qualunque altro è dato da un solo lato.
[la notazione è con nodi e lati, equivalente a qualunque altra, anche alla più usata con vertici e spigoli]
"martinof":
-il secondo concetto è quello di “livello rispetto ad uno stato”, definito come l'insieme di tutti gli stati confinanti con uno stato di riferimento, nell'esempio della torta, rispetto lo stato centrale, sono tutti gli spicchi; rispetto ad uno spicchio, sono solo i due spicchi “vicini” ed il cerchio centrale.

Ovvero tutti i sottografi connessi che contengano un dato nodo e tutti i nodi ad esso adiacenti, ho capito bene? Noto adesso, riscrivendo, che la caratteristica di essere connessi è implicita nelle due definizioni.
"martinof":
Se il colore di uno stato è vincolato a quello degli stati confinanti si sottintende che alcuni stati siano già colorati, quindi si assume che: data una mappa da colorare (in bianco) assegnando ad uno e solo uno stato un colore, la mappa sarà correttamente colorata (e qui non ci dovrebbero esser problemi, per assurdo, se quella colorazione non fosse corretta, dovrebbe esistere uno stato confinante colorato con lo stesso colore, ma per ipotesi lo stato colorato è solo uno, dunque la colorazione è ammissibile).

Lascia perdere le configurazioni iniziali, si può sempre eliminare questa condizione.
"martinof":
nella dimostrazione vengono formulati e dimostrati una serie di teoremi (11, ma sto cercando di accorparne qualcuno) sulle proprietà dei "gruppi", "livelli", "linee di confine" e "punti d'unione", e che conducono alla dimostrazione del teorema dei 4 colori.

spero di non essere stato troppo lungo...

No no. :-D
Comunque, se puoi astrarre i tuoi concetti come ti ho detto credo tu possa fare a meno di tante cose che cerchi di dimostrare.

Fammi sapere, decisamente mi hai incuriosito :)

martinof
"blackbishop13":

perchè dici cose come "voi matematici" neanche fossi un ingegnere... :D

:-D

ovviamente, io sono sicuro del fatto che la dimostrazione è corretta e da questa ho ricavato un algoritmo che funziona sempre, quindi anche con una mappa da 39848 stati.

sul fatto di condividerla, dovrei fare le figure al computer ma all'incirca è una cosa del genere:

il teorema dei quattro colori.
brevemente si enuncia dicendo che, per colorare una qualunque mappa geografica, volendo assegnare ad ogni stato un colore, sono sufficienti solo 4 colori, con un paio di logiche limitazioni (due stati si considerano adiacenti solo se hanno un tratto di confine in comune e non solo punti; i territori di ogni stato dovranno essere tutti all'interno del “confine”). è vero che uno stato può confinare con molti altri stati, pensando ad una torta divisa a spicchi con un cerchio al centro, ovviamente questo può confinare con un numero qualsiasi di spicchi, ma questi non saranno tutti confinanti tra loro.

nella mia dimostrazione la linea di principio generale che si segue è: il colore di uno stato dipende da quello degli stati confinanti, ma anche questi dovranno dipendere da quelli degli stati con loro confinanti e così via, devo quindi avere una visione d'insieme di carattere generale.
la visione d'insieme, la ricavo introducendo due concetti,

-il primo è quello di “gruppo d'adiacenza”, definito come l'insieme degli stati tra loro tutti confinanti, nell'esempio della torta un “gruppo” sarà formato dallo stato centrale e due soli spicchi alla volta, perché prendendo un terzo spicchio, non sarà adiacente agli altri due, ma solo ad uno, e formerà un altro “gruppo” con lo stato centrale e questo spicchio. si avrà che lo “stato” centrale apparterrà a tutti i “gruppi” e che ogni spicchio apparterrà a due gruppi.

-il secondo concetto è quello di “livello rispetto ad uno stato”, definito come l'insieme di tutti gli stati confinanti con uno stato di riferimento, nell'esempio della torta, rispetto lo stato centrale, sono tutti gli spicchi; rispetto ad uno spicchio, sono solo i due spicchi “vicini” ed il cerchio centrale.

Se il colore di uno stato è vincolato a quello degli stati confinanti si sottintende che alcuni stati siano già colorati, quindi si assume che: data una mappa da colorare (in bianco) assegnando ad uno e solo uno stato un colore, la mappa sarà correttamente colorata (e qui non ci dovrebbero esser problemi, per assurdo, se quella colorazione non fosse corretta, dovrebbe esistere uno stato confinante colorato con lo stesso colore, ma per ipotesi lo stato colorato è solo uno, dunque la colorazione è ammissibile).
in particolare, si ha che lo stato da scegliere come inizio della colorazione, non dovrà avere alcuna particolare proprietà o caratteristica.

-una volta colorato uno stato, si dimostra che tutti gli stati con questo confinanti (quelli che appartengono al "livello rispetto quello stato"), sono colorabili con al massimo 3 diversi colori da quello assegnato al primo stato (anche se con molteplicità diversa da 1), cioè utilizzando in totale 4 diversi colori.

-una volta colorati tutti gli stati adiacenti al primo, si dimostra che, per qualunque altro stato adiacente ad uno di quelli già colorati, non sarà possibile utilizzare, al massimo tre dei colori già utilizzati (il caso più semplice è uno stato che confina con tre stati con colori diversi, per ipotesi non confina col primo stato colorato -altrimenti sarebbe già colorato- e gli si può quindi assegnare lo stesso colore).

sarebbe facile, a questo punto, chiede di che colore dovrebbe essere colorato uno stato che confini anch'esso con quest'ultimo ed i tre già colorati con colori diversi, ma un punto importante della dimostrazione sono le proprietà dei "gruppi d'adiacenza" (nella dimostrazione ho usato una nomenclatura più generale stati=zone, colori=numeri) ed in particolare delle zone chiamate “z.c.”, ovvero “zone circondate”.

si dimostra infatti che, il caso in cui una zona possa essere colorata con un solo colore, implica che si configura un "gruppo" formato da 4 zone, ma questo implicherà a sua volta che, almeno una di queste non potrà confinare con altre zone, sarà cioè completamente circondata dalle tre e non può quindi appartenere ad altri gruppi (a meno di un caso particolare, che comunque non inefficacia la dimostrazione).

nella dimostrazione ci si serve di altri due concetti, ovvero della "linea di confine" (l'immaginaria recinzione di ogni stato) e dei "punti d'unione" (le linee di confine di due stati confinanti dovranno essere sovrapposte per un tratto e poi si separeranno definendo così due punti) e le loro proprietà.

nella dimostrazione vengono formulati e dimostrati una serie di teoremi (11, ma sto cercando di accorparne qualcuno) sulle proprietà dei "gruppi", "livelli", "linee di confine" e "punti d'unione", e che conducono alla dimostrazione del teorema dei 4 colori.

spero di non essere stato troppo lungo...

Raptorista1
Non credo esista un matematico in gradi di dirti se la tua dimostrazione è corretta... Se prima non la condividi anche con lui! :-D

Potresti risolvere i tuoi (ed anche i nostri) dubbi facendoci vedere la tua dimostrazione!

"blackbishop13":

Perché dici cose come "voi matematici" neanche fossi un ingegnere... :D


Ma questi flame gratuiti?? :-D

blackbishop13
Scusa ma tu studi fisica, quindi dovresti avere idea di cos'è una dimostrazione, e sapere che differenza c'è tra: ho provato qualche caso e funziona e sono sicuro che funziona sempre!

perchè dici cose come "voi matematici" neanche fossi un ingegnere... :D

comunque non si capisce bene, tu vuoi dire che hai trovato un algoritmo che ti permette effettivamente di colorare la mappa?
ma allora con una mappa di 39848 stati dovremmo aspettare qualche anno per vedere che funziona?

oppure sei sicuro che funzioni, e sapresti dimostrarlo?

martinof
"Rggb":
[quote="martinof"]tornando alla dimostrazione, ho trovato che "data una qualsiasi mappa" la coloro correttamente

Trovato ovverosia calcolato, oppure dimostrato? E' forse migliore di questa?
http://people.math.gatech.edu/~thomas/FC/fourcolor.html[/quote]
nella mia seguo un percorso diverso, cioè dimostro che, data una qualunque mappa da colorare e 4 colori, esiste sempre almeno un colore col quale colorare uno "stato", da li ricavo l'algoritmo di colorazione.
con una mappoa con una ventina di regioni ci vuole circa 15 minuti a mano

Rggb1
"martinof":
tornando alla dimostrazione, ho trovato che "data una qualsiasi mappa" la coloro correttamente

Trovato ovverosia calcolato, oppure dimostrato? E' forse migliore di questa?
http://people.math.gatech.edu/~thomas/FC/fourcolor.html

martinof
"Rggb":
[quote="martinof"]dopo qualche tempo (e notti insonni) ho trovato una pseudo-dimostrazione, da cui ho ricavato un metodo per colorare correttamente le mappe.
ora vi chiedo, visto che il metodo di colorazione ricavato dalla dimostrazione ottengo una colorazione corretta, la dimostrazione è valida?

Ni. Se è corretta NON significa automaticamente che lo sia sempre. Devi dimostrare che il risultato è sempre corretto per qualunque configurazione.
A proposito, che vuol dire "pseudo-dimostrazione"?[/quote]
"pseudo" perchè poi, voi matematici, dite che non è una vera dimostrazione... diciamo che ho "messo le mani avanti"!
tornando alla dimostrazione, ho trovato che "data una qualsiasi mappa" la coloro correttamente

Rggb1
"martinof":
dopo qualche tempo (e notti insonni) ho trovato una pseudo-dimostrazione, da cui ho ricavato un metodo per colorare correttamente le mappe.
ora vi chiedo, visto che il metodo di colorazione ricavato dalla dimostrazione ottengo una colorazione corretta, la dimostrazione è valida?

Ni. Se è corretta NON significa automaticamente che lo sia sempre. Devi dimostrare che il risultato è sempre corretto per qualunque configurazione.
A proposito, che vuol dire "pseudo-dimostrazione"?

martinof
significa che mi sono inventato una serie di mappe e funziona con tutte

alvinlee881
"martinof":

ora vi chiedo, visto che il metodo di colorazione ricavato dalla dimostrazione ottengo una colorazione corretta, la dimostrazione è corretta?

Cosa significa? Che hai dimostrato che il tuo algoritmo di colorazione funziona su qualsiasi mappa o lo hai testato su tutte le mappe (la vedo dura...)?

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.