Jakie są kluczowe różnice między tymi trzema terminami: izomorfizm, automorfizm i homomorfizm w prostym języku laika i dlaczego robimy izomorfizm, automorfizm i homomorfizm?
źródło
Jakie są kluczowe różnice między tymi trzema terminami: izomorfizm, automorfizm i homomorfizm w prostym języku laika i dlaczego robimy izomorfizm, automorfizm i homomorfizm?
Izomorfizm formalizuje pojęcie równych wykresów. Na przykład na tym rysunku widać trzy wykresy izomorficzne
Bardziej formalnie, izomorfizm wykresów i G 2 jest bijectionem f : V ( G 1 ) ↦ V ( G 2 ), który zachowuje przyleganie. To jest do powiedzenia:
Nietrudno znaleźć taki bijection dla każdej pary wykresów na zdjęciu.
i jak widać wykresy „wyglądają” dość symetrycznie. To właśnie dlatego, że ma „wiele” automorfizmów opisywanego typu.
Homomorfizmy wykresów zwykle nie są badane przez laika i są mniej więcej celami teoretycznymi. Na przykład są one ściśle związane z pojęciem kolorowania wierzchołków. Zobacz także Hipoteza Hadwigera
Teraz wykres izomorfizm jest homomorfizmem bijectywnym, co oznacza, że jego odwrotność jest również homomorfizmem. Jeśli dwa wykresy są izomorficzne, to są one zasadniczo tym samym wykresem, tylko z ponownym oznakowaniem wierzchołków. Problem określania, czy dwa wykresy są względem siebie izomorficzne, jest ważnym problemem w teorii złożoności.
Wreszcie automorfizm to izomorfizm od samego wykresu.
źródło