10: Allocazione dinamica della memoria Vers. 9.1 – Ottobre 2025
APPROFONDIMENTO: I ponti di Konisberg
E’ un problema che la tradizione vuole legato alla città di Königsberg della Prussia orientale( oggi Kaliningrad, in Russia), nota per aver dato i natali a Immanuel Kant( 1724-1804).
Il problema riguarda la possibilità di compiere un percorso( cammino semplice) attraversando tutti i ponti della città e passando per ognuno di essi una( e una sola) volta.
Alla semplicità dell’ enunciato, nei termini in cui la tradizione vuole fosse posto dagli abitanti del luogo, non corrisponde una soluzione matematica della questione altrettanto semplice.
In termini moderni, il problema si risolve attraverso le proprietà di percorribilità di un grafo, ma utilizzando prove empiriche, la maggior parte delle persone di quel tempo sembra propendesse per una risposta negativa.
Analizzando il problema dei ponti di Königsberg con il formalismo dei grafi, il percorso può essere rappresentato con un grafo con 4 nodi A, B, C, D collegati da 7 archi e aventi tutti ordine dispari, rispettivamente ordine 5, 3, 3, 3.
c
C
A d e g
D b
B a f
Fu Eulero a fornire la dimostrazione generale del problema nel trattato Solutio problematis ad geometriam situs pertinentis del 1741; nella sua soluzione si individua oggi l’ origine della moderna teoria dei grafi.
Egli infatti stabilì quindi le seguenti generalizzazioni:
• soltanto un grafo composto da nodi di ordine pari, può essere percorso toccando una e una sola volta tutti i nodi in modo da ritornare infine al punto di partenza; in pratica si effettua un percorso che è un cammino semplice ciclico o ciclo;
• se il grafo contiene tutti nodi di ordine pari ma soltanto due ordine dispari esso è ancora percorribile, ma occorre partire da uno dei due nodi dispari ed arrivare all’ altro nodo dispari; in questo caso non è quindi possibile giungere alla fine del percorso allo stesso nodo di partenza;
• se il grafo contiene più di due nodi di ordine dispari risulterà impossibile percorrerlo senza dover attraversare archi già toccati in precedenza.
Per queste ragioni e grazie ad Eulero, il problema dei ponti di Königsberg quindi, non ammette soluzione.
Autore: Rio Chierego( email: riochierego @ libero. it- sito web: www. riochierego. it) Pag. 46