N pontból mennyi egyszerű gráf adható meg?

Ha számozott csúcsokról van szó és n>=1, akkor

n*(n-1)/2

sum [((n*(n-1)/2) alatt az i]

i=0

Ha n=0, akkor értekemszerűen 1-féle gráf adható.

Ha nem számozott csúcsokról van szó, akkor lehetetlen megmondani tetszőleges n-re.

Ugye mikor mondunk két gráfot különbözőnek?

Például 3 pont legyek én, a Gyula meg az Ottó. Különbözik-e az a gráf, hogy én meg Gyula vagyunk összekötve (mert mondjuk mi mentünk sörözni, és Ottó nem jött), attól, hogy Gyula és Ottó van összekötve (azaz én nem voltam velük sörözni)? Vagy most két gráfot akkor tekintesz különbözőnek, ha nem izomorfak? (Ugye a fenti két gráf izomorf, mert például ha én és Ottó szerepét felcseréljük a második esetben, akkor éppen az elsőt kapjuk.)

Ezért kapsz kettő választ is:

[link]

[link]

Basszus, ezt benéztem. Ez az összefüggő gráfok száma.

[link]

És akkor 2^(n(n-1)/2).