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?

graph-theory

— Xara
źródło

18

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

Bardziej formalnie, izomorfizm wykresów i jest bijectionem który zachowuje przyleganie. To jest do powiedzenia: $G_1$ $G_2$ $f:V(G_1) \mapsto V(G_2)$

u \sim_{G_{1}} v ⟺ f (u) \sim_{G_{2}} f (v)

$u \sim_{G_1} v \iff f(u) \sim_{G_2} f(v)$

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

$G_1 = G_2$

$f$ $G$ $v$ $u$ $u$ $v$

$G$ $u,v \in V(G)$ $f:V(G) \mapsto 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:G\rightarrow G'$ $G=(V,E)$ $G'=(V',E')$ $e=(u,v) \in E$ $(h(u),h(v))\in 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