Введение

Свойство графов, которое зависит только от абстрактной структуры.

В теории графов свойство графа или инвариант графа — это характеристика графа, зависящая исключительно от его абстрактной структуры и не зависящая от конкретных способов его представления, таких как маркировка вершин или визуализация.

Определения

Хотя построение и представление графов являются допустимыми темами в теории графов, для фокусировки исключительно на абстрактной структуре графов, свойство графа определяется как свойство, сохраняющееся при всех возможных изоморфизмах графа. Иными словами, это свойство самого графа, а не конкретного изображения или представления графа. Неформально термин "инвариант графа" используется для свойств, выраженных количественно, тогда как "свойство" обычно относится к описательным характеристикам графов. Например, утверждение "граф не содержит вершин степени 1" является "свойством", а "количество вершин степени 1 в графе" – "инвариантом". Более формально, свойство графа – это класс графов, обладающий тем свойством, что любые два изоморфных графа либо оба принадлежат этому классу, либо оба не принадлежат ему.

Инварианты графов и изоморфизм графов

Легко вычисляемые инварианты графа играют важную роль в быстром определении изоморфизма графа, или, точнее, неизоморфизма, поскольку для любого инварианта два графа с различными значениями не могут (по определению) быть изоморфными. Однако два графа с одинаковыми инвариантами могут быть как изоморфными, так и неизоморфными. Инвариант графа I(G) называется полным, если совпадение инвариантов I(G) и I(H) влечет за собой изоморфизм графов G и H. Нахождение эффективно вычисляемого такого инварианта (проблема канонизации графа) означало бы простое решение сложной задачи об изоморфизме графов. Однако даже инварианты, принимающие полиномиальные значения, такие как хроматический полином, обычно не являются полными. Например, граф «коготь» и путь на 4 вершинах имеют один и тот же хроматический полином.