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.