Liczba grafów o polu 9-elementowym

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Oxford
Użytkownik
Użytkownik
Posty: 21
Rejestracja: 30 sty 2006, o 14:53
Płeć: Mężczyzna
Lokalizacja: Lublin
Podziękował: 1 raz

Liczba grafów o polu 9-elementowym

Post autor: Oxford » 22 sie 2011, o 18:48

Treść zadania jest następująca:

Ile jest grafów o polu 9-elementowym. Ile z nich jest takich, że zawiera podgraf zupełny o polu 5-elementowym i ich dopełnienie też zawiera podgraf zupełny o polu 5-elementowym.


Zatrzymuję się na pierwszej części zadania:
"Ile jest grafów o polu 9-elementowym."

Problem w tym, że wierzchołki są nieoznaczone. Gdyby wierzchołki tego grafu były oznaczone, łatwo byłoby policzyć ilość takich grafów:
Najpierw liczymy liczbę wszystkich możliwych krawędzi między dowolnymi dwoma punktami
\(\displaystyle{ {9 \choose 2}}\)
Później znajdujemy liczbę wszystkich grafów 9-elementowych czyli liczbę podzbiorów zbioru wyliczonej wcześniej liczby krawędzi
\(\displaystyle{ 2 ^{ {9 \choose 2} }}\)

Wygląda na to, że liczba grafów o nieoznaczonych wierzchołkach jest o wiele mniejsza niż grafów o wierzchołkach oznaczonych. Niestety nie wiem w jaki sposób policzyć tą liczbę.

Będę wdzięczny za każdą pomoc.

ODPOWIEDZ