Инвариант графа

---

Инвариа́нт гра́фа в теории графов — некоторое обычно числовое значение или упорядоченный набор значений (хеш-функция)^{[источник не указан 832 дня]}, характеризующее структуру графа ${\displaystyle G=\langle A,V\rangle }$ и не зависящее от способа обозначения вершин или графического изображения графа. Играет важную роль при проверке изоморфизма графов, а также в задачах компьютерной химии.

В качестве инварианта можно рассматривать не одно из приведенных выше чисел, а их кортеж (супериндекс) вида ${\displaystyle (p_{0},p_{1},p_{2},\dots )}$, которому, в свою очередь, может быть сопоставлен многочлен вида

суммирование ведется до последнего отличного от нуля значения ${\displaystyle p_{i}}$. Подобным образом можно ввести ещё несколько инвариантов графа:

Системы инвариантов графа, зависящие от двух и более параметров, можно записать в виде многочленов от нескольких формальных переменных ${\displaystyle x,y,z,\dots }$ Например:

Инвариант называется полным, если совпадения инвариантов графов необходимо и достаточно для установления изоморфизма. Например, каждое из значений ${\displaystyle \mu _{min}(G)}$ и ${\displaystyle \mu _{max}(G)}$ является полным инвариантом для графа с фиксированным числом вершин ${\displaystyle n}$.

---