Chodzi o problem wypisania wszystkich grafów izomorficznych z danym grafem prostym, opartych na tym samym zbiorze wierzchołków. Z tego, co się zorientowałem, najbardziej standardową metodą jest rozważenie działania grupy permutacji zbioru wierzchołków na zbiorze wszystkich grafów zadanych na tym zbiorze wierzchołków. Wówczas stabilizatorem danego grafu jest grupa wszystkich automorfizmów tego grafu, a moc jego orbity to liczba grafów izomorficznych z nim. Automorfizmy można wyznaczyć jakoś tam na palcach, dzięki czemu z własności \(\displaystyle{ \textrm{moc orbity} = \textrm{indeks stabilizatora}}\) dowiemy się, ile jest grafów izomorficznych. Ale chcielibyśmy je jeszcze wypisać. Jak to najłatwiej zrobić?
Ja to widzę tak, że cała grupa permutacji została pokrojona na warstwy przez ten stabilizator i wystarczyłoby mieć reprezentanta każdej takiej warstwy. I tu się pojawiają wątpliwości (być może to są proste pytania, ale trochę mi już uleciały z głowy takie rzeczy):
1. Warstwy mogą być prawo- lub lewostronne i te dwa podziały są na ogół różne. Skąd wiadomo, który z nich otrzymujemy? A może z jakiegoś powodu te podziały są takie same w przypadku stabilizatora?
2. Jeśli już wiadomo, który otrzymamy, jak najmądrzej wyłowić tych reprezentantów każdej warstwy?-- 2 czerwca 2016, 00:51 --Sprawa tak dalece mnie nękała, że w końcu sam ją sobie wyjaśniłem
Oczywiście można rozważać zarówno warstwy prawo-, jak i lewostronne względem stabilizatora, ale dwie permutacje będą leżały w jednej orbicie wtedy i tylko wtedy, gdy będą wyznaczały tę samą warstwę lewostronną. A to dlatego, że konstruując działanie na jakimkolwiek zbiorze za pomocą grupy permutacji, determinujemy, że będzie to działanie lewostronne. W przypadku działania prawostronnego orbita składałaby się z elementów wyznaczających tę samą warstwę prawostronną. Uff, niby proste, ale potrzebowałem to sobie dobrze wyjaśnić
A jeśli chodzi o drugie pytanie, to chyba wystarczy wziąć sobie jakąkolwiek permutację, która nie stabilizuje grafu i której rozkład na cykle różni się od każdej permutacji ze stabilizatora. Wtedy każda kolejna potęga tej permutacji powinna wpadać do innej warstwy, więc wystarczy aplikować grafowi te kolejne potęgi i będziemy otrzymywać kolejne klasy izomorfizmu. Pytanie tylko, czy zawsze znajdziemy permutację spełniającą takie wymogi, i to rzędu nie mniejszego niż indeks stabilizatora.
Jak na razie sam sobie chętnie postawiłbym pomagajkę, ale jeśli ktoś ma jakieś uwagi albo lepszy pomysł co do pytania drugiego, to będę wdzięczny