Dlaczego robimy izomorfizm, automorfizm i homomorfizm?

13

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?

Xara
źródło

Odpowiedzi:

18

Izomorfizm formalizuje pojęcie równych wykresów. Na przykład na tym rysunku widać trzy wykresy izomorficznewprowadź opis zdjęcia tutaj

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:G1G2f:V(G1)V(G2)

uG1vf(u)G2f(v)

Nietrudno znaleźć taki bijection dla każdej pary wykresów na zdjęciu.

G1=G2

fGvuuv

Gu,vV(G)f:V(G)V(G)f(u)=v.wprowadź opis zdjęcia tutaj

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

Jernej
źródło
1
... homomorfizmy zwykle nie są badane przez laika ... przezabawne! +1
Pratik Deoghare
8

h:GGG=(V,E)G=(V,E)e=(u,v)E(h(u),h(v))E

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.

Marc Khoury
źródło