- 0 vertici dispari: un circuito, da qualsiasi vertice a sé stesso
- 2 vertici dispari: un cammino dall'uno all'altro
- 4 o più: impossibile con un solo tratto
Cerca cammini euleriani
Si può disegnare la casa di San Nicola senza staccare la matita e senza ripassare su una linea? Sì, ma solo partendo da uno dei due angoli in basso, e da ciascuno ci sono 44 modi. Il motivo è il grado di un vertice, il numero di linee che vi si incontrano: ogni volta che la matita attraversa un vertice ne usa due linee. Leonhard Euler trovò questa regola nel 1736 con i sette ponti di Königsberg. Traccia tu stesso una figura, guarda dove resti bloccato e perché, chiedi un suggerimento o osserva un algoritmo che la disegna. Scegli una figura e tracciala: tocca un vertice per iniziare, poi gli archi o i vertici successivi in ordine, oppure trascina da un vertice all'altro. Ogni arco si usa una volta sola. Indietro annulla un passo, Suggerimento mostra il prossimo arco sicuro e Risolvi esegue passo per passo l'algoritmo di Fleury o quello di Hierholzer. I vertici dispari sono pieni e il bollino su ogni vertice è il suo grado. In Disegna, tocca uno spazio vuoto per aggiungere un vertice e due vertici per unirli, ancora una volta per un secondo arco; trascina un vertice per spostarlo. Cancella rimuove vertici e archi. Quando più di due vertici sono dispari, Aggiungi inserisce gli archi che rendono tracciabile la figura.
Come funziona
- Scegli una figura, come i sette ponti di Königsberg, la casa di San Nicola o una stella, oppure disegna la tua in Disegna, con quanti archi vuoi tra due vertici.
- Tocca un vertice per iniziare, poi gli archi o i vertici in ordine, oppure trascina da un vertice all'altro. Se resti bloccato, la riga di stato dice perché; Indietro annulla un passo e Suggerimento mostra un arco sicuro.
- Leggi la regola dei gradi sotto la figura, aggiungi a una figura impossibile gli archi suggeriti, oppure premi Risolvi per vedere l'algoritmo di Fleury o quello di Hierholzer disegnarla passo per passo.
Perché decidono i vertici dispari
Un tratto che attraversa un vertice arriva lungo una linea e riparte lungo un'altra, quindi usa le linee di quel vertice a due a due. Solo dove il tratto inizia o finisce una linea può restare senza compagna. Un vertice con un numero dispari di linee deve quindi essere l'inizio o la fine. Senza vertici dispari il tratto finisce dove è iniziato: un circuito euleriano. Con due, va dall'uno all'altro: un cammino euleriano. Con quattro o più ci sono troppe estremità per un solo tratto, e k vertici dispari richiedono k/2 tratti. Königsberg aveva quattro terre, con cinque, tre, tre e tre ponti: tutte dispari, quindi nessuna passeggiata poteva attraversare ogni ponte una volta. Un nuovo ponte tra due di esse l'avrebbe resa possibile.
Gli algoritmi di Fleury e di Hierholzer
Sapere che una figura si può disegnare non equivale a disegnarla: un tratto incauto può tagliarsi fuori dalle linee che gli servono ancora. L'algoritmo di Fleury, del 1883, lo evita con una regola: non attraversare mai un ponte, cioè una linea la cui rimozione dividerebbe in due pezzi le linee rimaste, a meno che non ci sia altra linea. L'algoritmo di Hierholzer, da un articolo pubblicato nel 1873, è più veloce: cammina dove vuoi finché resti bloccato, cosa che può accadere solo alla partenza, poi da un vertice del giro che ha ancora linee libere percorri un altro anello chiuso e inseriscilo nel giro. Il suo tempo cresce in proporzione al numero di archi, ed è così che i computer trovano i cammini euleriani.
Domande frequenti
Qual è la differenza tra un cammino euleriano e un circuito euleriano?
Entrambi usano ogni arco di un grafo esattamente una volta. Un circuito euleriano finisce dove è iniziato; un cammino euleriano finisce altrove. Un grafo connesso ha un circuito quando ogni vertice ha grado pari, e un cammino quando esattamente due vertici hanno grado dispari; il cammino va allora dall'uno all'altro.
Perché i sette ponti di Königsberg non si possono attraversare una volta ciascuno?
Disegna ogni terra come un vertice e ogni ponte come un arco. L'isola di Kneiphof aveva cinque ponti e le altre tre terre tre ciascuna, quindi tutti e quattro i vertici sono dispari. Una passeggiata può iniziare o finire solo in un vertice dispari, e quattro sono troppi. Aggiungendo un ponte tra due di essi restano due vertici dispari e la passeggiata diventa possibile.
In quanti modi si può disegnare la casa di San Nicola?
44 da ciascuno dei due angoli in basso, 88 in tutto, contando come diverso un altro ordine o un altro verso. Da qualsiasi altro vertice non si può, perché gli angoli in basso sono gli unici due con un numero dispari di linee. L'app conta così i modi per le figure piccole.
Che cos'è un ponte in un grafo?
Un arco la cui rimozione divide un grafo connesso in due pezzi. L'algoritmo di Fleury non attraversa mai un ponte degli archi rimasti finché ha un'altra scelta, perché si lascerebbe alle spalle una parte della figura. In questa app, a un tratto che resta bloccato dopo aver attraversato un ponte troppo presto viene detto quale passo è stato.
Ci può essere più di un arco tra due vertici?
Sì. Un grafo con archi paralleli si chiama multigrafo, e a Königsberg serve: due ponti univano il Kneiphof a ciascuna riva. In Disegna, tocca di nuovo due vertici per aggiungere un altro arco tra loro, fino a quattro. La regola dei gradi funziona allo stesso modo, contando ogni arco.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Vai all'editor