Indice
Un grafo si dice “connesso” se tra qualsiasi coppia di nodi esiste un percorso lungo gli archi.
Un grafo connesso e privo di cicli si chiama “albero” (v. numeri di alberi).
Il complemento di un grafo si ottiene eliminando tutti gli archi e aggiungendo archi tra i nodi che nel grafo di partenza non erano collegati da un arco.
Se un grafo non è connesso, il suo complemento lo è, ma il viceversa non è vero: il complemento del grafo costituito da un ciclo di 5 punti è isomorfo al grafo stesso.
La figura seguente mostra i grafi connessi topologicamente distinti con fino a 4 nodi.
La tabella seguente riporta i numeri di grafi connessi topologicamente distinti con n nodi, per n fino a 20 (Keith M. Briggs).
|
n |
Numero di grafi connessi con n nodi |
|
0 |
1 |
|
1 |
1 |
|
2 |
1 |
|
3 |
2 |
|
4 |
6 |
|
5 |
21 |
|
6 |
112 |
|
7 |
853 |
|
8 |
11117 |
|
9 |
261080 |
|
10 |
11716571 |
|
11 |
1006700565 |
|
12 |
164059830476 |
|
13 |
50335907869219 |
|
14 |
29003487462848061 |
|
15 |
31397381142761241960 |
|
16 |
63969560113225176176277 |
|
17 |
245871831682084026519528568 |
|
18 |
1787331725248899088890200576580 |
|
19 |
24636021429399867655322650759681644 |
|
20 |
645465483198722799426731128794502283004 |
Un grafo pari e connesso si dice “euleriano”, perché permette un percorso euleriano, ossia un percorso chiuso, che attraversa tutti gli archi esattamente una volta.
La figura seguente mostra i grafi euleriani topologicamente distinti con fino a 6 nodi.
La tabella seguente riporta i numeri di grafi euleriani 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 euleriani con n nodi |
|
0 |
0 |
|
1 |
1 |
|
2 |
0 |
|
3 |
1 |
|
4 |
1 |
|
5 |
4 |
|
6 |
8 |
|
7 |
37 |
|
8 |
184 |
|
9 |
1782 |
|
10 |
31026 |
|
11 |
1148626 |
|
12 |
86539128 |
|
13 |
12798435868 |
|
14 |
3620169692289 |
|
15 |
1940367005824561 |
|
16 |
1965937435288738165 |
|
17 |
3766548132138130650270 |
|
18 |
13666503289976224080346733 |
|
19 |
94095371741948582794446564120 |
|
20 |
1231975556997436439337832688604922 |
|
21 |
30738742530157322096089832123489559100 |
|
22 |
1464585844918257668548910738577612061958548 |
|
23 |
133516402808742594944502554177384132346202707043 |
|
24 |
23331244932606878105265510415114785940755577712658966 |
|
25 |
7828217722112283636653929664080981065542811930261502038224 |
|
26 |
5051214672012446247374492051778657066172313560637348240264668992 |
Tabelle numeriche
Il numero di grafi topologicamente distinti con n nodi, per n fino a 75, Il numero di grafi connessi, topologicamente distinti, con n nodi, per n fino a 75, I numeri di grafi k-regolari con n nodi, per n fino a 24, I numeri di grafi k-regolari connessi con n nodi, per n fino a 24, Il numero di grafi etichettati con n nodi per n fino a 100, Il numero totale di nodi dei grafi etichettati con n nodi per n fino a 100, Il numero totale di archi dei grafi etichettati con n nodi per n fino a 100, Il numero di grafi etichettati connessi con n nodi, per n fino a 50.Vedi anche
Numeri di alberi.Bibliografia
- Wilf, Herbert S.; Generatingfunctionology, Wellesley, A.K. Peters Ltd., III ediz., 2006 -
Uno splendido testo sulle funzioni generatrici.