Изоморфизм графов

---

В теории графов изоморфизмом графов ${\displaystyle G=\left\langle V_{G},E_{G}\right\rangle }$ и ${\displaystyle H=\left\langle V_{H},E_{H}\right\rangle }$ называется биекция между множествами вершин графов ${\displaystyle f\colon \ V_{G}\rightarrow V_{H}}$ такая, что любые две вершины ${\displaystyle u}$ и ${\displaystyle v}$ графа ${\displaystyle G}$ смежны тогда и только тогда, когда вершины ${\displaystyle f(u)}$ и ${\displaystyle f(v)}$ смежны в графе ${\displaystyle H}$. Здесь графы понимаются неориентированными и не имеющими весов вершин и ребер. В случае, если понятие изоморфизма применяется к ориентированным или взвешенным графам, накладываются дополнительные ограничения на сохранение ориентации дуг и значений весов. Если изоморфизм графов установлен, они называются изоморфными и обозначаются как ${\displaystyle G\simeq H}$.

---