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

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 4 nodi.

Grafo completo con 4 nodi

 

In un grafo del genere si può andare da un nodo a un altro percorrendo un solo arco, ma in quanti modi si può farlo percorrendo un qualsiasi numero di archi, senza però ripassare due volte dallo stesso?

Per esempio, con 4 nodi, che chiameremo A, B, C e D come nella figura, si può andare da A a B in 5 modi: A – B, A – C – B, A – D – B, A – C – D – B e A – D – C – B.

L’esempio mostra come il numero di modi sia uguale alle sequenze di lettere con prima e ultima lettera fissata, che contengano fino a n lettere fissate, nessuna delle quali ripetuta, oppure (scartando le lettere estreme) ai modi di ordinare un sottoinsieme (anche vuoto) di oggetti scelti tra n – 2 oggetti distinti.

 

La risposta generale è data dalla formula Formula per il numero di percorsi, che per n > 2 diviene Formula per il numero di percorsi e si può approssimare con e(n – 2)!.

 

I valori possono anche essere calcolati con la ricorrenza a0 = 1, a2 = 1, an = (n – 3)(an – 1 + an – 2) + 2.

 

Il numero di cammini chiusi in un grafo completo con n nodi, che iniziano e terminano in un nodo fissato, senza passare due volte dallo stesso nodo, è an + 1 – 1, che si riduce a an + 1n se non si permette di ripassare (in direzione inversa) sullo stesso arco.

 

La tabella segeunte mostra i primi valori.

n

Numero di percorsi

2

1

3

2

4

5

5

16

6

65

7

326

8

1957

9

13700

10

109601

11

986410

12

9864101

13

108505112

14

1302061345

15

16926797486

16

236975164805

17

3554627472076

18

56874039553217

19

966858672404690

20

17403456103284421

 

La sequenza ha una curiosa proprietà: anam è divisibile per nm, per n > m.

 

Gli unici primi noti nella sequenza sono a3 = 2 e a4 = 5.

Bibliografia

  • De Koninck, Jean-Marie;  Those Fascinating Numbers, American Mathematical Society, 2009 -

    Un'inesauribile miniera di notizie sugli interi, informazioni e spunti per approfondimenti.

Contattami

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