Топ-100
Indietro

ⓘ Cammino euleriano. In teoria dei grafi la nozione di cammino euleriano si può definire per varie strutture relazionali. Un cammino euleriano sopra un multigrafo ..




Cammino euleriano
                                     

ⓘ 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. Lambito 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 sullinsieme degli spigoli o sullinsieme 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.

                                     
  • di un circuito euleriano i secondi posseggono un cammino euleriano ma non un circuito euleriano i terzi non sono multigrafi euleriani Consideriamo un
  • grafi si dice multidigrafo euleriano un multidigrafo connesso, privo di cappi e dotato di un cammino euleriano cioè di un cammino che tocca tutti i suoi
  • grafo è euleriano la soluzione del problema del postino cinese è quindi un suo percorso euleriano Chinese Postman Problem su nist.gov. Cammino euleriano
  • topologico X Cammino casuale Cammino euleriano Cammino hamiltoniano Cammino libero medio Cammino libero medio anaelastico Cammino minimo Cammino spirituale
  • Eulero Carico critico euleriano Cerchio di Eulero, o cerchio di Feuerbach Diagramma di Eulero - Venn Criterio di Eulero Grafo euleriano Gli integrali di Eulero
  • toccati da un numero dispari di spigoli. Un tale cammino viene chiamato cammino euleriano Tra i grafi euleriani ricordiamo tutti grafi completi di ordine dispari
  • volta. Determinare se questo cammino esista è un problema NP - completo. In termini rigorosi, la determinazione di un cammino hamiltoniano è la ricerca di
  • nodi avranno grado pari. Questo produce un grafo euleriano trovare al suo interno un circuito euleriano Ovviamente, la sua lunghezza è il doppio della
  • Corput sul teorema della discrepanza e al teorema BEST inerente al cammino euleriano sopra un grafo. Oppervlakken met scharen van gesloten geodetische
  • esistenza di cammini hamiltoniani, colorabilità, planarità e connettività dei diversi tipi. All opposto, i problemi riguardanti i cammini euleriani riguardano
  • duale di un grafo cammino è un multigrafo multicappio, multigrafo con un solo nodo e tanti cappi quanti sono gli spigoli del cammino Dualmente il multigrafo
  • fare preciso riferimento a questo termine. Multigrafo duale Multigrafo euleriano Problema dei ponti di Königsberg Grafo Grafo arricchito Multidigrafo Plurigrafo