Cammino euleriano
In teoria dei grafi la nozione di cammino euleriano si può definire per varie strutture relazionali.
Un cammino euleriano sopra un multigrafo è 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 però quello dei multigrafi e dei multidigrafi. Più precisamente si trascurano anche le possibilità 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 possibilità 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 è 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, cioè i cammini euleriani aventi vertice iniziale e vertice finale coincidenti. Questi sono detti circuiti euleriani.
Voci correlate
modifica- Cammino hamiltoniano
- Lemma della stretta di mano, dimostrato da Eulero nel suo articolo originale, che mostra che qualsiasi grafo connesso non orientato ha un numero pari di vertici di grado dispari.
Altri progetti
modifica
Wikimedia Commons contiene immagini o altri file sul cammino euleriano
Collegamenti esterni
modifica- (EN) Eric W. Weisstein, Cammino euleriano, su MathWorld, Wolfram Research.
