Kuratowski ed il teorema dei 4 colori

Domande di teoria, mini-dispense degli utenti, richieste di riferimenti ad articoli, ...

Moderatore: Moderatori

Kuratowski ed il teorema dei 4 colori

Messaggioda Endomorfismo il mar 6 mar 2012, 18:47

Vorrei scrivere un messaggio in Combinatoria, ma visto che non mi è concesso lo posto qui. A causa della mia incompetenza, il teorema dei quattro colori non mi sembra altro che un banale corollario del teorema di Kuratowski; ma se fosse vero non avrebbe bisogno di una dimostrazione a parte. Qualcuno sarebbe così gentile da tentare di far capire perché non lo è?
Endomorfismo
 
Messaggi: 19
Iscritto il: sab 3 mar 2012, 16:26
Località: Una causalmente connessa con la tua

Messaggioda salvo.tringali il mar 6 mar 2012, 18:49

Endomorfismo ha scritto:Vorrei scrivere un messaggio in Combinatoria, ma visto che non mi è concesso lo posto qui. A causa della mia incompetenza, il teorema dei quattro colori non mi sembra altro che un banale corollario del teorema di Kuratowski [...]

Kuratowski ha dimostrato dozzine di teoremi fondamentali: a quale dei tanti ti riferisci?
"Che bella storia", disse l'Alchimista. | Whatever can be encoded by syntax shouldn't be left to semantics. | Homomorphisms are to algebraic structures as seminorms are to ordered structures.
Avatar utente
salvo.tringali
 
Messaggi: 5354
Iscritto il: mar 17 giu 2008, 19:46
Località: Karl-Franzens-Universität, Graz (AT)

Messaggioda Endomorfismo il mar 6 mar 2012, 18:56

salvo.tringali ha scritto:Kuratowski ha dimostrato dozzine di teoremi fondamentali: a quale dei tanti ti riferisci?

Quello che dice che un grafo è planare se e solo se non contiene alcun sottografo che sia un'espansione di \,K_5 o un'espansione di K_{3,3},.
Endomorfismo
 
Messaggi: 19
Iscritto il: sab 3 mar 2012, 16:26
Località: Una causalmente connessa con la tua

Messaggioda hydro il mar 6 mar 2012, 20:31

ci potresti anche dire cosa sono K_5 e K_{3,3} e che cosa si intende per espansione di un grafo?
hydro
 
Messaggi: 435
Iscritto il: mer 1 apr 2009, 9:40

Messaggioda Endomorfismo il mer 7 mar 2012, 9:35

hydro ha scritto:ci potresti anche dire cosa sono K_5 e K_{3,3} e che cosa si intende per espansione di un grafo?

Grafo K_5:
Immagine
Grafo K_{3,3}:
Immagine.
Un grafo si espande inserendo un nuovo nodo in un arco e spezzandolo in due.

Una violazione del teorema dei quattro colori dovrebbe portare, prendendo un punto all'interno di ogni regione e congiungendo quelli delle regioni confinanti, ad una violazione di questo teorema di Kuratowski. :|
Endomorfismo
 
Messaggi: 19
Iscritto il: sab 3 mar 2012, 16:26
Località: Una causalmente connessa con la tua

Messaggioda hydro il mer 7 mar 2012, 10:38

Uhmm... messa così non dice molto... se vuoi un parere matematico su questa possibile dimostrazione dovresti formularla nel linguaggio opportuno...
hydro
 
Messaggi: 435
Iscritto il: mer 1 apr 2009, 9:40

Messaggioda Endomorfismo il mer 7 mar 2012, 12:17

hydro ha scritto:Uhmm... messa così non dice molto... se vuoi un parere matematico su questa possibile dimostrazione dovresti formularla nel linguaggio opportuno...

Con la licenza media? :( Vediamo: individuiamo dei punti all'interno di ogni regione (uno e uno solo per ogni regione) e generiamo un grafo collegando tra loro i punti corrispondenti a regioni nella mappa. Il grafo dev'essere planare, perché se le regioni confinano esiste un cammino che colleghi i due punti senza intersecare altri collegamenti. Dal teorema dei quattro colori deriva che un punto connesso a due punti tra loro connessi non può essere connesso con più di altri due punti connessi con entrambi i due punti collegati di partenza, e che in ogni caso questi due punti non possono essere collegati tra loro con uno spigolo. Se mi raffiguro mentalmente queste due situazioni, ottengo i due grafi di cui sopra. Sapendo che non possono essere planari, mi sembra che non serva altro per verificare il teorema dei quattro colori.
Endomorfismo
 
Messaggi: 19
Iscritto il: sab 3 mar 2012, 16:26
Località: Una causalmente connessa con la tua

Messaggioda hydro il mer 7 mar 2012, 14:35

Endomorfismo ha scritto:
hydro ha scritto:Uhmm... messa così non dice molto... se vuoi un parere matematico su questa possibile dimostrazione dovresti formularla nel linguaggio opportuno...

Con la licenza media? :( Vediamo: individuiamo dei punti all'interno di ogni regione (uno e uno solo per ogni regione) e generiamo un grafo collegando tra loro i punti corrispondenti a regioni nella mappa. Il grafo dev'essere planare, perché se le regioni confinano esiste un cammino che colleghi i due punti senza intersecare altri collegamenti. Dal teorema dei quattro colori deriva che un punto connesso a due punti tra loro connessi non può essere connesso con più di altri due punti connessi con entrambi i due punti collegati di partenza, e che in ogni caso questi due punti non possono essere collegati tra loro con uno spigolo. Se mi raffiguro mentalmente queste due situazioni, ottengo i due grafi di cui sopra. Sapendo che non possono essere planari, mi sembra che non serva altro per verificare il teorema dei quattro colori.


Al di la' del fatto che non ho capito il tuo ragionamento, mi puzza il fatto che a meta' tu dica "dal teorema dei quattro colori segue...". Se vuoi dimostrarlo, certo non lo puoi assumere come ipotesi! Se invece vuoi ragionare per assurdo, allora dovrei leggere qualcosa del tipo:
"supponiamo che il teorema dei quattro colori sia falso. Allora esiste un grafo planare che non e' 4-colorabile. Quindi..."
Ed infine, stando a quanto dice wikipedia perche' e' un argomento di cui non so nulla, ogni grafo ottenuto mettendo un vertice per ogni regione ed uno spigolo per ogni coppia di vertici corrispondenti a regioni adiacenti e' automaticamente planare, quindi non vedo proprio come potresti usare questo teorema di Kuratowski. Ma magari non ho capito bene io.
hydro
 
Messaggi: 435
Iscritto il: mer 1 apr 2009, 9:40

Messaggioda Endomorfismo il mer 7 mar 2012, 18:58

Scusa, riformulo.
Supponiamo che il teorema dei quattro colori sia falso. Allora esiste un grafo planare che non è 4-colorabile. Quindi, in questo grafo, ci sarebbe un punto A connesso sia con due punti B e C tra loro connessi, sia con almeno tre punti connessi con B e C, oppure con almeno due punti D ed E connessi con B e C e tra di loro. Avremmo quindi un grafo planare contenente K_{3,3} (primo caso) o K_5 (secondo caso), violando il teorema di Kuratowski.
Endomorfismo
 
Messaggi: 19
Iscritto il: sab 3 mar 2012, 16:26
Località: Una causalmente connessa con la tua

Messaggioda hydro il mer 7 mar 2012, 22:16

Endomorfismo ha scritto:Scusa, riformulo.
Supponiamo che il teorema dei quattro colori sia falso. Allora esiste un grafo planare che non è 4-colorabile. Quindi, in questo grafo, ci sarebbe un punto A connesso sia con due punti B e C tra loro connessi, sia con almeno tre punti connessi con B e C, oppure con almeno due punti D ed E connessi con B e C e tra di loro.


Questo passaggio non è per nulla chiaro (almeno per me). Come fai a dimostrare che dal fatto che non esista nessuna 4-colorazione segue necessariamente una di queste 2 situazioni?
hydro
 
Messaggi: 435
Iscritto il: mer 1 apr 2009, 9:40

Prossimo

Torna a Teoria

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite

cron