Blog divulgativo sulla matematica applicata

Le Passeggiate Salutiste (Parte due): ancora sulla teoria dei grafi e il passeggiare

Bentornati nel post più salutista di tutto il blog Math is in the Air!

foto_001

L'ultima volta ci siamo lasciati con il dubbio se questa passeggiata attraverso i sette ponti di Königsberg si possa fare, a condizione di passare una e una volta sola per ognuno dei ponti (clicca qui per leggere il precedente post). Diamo, dunque, una risposta a questo dilemma che tanto attanagliò i signorotti panciuti del capoluogo della Prussia orientale.

Come fare? Basta un numeretto...

L'idea di Eulero fu quella di assegnare un numero naturale ad ogni nodo, ovvero il numero di archi entranti nello stesso. Chiameremo questo numero grado del nodo. Prendiamo il caso limite che vi ho suggerito lo scorso post, vale a dire un grafo ad anello:

Grafo ad anello

Ad ogni nodo è associato il numero 2; se immaginassimo di iniziare un cammino dal nodo A, saremmo obbligati a muoversi verso B o D. In qualsiasi caso, ci lasceremmo dietro un arco. Supponendo di passare per B, avremmo toccato entrambi gli archi che collegano B, non a caso a tale nodo è associato un numero pari: un arco entrante, un arco uscente (1 + 1 = 2). Questo fatto deve avvenire ogni qualvolta si passa per un nodo con un grado pari: tante volte si entra in quel nodo, altrettante se ne deve uscire. Non a caso, nel grafo ad anello con 4 nodi la passeggiata si conclude esattamente in A, in quanto il computo degli archi “toccati” sul nodo iniziale era rimasto a 1.

Consideriamo un altro grafo, un anello di 3 nodi con un quarto nodo collegato all'anello tramite un arco. Studiando i gradi, si ottiene

Grafo 2

Sfido ognuno degli utenti lettori a immedesimarsi nei signorotti locali e far partire la passeggiata dal nodo B o C... Non ci riuscite, vero? 

Provate, invece, a partire da A o D. Riuscirete sicuramente a concludere la passeggiata passando per tutti i ponti una volta sola. Non a caso, siete partiti da un nodo di grado dispari. Il motivo è piuttosto semplice: se immaginate di far partire una passeggiata, dovrete pensare un punto di partenza e un punto di arrivo, considerando la possibilità che da dove siete partiti potreste non tornarci, e che dove siete arrivati non dovrete più muovervi. Ha senso dunque pensare che questi due nodi speciali:

  • possono avere grado dispari

  • non devono essere più di due, uno dove partire e uno dove arrivare.

Fu questa la scoperta di Eulero: affinché un grafo rispetti le condizione descritte dal problema, il numero di nodi di grado dispari deve essere al più 2. I grafi con questa caratteristica, infatti, si chiamano cammini euleriani.

Alla luce di ciò, è possibile rispondere alla domanda iniziale. Riporto di seguito il grafo associato ai ponti di Königsberg con annessi gradi:

Grafo 3

I gradi dei nodi di questo grafo sono tutti dispari, quindi questo non è un cammino euleriano.

Ed ora? Applicazioni!

Dopo l'esperienza dei ponti di Königsberg, Eulero proseguì con lo studio della teoria dei grafi e, con lui, numerosissimi matematici. Altrettanto numerosi sono stati i problemi risolti grazie alla teoria dei grafi. Ecco alcuni esempi di applicazioni:

  • il problema dei quattro colori è forse la più famosa applicazione della teoria dei grafi ed è nato da una congettura del matematico e botanico Francis Gurthie. Quest'ultimo fu il primo a supporre che bastavano quattro colori per colorare le regioni della Gran Bretagna senza che due regioni confinanti avessero lo stesso colore. Il problema è stato generalizzato su un piano con un numero qualsiasi di regioni: ad ogni regione è associato un nodo e due regioni confinanti sono collegate grazie a un arco. Il problema fu dimostrato solo nel 1976 da K. Appel e W. Haken grazie all'ausilio dei “potenti e innovativi” calcolatori.

  • Il problema del commesso viaggiatore ha il seguente enunciato:
    data una rete di città connesse tra loro con strade, trovare il percorso di minore lunghezza che un commesso viaggiatore deve seguire per visitare tutte le città una e una sola volta". Il problema viene utilizzato per risolvere problemi tipo i flussi di merci tra fornitori e distributori, oppure per trovare il percorso minimo di un trapano per creare i fori di una piastra in un circuito stampato. Anche in questo caso, per la ricerca di una soluzione ottimale si passa allo studio di un grafo associato e vengono sfruttati i concetti di grafo pesato e di circuito hamiltoniano.

  • le p-reti, dette anche reti di Petri, sono una rappresentazione matematica di un sistema distribuito discreto, utilizzato in ambiti come ingegneria informatica, data analysis e affidabilità. Tramite la struttura di grafo, è possibile definire dei nodi posti, dei nodi transizioni e degli archi diretti che collegano posti e transizioni. La struttura di grafo utilizzata in questo caso è quella di grafo bipartito, ovvero un grafo suddivisibile in due sottografi tali che non esistano archi con entrambi i nodi terminali nello stesso sottografo.

Spero che il post vi sia piaciuto! Ci vediamo nel prossimo appuntamento con la storia della matematica!!

...Ah già, c'è una morale dietro tutto questo! Lasciate le chiavi della macchina sul muretto di casa, una bella passeggiata è il metodo migliore per schiarirsi un po' le idee! ;)

mfront_anziani_parco

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Similar posts

Nessun commento ancora

Lascia una risposta

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *

È possibile utilizzare questi tag ed attributi XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Partecipa all’indagine “Io e la Matematica”

Clicca sull'immagine sottostante per rispondere al breve e anonimo questionario:

MIA15 - Nomination

Conviditi con i tuoi contatti questo link!

Canale Telegram dedicato alla Matematica

Iscriviti sul nostro canale Telegram

MIA15 - Nomination

Rimani aggiornato sui più interessanti articoli di divulgazione matematica e non solo!

Iscriviti alla nostra newsletter

Resta aggiornato sui nostri post e su quello che facciamo.

Seguici su Twitter

Tag Cloud

Grazie per il sostegno ai #MIA2015

Grazie a tutti per averci votato ai "Macchia Nera Awards 2015" nella categoria "Miglior Sito Tecnico-Divulgativo".

Siamo arrivati in finale grazie al vostro sostegno!

MIA15 - Nomination