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

Grafi (numeri di)

Matematica combinatoria  Sequenze 

Indice

  1. 1. Pagina principale
  2. 2. Grafi connessi
  3. 3. Grafi etichettati

Due grafi sono topologicamente distinti se non è possibile trasformare l’uno nell’altro, facendo corrispondere nodo a nodo e arco ad arco, indipendentemente da come siano disegnati.

Per esempio, i due grafi mostrati nella figura seguente non sono topologicamente distinti, perché è possibile deformare l’uno nell’altro senza aggiungere o rimuovere archi.

 

Grafi topologicamente equivalenti

 

 

La figura seguente mostra i grafi topologicamente distinti con fino a 4 nodi.

 

Grafi topologicamente distinti con fino a 4 nodi

 

 

Il numero di grafi topologicamente distinti con n nodi tende a Numero di grafi topologicamente distinti con n nodi.

 

La tabella seguente riporta i numeri di grafi topologicamente distinti con n nodi, per n fino a 20 (Keith M. Briggs).

n

Numero di grafi con n nodi

0

1

1

1

2

2

3

4

4

11

5

34

6

156

7

1044

8

12346

9

274668

10

12005168

11

1018997864

12

165091172592

13

50502031367952

14

29054155657235488

15

31426485969804308768

16

64001015704527557894928

17

245935864153532932683719776

18

1787577725145611700547878190848

19

24637809253125004524383007491432768

20

645490122795799841856164638490742749440

 

Un grafo si dice “pari” se tutti i nodi sono connessi da un numero pari di archi.

Un grafo pari è anche talvolta chiamato “euleriano”, ma è più corretto riservare il termine ai grafi pari connessi.

La figura seguente mostra i grafi pari topologicamente distinti con fino a 5 nodi.

 

Grafi pari topologicamente distinti con fino a 5 nodi

 

 

La tabella seguente riporta i numeri di grafi pari topologicamente distinti con n nodi, per n fino a 26 (R.W. Robinson, The Online Encyclopedia of Integer Sequences http://oeis.org).

n

Numero di grafi pari con n nodi

0

1

1

1

2

1

3

2

4

3

5

7

6

16

7

54

8

243

9

2038

10

33120

11

1182004

12

87723296

13

12886193064

14

3633057074584

15

1944000150734320

16

1967881448329407496

17

3768516017219786199856

18

13670271807937483065795200

19

94109042015724412679233018144

20

1232069666043220685614640133362240

21

30739974599837035594494908346443726272

22

1464616584892951614637834432454928487321792

23

133517867425328719965824261177376949378463724928

24

23331378450474334173960358458324497256118170821672192

25

7828241053490735575604692213976871639067242060743800973568

26

5051222500253499871627935174024445724071241027782979567759187712

 

Vedi anche

Numeri di alberi.

Contattami

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