Policzyć grafy według typów izomorfizmów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
jakubjo
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 16 gru 2009, o 19:54
Płeć: Mężczyzna
Lokalizacja: LDZ / W-Wa
Pomógł: 1 raz

Policzyć grafy według typów izomorfizmów

Post autor: jakubjo »

Policzyć grafy na 7 wierzchołkach z 6 krawędziami według typów izomorfizmów ze wskazaniem ile jest grafów każdego typu.

Wszystkich grafów na 7 wierzchołkach z 6 krawędziami jest \(\displaystyle{ {{7 \choose 2} \choose 6} = 54264}\), z czego \(\displaystyle{ 7^5 = 16807}\) to drzewa, a reszta - różnego rodzaju grafy niespójne.

I stąd moje pytanie: czy istnieje jakiś względnie szybki sposób na zrobienie takiego zadania (inny niż mozolne "zgadywanie" jak wyglądały będą kolejne typy izomorfizmów i sprawdzanie ich liczby tak, aby stwierdzić czy odnalazło się już wszystkie)?
ODPOWIEDZ