Un esempio di cammino euleriano
In
teoria dei grafi
la nozione di
cammino euleriano
si puo definire per varie
strutture relazionali
.
Un cammino euleriano sopra un
multigrafo
e un cammino che tocca tutti i suoi archi una e una volta sola. Questa definizione si applica anche ai
grafi non orientati
, strutture che possono considerarsi casi particolari dei multigrafi.
Similmente per cammino euleriano sopra un
multidigrafo
si intende un cammino che tocca tutti i suoi archi una e una volta sola. Questa definizione si applica anche ai
digrafi
, strutture che possono considerarsi casi particolari dei multidigrafi.
Queste definizioni si estendono poi a tutti i generi di arricchimenti dei multigrafi (ad esempio alle reti di trasporto) e dei multidigrafi (ad esempio ai vari generi di automi e di
macchine formali
). L'ambito naturale per studiare queste nozioni rimane pero quello dei multigrafi e dei multidigrafi. Piu precisamente si trascurano anche le possibilita di avere dei cappi.
Non tutti i multigrafi e non tutti i multidigrafi posseggono cammini euleriani. Si distinguono quindi i multigrafi euleriani e i multidigrafi euleriani, strutture dotate di cammini euleriani.
Si osserva anche che la presenza di cappi non influisce sulla possibilita di individuare cammini euleriani; lo stesso accade per gli arricchimenti di multigrafi e di multidigrafi.
Si pone allora il problema di stabilire se un multigrafo o un multidigrafo privo di cappi sia euleriano o no. Questo problema e stato risolto sostanzialmente in modo completo da
Eulero
nel
1736
con un lavoro che ha segnato la nascita della
teoria dei grafi
e della
topologia
. Da questo lavoro pionieristico deriva a questi grafi e ai cammini che li caratterizzano la qualifica di
euleriani
.
Si segnala che come
sinonimo
di cammino euleriano su un multigrafo si usa anche il termine cammino biiettivo sugli spigoli, mentre come sinonimo di cammino euleriano su un multidigrafo si usa anche il termine cammino biiettivo sugli archi. In effetti questi cammini si possono considerare funzioni iniettive e suriettive sull'insieme degli spigoli o sull'insieme degli archi.
Casi particolari di cammini euleriani sono i cammini chiusi, cioe i cammini euleriani aventi vertice iniziale e vertice finale coincidenti. Questi sono detti circuiti euleriani.