Zrozumienie izomorfizm grafu

[Fray]

Witam.

Po dość długim wytężaniu mózgu doszedłem do wniosku, że cały ten izomorfizm sprowadza się do tego aby pokazać, że w dwóch grafach możemy znaleźć taką bijekcję wierzchołków, że jeżeli krawędzie łączyły wierzchołki \(\displaystyle{ u}\) i \(\displaystyle{ v}\) z grafu \(\displaystyle{ G}\), a izomorfizm przyporządkował \(\displaystyle{ u \rightarrow a, v \rightarrow b}\), to w grafie \(\displaystyle{ H}\) będzie istniała krawędź \(\displaystyle{ \{ab\}}\).

Czy to jest słuszne rozumowanie? To tak jakbyśmy szukając izomorfizmu z \(\displaystyle{ G}\) do \(\displaystyle{ H}\) przesuwali wierzchołki z \(\displaystyle{ G}\), nie niszcząc żadnych krawędzi. Czy wszystko się sprowadza do tego, że graf "inaczej" wygląda wizualnie, a wierzchołki i połączenia między nimi są zachowane.

Czy to rozumowanie ma sens? Dodam, że oczywiście znam definicje.

Pozdrawiam,
Fray

[ravgirl]

Czy to jest słuszne rozumowanie? To tak jakbyśmy szukając izomorfizmu z G do H przesuwali wierzchołki z G, nie niszcząc żadnych krawędzi. Czy wszystko się sprowadza do tego, że graf "inaczej" wygląda wizualnie, a wierzchołki i połączenia między nimi są zachowane.

Tak. Na przykład:

[Fray]

Ok. To teraz na czym polega automorfizm? Czy to z kolei działa w ten sposób, że mamy graf \(\displaystyle{ G = ( V, E)}\), rysujemy graf, następnie jego kopię bez przepisywania wierzchołków i staramy się tak przyporządkować te wierzchołki ze starego grafu, żeby ponownie wszystkie krawędzie były zachowane?

Czy istnieje jakaś metoda policzenia wszystkich izomorfizmu grafu krócej niż rozpatrując wszystkie przypadki?

Znam wzór: \(\displaystyle{ \frac{n!}{aut(G)}}\) dla \(\displaystyle{ n = |V|}\)

Pozdrawiam,
Fray

[norwimaj]

Po dość długim wytężaniu mózgu doszedłem do wniosku, że cały ten izomorfizm sprowadza się do tego aby pokazać, że w dwóch grafach możemy znaleźć taką bijekcję wierzchołków, że jeżeli krawędzie łączyły wierzchołki \(\displaystyle{ u}\) i \(\displaystyle{ v}\) z grafu \(\displaystyle{ G}\), a izomorfizm przyporządkował \(\displaystyle{ u \rightarrow a, v \rightarrow b}\), to w grafie \(\displaystyle{ H}\) będzie istniała krawędź \(\displaystyle{ \{ab\}}\).

To nie jest poprawna definicja izomorfizmu. Przy izomorfizmie, dwa wierzchołki jednego grafu są połączone krawędzią wtedy i tylko wtedy, gdy ich obrazy są połączone krawędzią w drugim grafie.