Почему мы делаем изоморфизм, автоморфизм и гомоморфизм?

Каковы основные различия между этими тремя терминами изоморфизм, автоморфизм и гомоморфизм в простом языке неспециалистов и почему мы делаем изоморфизм, автоморфизм и гомоморфизм?

Изоморфизм формализует понятие равных графов. Например, на этом рисунке вы видите три изоморфных графика

Более формально, изоморфизм графов и является биекцией которая сохраняет смежность. То есть:$G_1$$G_2$$f:V(G_1) \mapsto V(G_2)$

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

Нетрудно найти такую ​​биекцию для каждой пары графиков на картинке.

Теперь, если то полученное отображение становится автоморфизмом - изоморфизмом из графа в себя.$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.$

и, как вы можете видеть, графики «выглядят» довольно симметрично. Именно потому, что он имеет «много» автоморфизмов описанного типа.

Гомоморфизмы графа обычно не изучаются неспециалистом и имеют более или менее теоретические цели. Например, они тесно связаны с понятием окраски вершин. Смотрите также гипотезу Хадвигера

В контексте теории графов гомоморфизм - это отображение между двумя графами, которое отображает смежные вершины в на смежные вершины в . Другими словами, для каждого ребра ребро . Гомоморфизм графов подразумевает множество свойств, в том числе приводит к раскраске графов. G = ( V , E ) G ′ = ( V ′ , E ′ ) e = ( u , v ) ∈ E ( h ( u ) , h ( v ) ) ∈ E $h:G\rightarrow G'$$G=(V,E)$$G'=(V',E')$$e=(u,v) \in E$$(h(u),h(v))\in E'$

Теперь изоморфизм графов - это биективный гомоморфизм, то есть обратный он также является гомоморфизмом. Если два графа изоморфны, то это, по сути, один и тот же граф, только с перемаркировкой вершин. Проблема определения того, являются ли два графа изоморфными друг другу, является важной проблемой в теории сложности.

Наконец, автоморфизм - это изоморфизм из графа в себя.