Teoria dei grafi
Il problema dei quattro colori consiste nel colorare una qualsiasi carta geografica utilizzando soltanto quattro colori in modo tale che due generiche nazioni confinanti non abbiano mai lo stesso colore.
(negli studi compiuti a riguardo da Apel e Haken nel 1976, sono state messe in evidenza 1936 configurazioni critiche (una sorta di ipotetiche trappole o situazioni non desiderate), per le quali sono state impiegate 1200 ore di elaborazione con un calcolatore per dimostrare che in realtà ogni situazione critica può essere risolta con quattro colori)
Ipotizziamo ora di avere a che fare con volumi e non con superfici:
quanti colori sono necessari per riempire i volumi di solidi di forma casuale in modo tale che nessun solido sia mai adiacente ad un solido riempito dello stesso colore?
(negli studi compiuti a riguardo da Apel e Haken nel 1976, sono state messe in evidenza 1936 configurazioni critiche (una sorta di ipotetiche trappole o situazioni non desiderate), per le quali sono state impiegate 1200 ore di elaborazione con un calcolatore per dimostrare che in realtà ogni situazione critica può essere risolta con quattro colori)
Ipotizziamo ora di avere a che fare con volumi e non con superfici:
quanti colori sono necessari per riempire i volumi di solidi di forma casuale in modo tale che nessun solido sia mai adiacente ad un solido riempito dello stesso colore?
Risposte
per caso tu hai già una risposta? Non occorre ch me la dici, dimmi solo se hai già risolto il problema o se ci stai ancora pensando anche tu . . .
"La statistica è quella scienza che dice che se hai la testa nel congelatore e i piedi nel forno, mediamente stai bene"
"La statistica è quella scienza che dice che se hai la testa nel congelatore e i piedi nel forno, mediamente stai bene"
Potrei tirarne a indovinare almeno quattro di soluzioni senza la benchè minima dimostrazione ovviamente, è un problema fuori dalla mia portata
Per i solidi non c'è una limitazione superiore valida per qualsiasi configurazione possibile.
Infatti, per ogni n>0 è facile ideare una configurazione fatta di n solidi, ognuno dei quali ha un "peduncolo" che tocca tutti gli altri n-1 solidi. Per tale configurazione i solidi devono essere tutti di colori diversi.
Infatti, per ogni n>0 è facile ideare una configurazione fatta di n solidi, ognuno dei quali ha un "peduncolo" che tocca tutti gli altri n-1 solidi. Per tale configurazione i solidi devono essere tutti di colori diversi.
Mi sa che mi hai convinto, anche se ci vuole troppa capicità di astrazione, ci vorrebbero delle simulazioni con grafica 3d, comunque mi pare di riuscire ad immaginare quello che hai descritto.
1) Ipotizziamo ora di poter utilizzare un'unica figura geometrica invece che un numero imprecisato per riempire il piano dei grafi 2d, quale figura è compatibile con la teoria dei grafi 2d?
2) Correggo il problema dei grafi 3d, ipotizzando di poter utilizzare un'unica forma solida per saturare lo spazio, quanti colori sono necessari per riempire i volumi di tutti i solidi in modo tale che nessun solido sia mai adiacente ad un solido riempito dello stesso colore?
PS
Non sono quesiti tanto per fare, credo che le relative risposte abbiano delle implicazioni nel determinare le possibili configurazioni delle strutture atomiche e sub atomiche.
1) Ipotizziamo ora di poter utilizzare un'unica figura geometrica invece che un numero imprecisato per riempire il piano dei grafi 2d, quale figura è compatibile con la teoria dei grafi 2d?
2) Correggo il problema dei grafi 3d, ipotizzando di poter utilizzare un'unica forma solida per saturare lo spazio, quanti colori sono necessari per riempire i volumi di tutti i solidi in modo tale che nessun solido sia mai adiacente ad un solido riempito dello stesso colore?
PS
Non sono quesiti tanto per fare, credo che le relative risposte abbiano delle implicazioni nel determinare le possibili configurazioni delle strutture atomiche e sub atomiche.
citazione:
Per i solidi non c'è una limitazione superiore valida per qualsiasi configurazione possibile.
Infatti, per ogni n>0 è facile ideare una configurazione fatta di n solidi, ognuno dei quali ha un "peduncolo" che tocca tutti gli altri n-1 solidi. Per tale configurazione i solidi devono essere tutti di colori diversi.
Forse non ho ben capito la tua riflessione, pero' faccio presente che anche su un piano e' possibile ideare una configurrazione in cui n regioni si tocchino tutte le une con le altre. Il problema dei quattro colri, infatti, e' generale, e vale per qualunque configurazione immaginabile (anche inserendo confini curvi, che assicurano tutti i collegamenti se vuoi). Ora, dato che se rispondi a questo post si presume che tu conosca il teorema e la sua soluzione, non capisco proprio la tua affermazione . . .
Con simpatia
"La statistica è quella scienza che dice che se hai la testa nel congelatore e i piedi nel forno, mediamente stai bene"
citazione:
1) Ipotizziamo ora di poter utilizzare un'unica figura geometrica invece che un numero imprecisato per riempire il piano dei grafi 2d, quale figura è compatibile con la teoria dei grafi 2d?
2) Correggo il problema dei grafi 3d, ipotizzando di poter utilizzare un'unica forma solida per saturare lo spazio, quanti colori sono necessari per riempire i volumi di tutti i solidi in modo tale che nessun solido sia mai adiacente ad un solido riempito dello stesso colore?
PS
Non sono quesiti tanto per fare, credo che le relative risposte abbiano delle implicazioni nel determinare le possibili configurazioni delle strutture atomiche e sub atomiche.
In questo caso, invece, non riesco a capire, caro Cannigo, cosa chiedi. Ti pregherei di ripetere la tua ipotesi per la mia striminzita mente, perche' non ne ho compreso il senso. Una unica figura geomentrica per fare cosa? E cosa vuol dire "figura compatibile con la teoria dei grafi"? Ogni figura piana e' compatibile con la teoria dei grafi, se essa ha almeno due vertici e uno spigolo che li congiunge...
Ed inoltre non capisco il riferimento alla "teoria dei grafi 3D" . . . per definizione, una grafo e' una rappesentazione piana . . . forse ti riferisci al "problema dei colori" 3D, ma non e' la stessa cosa!!!! Ti prego di chiarire i miei dubbi, e dirmi qual'e' lo scopo della tua riflessione. Grazie e ciao!
"La statistica è quella scienza che dice che se hai la testa nel congelatore e i piedi nel forno, mediamente stai bene"
Rispondo prima al posto di abell:
Immaginiamo una configurazione di volumi cubici, tutti uguali, sono sufficienti due colori per far sì che colori uguali non entrino a contatto. Ora ipotizziamo che un vermone cominci a scavare una galleria che collega più cubi, il volume della galleria a questo punto dovrebbe essere riempito di un terzo colore e ogni volta che si aggiunge una galleria che interseca la galleria precedente ci vuole un ulteriore colore, non vale lo stesso discorso in uno schema bidimensionale in quanto la "galleria" sarebbe un "guado" o un attraversamento che dividerebbe in due un Grafo e quindi una delle due metà potrebbe cambiare colore...
PS
E' stata una lotta
Modificato da - cannigo il 16/02/2004 18:15:59
Immaginiamo una configurazione di volumi cubici, tutti uguali, sono sufficienti due colori per far sì che colori uguali non entrino a contatto. Ora ipotizziamo che un vermone cominci a scavare una galleria che collega più cubi, il volume della galleria a questo punto dovrebbe essere riempito di un terzo colore e ogni volta che si aggiunge una galleria che interseca la galleria precedente ci vuole un ulteriore colore, non vale lo stesso discorso in uno schema bidimensionale in quanto la "galleria" sarebbe un "guado" o un attraversamento che dividerebbe in due un Grafo e quindi una delle due metà potrebbe cambiare colore...
PS
E' stata una lotta
Modificato da - cannigo il 16/02/2004 18:15:59
citazione:
Una unica figura geomentrica per fare cosa? E cosa vuol dire "figura compatibile con la teoria dei grafi"? Ogni figura piana e' compatibile con la teoria dei grafi, se essa ha almeno due vertici e uno spigolo che li congiunge...
Intendo dire: immaginando di dover suddividere un piano in poligoni tutti uguali tra loro ma che necessitino di quattro colori per mantenere l'alternanza dei colori (es: una scacchiera necessita di soli due colori per mantenere l'alternanza e quindi non mi va bene per confermare la teoria dei quattro colori).
citazione:
Ed inoltre non capisco il riferimento alla "teoria dei grafi 3D" . . . per definizione, una grafo e' una rappesentazione piana . . . forse ti riferisci al "problema dei colori" 3D, ma non e' la stessa cosa!!!! Ti prego di chiarire i miei dubbi, e dirmi qual'e' lo scopo della tua riflessione. Grazie e ciao!
Chiamalo come vuoi il problema, per me grafo 3d rende l'idea.
citazione:
"La statistica è quella scienza che dice che se hai la testa nel congelatore e i piedi nel forno, mediamente stai bene"
'Sta cosa l'abbiamo capita:-)
ok Cannigo, adesso ho capito cosa intendi, e ci pensero'.
L'ultima e' la mia "firma" che si inserisce ad ogni post che invio. Ognuno di voi puo' farsela. Se rompe le scatole la tolgo.
CIAO!
"La statistica è quella scienza che dice che se hai la testa nel congelatore e i piedi nel forno, mediamente stai bene"
L'ultima e' la mia "firma" che si inserisce ad ogni post che invio. Ognuno di voi puo' farsela. Se rompe le scatole la tolgo.
CIAO!
"La statistica è quella scienza che dice che se hai la testa nel congelatore e i piedi nel forno, mediamente stai bene"
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo