grafy izomorfizm automorfizm

[kriegor]

co to jest automorfizm grafow? podobono izomorfizm grafu w samego siebie ale jesli dobrze rozumiem izomorfizm grafu to jest to po prostu permutacja jego wierzcholkow no to jakos nie widze czym by mial byc automorfizm, jakis przyklad?

i tak od razu zeby po cos to bylo to takie zadanie:
oblicz ile jest nieizomorficznych turniejow (skierowana klika) o \(\displaystyle{ 5}\) wierzcholkach.

no to pewnie jakos trzeba z lematu burnsidea ale zupelnie nie wiem co tutaj ma byc grupa dzialajaca na graf, zawsze to byly po prostu obroty lub symetrie i sprawa byla jasna-- 21 sie 2012, o 18:02 --da sie to jakos zrobic w ogolnosci a nie tylko dla \(\displaystyle{ 5}\)-wierzcholkowego turnieju ?

[szw1710]

Nie studiowałem teorii grafów, więc podzielę się intuicją. W automorfizmie chyba chodzi o to, żeby zbiór wierzchołków przekształcić na zbiór wierzchołków wzajemnie jednoznacznie i to w ten sposób, żeby spełnić warunek: jeśli dwa punkty są połączone krawędzią, to ich obrazy także. Nawet w dwie strony: wtedy i tylko wtedy. W szczególności, jeśli mamy graf pełny (każde dwa różne wierzchołki są połączone krawędzią), to każda bijekcja zbioru wierzchołków będzie automorfizmem w proponowanym sensie.

[norwimaj]

jesli dobrze rozumiem izomorfizm grafu to jest to po prostu permutacja jego wierzcholkow

Oczywiście nie każda permutacja, tylko tak jak napisał szw1710.

no to pewnie jakos trzeba z lematu burnsidea ale zupelnie nie wiem co tutaj ma byc grupa dzialajaca na graf, zawsze to byly po prostu obroty lub symetrie i sprawa byla jasna

Może wszystkie permutacje wierzchołków? I zliczyć trzeba dla każdej permutacji liczbę turniejów takich, że zwrot strzałek jest zachowany. Można też próbować policzyć bez lematu Burnside'a, rozrysowując wszystkie nieizomorficzne turnieje, ale sposób z lematem chyba jest prostszy.

[kriegor]

Może wszystkie permutacje wierzchołków?

no dobra to pojde w ta strone tylko chyba wciaz nie czuje tej izomorficznosci
no bo zeby rozwazac jakies permutacje to musze te wierzcholki grafu poetykietowac ??
i teraz ide po wszystkich permutacjach i zliczam ich punkty stale ? po wszystkich \(\displaystyle{ 120}\) pewnie isc nie bedzei trzeba bo rozlozy sie je na cykle i wiadomo ile jest permutacji o danej budowie cyklowej co skroci rachunki, tak teraz glosno mysle
ale sie nie moge przelamac i zaczac bo jak biore jakas permutacje powiedzmy \(\displaystyle{ (1)(24)(35)}\) to przychodzi moment zeby zobaczyc jakie turnieje sa po przepuszczeniu przez ta permutacje takie same a tego po prostu nie czuje, nie widze tutaj zadnej metody jak sobie pomoc i latwo sprawdzac ktore sa izomorficzne, pomijajac fakt ze nie wiem co z tym etykietowaniem

jest \(\displaystyle{ 10}\) krawedzi czyli tak jakbym sobie mial narysowac wszystkie te turnieje to byloby ich \(\displaystyle{ 2^{10}}\)
przypadek ogolny na ta chwile wydaje mi sie niemozliwy, juz ten jest ciezki

[norwimaj]

Tak, wierzchołki etykietujemy, na przykład liczbami od \(\displaystyle{ 1}\) do \(\displaystyle{ 5}\). Wtedy wiadomo, co oznacza zapis \(\displaystyle{ \sigma=(1)(24)(35)}\).

Jeśli w danej permutacji jest cykl długości \(\displaystyle{ 2}\), to wtedy nie ma żadnych punktów stałych. No bo jak w tym przykładzie może być skierowana krawędź pomiędzy \(\displaystyle{ 2}\) a \(\displaystyle{ 4}\)? Jeśli jest \(\displaystyle{ 2\to4}\), to jej obrazem jest \(\displaystyle{ \sigma(2)\to\sigma(4)}\), czyli \(\displaystyle{ 4\to2}\). Można też pokazać, że ogólnie cykle parzystej długości są "złe".

Weźmy trudniejszy przykład, \(\displaystyle{ \tau=(12345)}\). Jeśli ustalimy kierunek krawędzi \(\displaystyle{ 1-2}\), to już mamy ustalone kierunki wszystkich krawędzi wzdłuż cyklu, na przykład jeśli \(\displaystyle{ 1\to2}\), to \(\displaystyle{ 1\to2\to3\to4\to5\to1}\). Podobnie ustalenie kierunków krawędzi \(\displaystyle{ 1-3}\) sprawia, że zwroty wszystkich przekątnych pięciokąta są ustalone. Łącznie mamy więc \(\displaystyle{ 2\cdot2=4}\) punkty stałe, bo dwie możliwości ustalenia zwrotów wzdłuż cyklu i dwie możliwości dla przekątnych.

[kriegor]

ok to ja juz zaczynam to nieco widziec, dzieki
szczegolnie z tym obrazem bylo istotne na przykladzie
ja zupelnie nie wiedzialem jak przeniesc wiedze o lemacie tutaj ale juz jest fajnie
i ten ostatni akapit czaje wiec jest niezle, powinienem dac rade z tym konkretnym przykladem