Quanti sono i possibili grafi distinti con N vertici?

[Ishima]

Buongiorno,
è possibile calcolare il numero di grafi distinti che è possibile ottenere avendo N vertici?
Grazie in anticipo!

[Martino]

Sì basta contare i possibili archi e ricordare che per ogni arco ci sono 2 possibilità (esserci o non esserci). Ti lascio dedurre la formula.

[Ishima]

Sì basta contare i possibili archi e ricordare che per ogni arco ci sono 2 possibilità (esserci o non esserci). Ti lascio dedurre la formula.

Allora in un grafo con 5 vertici possono esserci al massimo 8 lati,dopodichè il primo grafo avrà 8 lati,il secondo 7 ecc..è corretto?
Però al di fuori del grafo completo,possono esserci 8 grafi da 7 lati,8 da 6 ecc..corretto?

[Martino]

Falla più semplice. Supponi di avere 3 vertici. Quanti grafi riesci a costruire?

[Ishima]

4?

[Martino]

Non mi risulta. Comunque non è un quiz è per farti ragionare, se pensi che siano 4 allora dimmi quali sono questi 4.

[Ishima]

Credo siano i seguenti,scusami la scarsa precisione:
[/url]

[Martino]

E quelli con un solo arco? E quelli senza archi?

[Ishima]

Quindi contanto anche quello senza archi e con un solo arco,avremmo 4 + 1 + 3?

[Martino]

Sì quindi 8 in totale. Adesso riesci a generalizzare?