10 : Allocazione dinamica della memoria Vers . 8.3 – Ottobre 2023
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