Definizione
Un percorso euleriano su un grafico tocca ogni bordo una sola volta. Un circuito euleriano è un percorso euleriano che inizia e finisce nello stesso punto. Questo tipo di circuito in primo luogo è stato teorizzato dal matematico Leonhard Euler. Prima descritti da lui mentre si lavora sul problema sette ponti di Königsberg: data una specifica serie di ponti che collegano vari punti, se era possibile costruire un percorso che sarebbe attraversare ogni ponte in una sola volta. Eulero stabilito che questo problema non aveva alcuna soluzione, creando le fondamenta per la teoria dei grafi.
Condizioni per un circuito euleriano
Per un circuito euleriano sia possibile, ogni punto del grafico deve avere un numero pari di sentieri che collegano ad esso. Ciò significa che un circuito euleriano è possibile per qualsiasi grafico in cui ogni vertice ha 2, 4 o un numero simile di linee che collegano ad esso. Di conseguenza, non importa la forma effettiva e la configurazione del grafico; tutto ciò che realmente conta è il numero di percorsi per ogni riga.
Costruzione di un percorso euleriano per un grafico
Un grafico può avere un percorso euleriano se ne consegue due condizioni: deve avere tutti i suoi sentieri sullo stesso piano (si pensi un aereo come una superficie piana, come un tavolo o un pezzo di carta) e ci sono alcune restrizioni per gli "angoli" del grafico. Ci può essere non più di due angoli che hanno un numero dispari di linee provenienti da loro. Se queste condizioni sono soddisfatte, un percorso euleriano può essere fatto utilizzando un processo chiamato algoritmo di Fleury. In primo luogo, si avvia in un vertice con un numero dispari di sentieri che conducono da esso. Quindi si sposta lungo qualsiasi bordo che, se fosse necessario cancellato, il grafico sarebbe ancora essere connesso..--se non non c'è nessun altra scelta. In tal caso, il bordo viene eliminato. Al termine dell'algoritmo, un percorso euleriano (o in alcuni casi, un circuito euleriano) è formata.