Ile jest grafów?

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
jul1a
Użytkownik
Użytkownik
Posty: 21
Rejestracja: 4 paź 2019, o 11:31
Płeć: Kobieta
wiek: 20

Ile jest grafów?

Post autor: jul1a »

Ile jest wszystkich grafów prostych etykietowanych o wierzchołkach \(\displaystyle{ 1, 2, . . . , n }\) ?
Czy jest na to wzór jak wyznaczyć tą liczbę?
Awatar użytkownika
Gosda
Użytkownik
Użytkownik
Posty: 340
Rejestracja: 29 cze 2019, o 19:46
Płeć: Mężczyzna
Lokalizacja: Oulu
Podziękował: 42 razy
Pomógł: 60 razy

Re: Ile jest grafów?

Post autor: Gosda »

Chodzi o nieskierowane grafy bez pętli i krawędzi wielokrotnych?
jul1a
Użytkownik
Użytkownik
Posty: 21
Rejestracja: 4 paź 2019, o 11:31
Płeć: Kobieta
wiek: 20

Re: Ile jest grafów?

Post autor: jul1a »

Tak,znalazłam,że będzie to \(\displaystyle{ {n \choose 2}}\) jednak nie rozumiem skąd taka odpowiedź :|
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Ile jest grafów?

Post autor: arek1357 »

Wzór jest do niczego...

Dodano po 5 minutach 11 sekundach:
Powinno być:

\(\displaystyle{ \sum_{i=0}^{ {n \choose 2} } { {n \choose 2} \choose i} }\)

Dodano po 23 godzinach 20 minutach 50 sekundach:
Jeżeli chciałabyś wyliczyć ilość grafów nienumerowanych musiałabyś wziąć grupę działającą na zbiorze krawędzi generowaną przez grupę
\(\displaystyle{ S_{n}}\) działającą na zbiorze punktów , potem przeliczyć indeksy cyklowe i masz ilość grafów nienumerowanych...
ODPOWIEDZ