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

Изоморфи́зм гра́фов, отношение эквивалентности на множестве графов. Изоморфным отображением одного неориентированного графа на другой называется взаимно однозначное отображение вершин и рёбер одного графа соответственно на вершины и рёбра другого графа, при котором сохраняется отношение инцидентности. Два графа называются изоморфными, если существует изоморфное отображение одного из этих графов на другой. Графы ${\displaystyle G_{1}}$ и ${\displaystyle G_{2}}$, представленные на рисунке, не изоморфны, а ${\displaystyle G_{1}}$ и ${\displaystyle G_{3}}$ изоморфны. Обычно изоморфные графы не различают. Число попарно неизоморфных графов с данным числом вершин и данным числом рёбер конечно. Подобным образом можно определить изоморфизм ориентированных графов, гиперграфов и сетей.

Проблема установления изоморфизма графов является важной проблемой теории графов. Для некоторых классов графов имеются алгоритмы, позволяющие установить изоморфизм достаточно эффективно (например, для деревьев или плоских графов). Для некоторых классов графов с ${\displaystyle n}$ вершинами доказана однозначная (с точностью до изоморфизма) восстанавливаемость графа по набору всех его ${\displaystyle (n-1)}$-вершинных подграфов ${\displaystyle G-v}$, получаемых удалением всевозможных вершин ${\displaystyle v}$. Это установлено, в частности, для деревьев и турниров (при ${\displaystyle n\neq 5,6}$).