Don't take life too seriously: it's just a temporary situation

Percorsi euleriani (numero di)

Matematica combinatoria  Teoria dei grafi 

Un grafo completo con n nodi è un grafo nel quale ciascuno degli n nodi è connesso a tutti gli altri.

La figura seguente mostra il grafo completo con 5 nodi.

 

Grafo completo con 5 nodi

 

In un grafo del genere si può percorrere un ciclo euleriano, ossia un percorso chiuso che passi esattamente una volta per tutti gli archi?

La risposta, come dimostrò Eulero, è affermativa se e solo se il numero di nodi è dispari; nel caso della figura, uno dei 264 possibili cicli euleriani è A – B – C – D – E – A – C – E – B – D – A.

 

Il problema che si pone è determinare il numero di tali percorsi; due percorsi si considerano equivalenti se uno corrisponde a una permutazione ciclica dell’altro: essendo percorsi chiusi, infatti, la scelta del nodo iniziale è irrilevante.

Non si considerano invece equivalenti i percorsi che differiscono per il verso di percorrenza, quindi, per esempio, su un grafo completo di tre nodi, che chiameremo A, B e C, sono possibili due percorsi euleriani: A – B – C (equivalente a B – C – A e C – A – B) e C – B – A (equivalente a B – A – C e A – C – B).

 

Il numero di percorsi euleriani per un grafo completo con 7 nodi fu calcolato da M. Reiss nel 1859 e pubblicato postumo solo nel 1871. In effetti Reiss risolse il problema di contare il numero di circuiti chiusi che possono essere formati con le 28 tessere del domino, ma C.A. Laisant fece notare che se si eliminano le tessere contenenti un doppio numero, il problema è equivalente a quello di contare i percorsi euleriani, considerando una tessera come l’indicazione di un arco tra i due nodi corrispondenti ai numeri incisi sulla tessera.

 

Jolivad nel 1895 e indipendentemente G. Tarry nel 1896 calcolarono il numero di percorsi euleriani per un grafo completo con 9 nodi.

 

V.S. Shishov e Ho Ba Thuan pubblicarono nel 1968 un metodo per ottenere il numero di percorsi euleriani per qualsiasi grafo dalla soluzione di un sistema di equazioni. Sfortunatamente il numero di equazioni cresce molto rapidamente al crescere del numero di nodi e il metodo non è di fatto utilizzabile.

 

Brendan D McKay e Robert W. Robinson dimostrarono nel 1995 che i numero di cammini euleriani in un grafo completo con n nodi è maggiore di Limite inferiore per il numero di percorsi euleriani in un grafo completo con n nodi e cresce asintoticamente come tale espressione.

I due matematici calcolarono anche i numeri di percorsi euleriani per grafi completi con n nodi, per n fino a 21, riportati nella tabella seguente.

n

Numero di percorsi euleriani

3

2

5

264

7

1015440

9

90449251200

11

169107043478365440

13

6267416821165079203599360

15

4435711276305905572695127676467200

17

58393052751308545653929138771580386824519680

19

14021772793551297695593332913856884153315254190271692800

21

60498832138791357698014788383803842810832836262245623803123983974400

 

Il numero di percorsi hamiltoniani, cioè percorsi che toccano esattamente una volta tutti i nodi, in un grafo completo con n nodi è semplice da calcolare: scelto arbitrariamente un nodo come partenza, i restanti possono essere ordinati in (n – 1)! modi diversi, ciascuno dei quali corrisponde a un percorso diverso.

Vedi anche

Numero di percorsi.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.