Soluzioni ottavo, nono e decimo ponte di Königsberg

Per facilitare le successive spiegazioni, la città  di Königsberg è stata ridotta a un grafo con i nodi colorati (a sinistra, già pubblicato nel precedente post).  Con il bianco è stata indicata la penisola sulla quale dimora il Vescovo e si erge la sua chiesa, i due castelli sulle sponde opposte hanno i colori dei rispettivi principi e, infine, il nodo arancione rappresenta l'isola con l'ormai famosa osteria.

L'ottavo ponte del Principe Blu 
Avendo in partenza 4 nodi di grado dispari, un qualunque ottavo spigolo (ponte) varierà il grado di due di essi creando un grafo con  due nodi pari e due dispari. Sappiamo che in tale situazione è possibile avere un percorso eulriano iniziando da uno dei due nodi dispari (nel nostro caso deve essere il castello el principe blu)  terminando all'altro (l'osteria). Ne consegue, logicamente, che i nodi da far diventare di grado pari sono quello dell'altro castello e del Vescovado e quindi costruire un ponte che li unisca. (disegno in basso a sinistra)

   

Il nono ponte del Principe Rosso 
Un ragionamento simile ci farà risolvere anche il problema del nono spigolo. Il nodo del principe blu dovrà ridiventare dispari e quello del rosso pari, lasciando invariato il grado degli altri due nodi. Di conseguenza il nono ponte verrà costruito fra i due castelli. (disegno in alto a destra)

Il decimo ponte del Vescovo 
Adesso che la logica del metodo è stata completamentea compresa, almeno spero, e ricordando che affinché sia possibile ottenere un circuito euleriano (il vescovo vuole che ognuno possa rientrare a casa senza dover terminare il percorso all'osteria) tutti i nodi devono essere di grado pari, il ponte sarà costruito fra i due dispari (vescovado e osteria), rendendoli pari. (disegno in basso a sinistra) 

  

Nel disegno in alto destra viene rappresentata la situazione definitiva, graficamente ancor più chiara, nella quale sono riportati i ponti con il loro numero d'ordine di costruzione.

Testo di giovis, disegni tratti da Wikipedia

PS - Come anticipato nel primo post relativo ai 7 ponti di Königsberg, è mia intenzione proporvi in futuro altri problemi che possono essere facilmente risolti riducendoli a grafi. In particolare la teoria è utile per la pianificazione e ottimizzazione di itinerari, siano essi circolari o lineari.

Varianti del problema dei 7 ponti di Königsberg

Se si rinuncia alla condizione che il punto di inizio e il punto finale debbano per forza coincidere, si potrà avere un cammino (ma non un circuito) euleriano anche nel caso in cui due vertici siano raggiunti da un numero dispari di spigoli. Indifferentemente, uno di essi rappresenterà il punto di partenza e l'altro quello di arrivo. Il problema originale dei 7 ponti di Königsberg  tratta di vertici generici, caratterizzati solo dai loro collegamenti, ma aggiungendo informazioni "urbanistiche e sociali", sono state proposte alcune simpatiche varianti al quesito in stile narrativo e descrittivo. Si ipotizza che sulla riva settentrionale sorgesse il castello del principe Blu e su quella meridionale quello del principe Rosso; sulla penisola si colloca il Vescovado e nell'isola centrale un'osteria. 

Per aiutarvi a visualizzare la situazione e a seguire i successivi sviluppi (risolvendo i quesiti) la città è stata ridotta a un grafo con i nodi colorati, attribuendo il bianco al Vescovo, ai castelli i colori dei rispettivi principi e rappresentando in arancione l'isola con l'osteria (disegno da Wikipedia) e ora comincia la storia. Era consuetudine di molti degli abitanti della città, prìncipi compresi, passare le serate all'osteria e quasi ogni notte qualcuno, già almeno brillo, scommetteva di essere in grado di attraversare i 7 ponti una volta ciascuno e tornare dagli amici. Alcuni, rientrati chissà come all'osteria, si vantavano di esserci riusciti senza però saper spiegare come, ma poco importava poiché comunque qualcuno avrebbe pagato e tutti avrebbero continuato a bere.

L'ottavo ponte del principe Blu
Il principe Blu, resosi conto dell'irrisolvibilità del problema, ne cambia un po' i termini e fa costruire di nascosto un ottavo ponte in modo che possa passarli tutti partendo dal suo castello e finendo all'osteria. Oltre a vantarsi della sua impresa potrà anche prendere in giro il suo rivale, il principe Rosso, poiché questi non può fare altrettanto iniziando dal suo castello.
Dove è stato costruito il ponte del principe Blu?

Il nono ponte del principe Rosso 
Il principe Rosso, non essendo disposto a subire passivamente l'affronto, decide quindi di far costruire un ulteriore ponte in modo da ribaltare la situazione. Ora è lui che può andare dal suo castello all'osteria passando per tutti i ponti e con questa aggiunta il principe Blu non potrà più fare altrettanto.
Dove è stato costruito il nono ponte del principe Rosso?

Il decimo ponte del Vescovo 
Ma a questo punto scende in campo il Vescovo che, irritato da questa stupida sfida che ha solo reso popolare l'osteria e ha fatto aumentare gli ubriachi che vanno in giro di notte per attraversare tutti i ponti, decide di far costruire un ultimo ponte che permetta a chiunque di passarli tutti, a partire da qualunque punto della città, e tornare a casa sobri, senza doversi fermare all'osteria.
Dove è stato costruito il decimo ponte del Vescovo?

Chi vuole verificare se ha assimilato il concetto, può risolvere i quesiti e disegnare i vari ponti, in successione. Gli impazienti possono facilmente trovare in rete la soluzione che comunque proporrò in un prossimo post.
Suggerimento: non perdete tempo procedendo per tentativi, ma ragionate in termini di nodi di grado pari e dispari e troverete rapidamente la soluzione di ciascun quesito.

La Teoria dei Grafi a partire da Königsberg

Introduco la teoria dei grafi proponendo un quesito classico, quello dei 7 ponti di Königsberg. Si dice (forse si tratta di leggenda metropolitana) che il problema se lo pose Eulero volendo cercare un itinerario circolare per una passeggiata che includesse il passaggio di tutti i ponti, ma solo una volta ciascuno. Questa è una mappa della città, costruita attorno alla confluenza di due corsi d'acqua con un'isola al centro del ramo unico.

In linea generale, per affrontare questo tipo di problema, è necessario semplificarlo con un'astrazione, concentrandosi solo sugli elementi essenziali che in questo caso sono 4 aree ben separate dall'acqua e connesse solo attraverso i ponti. Come andare da un ponte all'altro non influisce sulle nostre scelte. Indicate le aree con lettere vediamo che la A (l'isola) è raggiunta da 5 ponti, due dalla riva sud B, due da quella nord C e uno dalla lingua di terra D delimitata dai due corsi d'acqua confluenti.

Fatti un paio di tentativi, sperimentali e certamente senza esito, vi renderete ben presto conto che la soluzione non esiste. Infatti, dovunque andiate, dovreste utilizzare un ponte diverso per lasciare quell'area e visto che si richiede di passare per tutti i ponti una sola volta l'itinerario potrà essere costruito solo nel caso in cui ciascuna area abbia un numero pari di ponti. Nel caso proposto l'isola ne ha 5 e le altre tre zone solo 3, quindi tutti numeri dispari, ma ne sarebbe bastata anche solo una per avere la certezza dell'impossibilità di risolvere il problema.
Nella teoria dei grafi le aree di Königsberg sono i nodi, e i collegamenti fra essi sono indicati come archi o spigoli (nel nostro caso i ponti). Il numero di archi facenti capo ad un nodo ne forniscono il grado. La regola generale alla quale siamo appena giunti può quindi essere enunciata così: per costruire un percorso euleriano (una linea che percorra tutti gli archi una sola volta e riconduca al nodo iniziale) è necessario che tutti i nodi siano di grado pari.
In un prossimo post proporrò alcune varianti al classico quesito dei 7 ponti di Königsberg che verranno "giustificate" dall'esigenza di accontentare il Vescovo, il Principe Blu e il Principe Rosso che, volta per volta, decideranno di far costruire un nuovo ponte.
Successivamente vedremo che la teoria dei grafi si applica in una miriade di casi, dai calendari dei tornei sportivi alle scelte di percorso suggerite dal vostro navigatore stradale.
Questa nozione può tornare utile anche agli escursionisti per pianificare itinerari che prevedano il ritorno al punto di partenza evitando di ripercorrere uno stesso tratto (arco). Applicheremo la teoria per cercare di percorrere i vari sentieri di Monte San Costanzo senza tornare sui nostri passi.

NB - a partire da questo e nel corso delle prossime settimane, i post saranno sporadici (dipende da quando avrò la possibilità di collegarmi) e probabilmente  conterranno errori in quanto utilizzo il tablet, con il quale non ho eccessiva dimestichezza ed ha certamente dei limiti comparato con un computer.