Teoria dei grafi

[MayDay1]

Buongiorno, qualcuno saprebbe per cortesia indicarmi un link al quale posso trovare dispense complete e scaricabili gratuitamente sulla teoria dei grafi? Possibilmente che partano dal principio, o quasi . . .

Grazie a chiunque saprà aiutarmi!

"La statistica è quella scienza che dice che se hai la testa nel congelatore e i piedi nel forno, mediamente stai bene"

[MayDay1]

citazione:

---

Che figata!

PS
Mi hai dato l'idea per un giochino, ti rimando alla sezione giochi e gare.


Modificato da - cannigo il 10/02/2004 10:25:44

---

accetto!!!!

"La statistica è quella scienza che dice che se hai la testa nel congelatore e i piedi nel forno, mediamente stai bene"

[Sk_Anonymous]

Che figata!

PS
Mi hai dato l'idea per un giochino, ti rimando alla sezione giochi e gare.


Modificato da - cannigo il 10/02/2004 10:25:44

[MayDay1]

il teorema dei quattro colori è il più importante teoema dimostrato con la teoria dei grafi. Mi sembra che lo abbia dimostrato qualcuno con l'aiuto di Paul Erdos (già egli stesso grande amante di questa tecnica) negli anni '70. La teoria dei grafi nasce con la dimostrazione del problema dei Ponti di Koenigsberg, effettuata da Euler nel '600. Si parla in sostanza di insiemistica e di relazioni tra insiemi, ha una marea di applicazioni pratiche (dalle reti telefoniche alla strada più corta per i postini ecc ...). Comunque,per tornare ai 4 colori, Cannigo, ogni regione può confinare con infinite -1 altre regioni, è vero . . . in ogni caso con 4 colori puoi fare in modo che nessuna regione abbia il colore di una delle regioni confinanti. Non ci credi? Ecco qui . . .

http://digilander.libero.it/basecinque/ ... or4col.htm

"La statistica è quella scienza che dice che se hai la testa nel congelatore e i piedi nel forno, mediamente stai bene"

Modificato da - MayDay il 10/02/2004 09:57:21

[Sk_Anonymous]

Non c'ho capito quasi niente:

citazione:

---

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.
Alcune considerazioni: osserviamo che, 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.

Si palesa così la complessità della dimostrazione.

Procediamo per passi:


passo 1: 1 colore.

È evidente che non è sufficiente.


passo 2: 2 colori.

Se consideriamo una regione divisa in tre partizioni si osserva che due colori non sono sufficienti: necessariamente due partizioni attigue hanno lo stesso colore


passo 3: 3 colori.

Se consideriamo una regione divisa in quattro partizioni si osserva che tre colori non sono sufficienti: anche in questo caso necessariamente due partizioni attigue hanno lo stesso colore


passo 4: 4 colori.

Con quattro colori si osserva che il problema del terzo passo è risolto e per ogni successiva partizione è possibile assegnare uno dei quattro colori in modo tale che sia diverso da quelli delle partizioni confinanti.

---

Ma una regione può anche confinare con infinite -1 altre regioni, o no?

[Sk_Anonymous]

Ci ho dato una rapida occhiata: E' possibile colorare con soli quattro colori aree confinanti e mai intersecanti di forma casuale senza che mai lo stesso colore debba essere usato per colorare aree limitrofe (adiacenti [confinanti]). Non ho capito qual'è il problema, hai finito il rosso?:-)

[Sk_Anonymous]

"La statistica è quella scienza che dice che se hai la testa nel congelatore e i piedi nel forno, mediamente stai bene"

Se becchi il fanatico di statistica, per essere sicuro che tu non possa contestare la sua affermazione, prima di farla ti taglia la testa e ipiedi

Cos'è la teoira dei grafi?