Изоморфизм графов: Математика структурного сходства
Один и тот же математический граф можно нарисовать на листе бумаги бесконечным множеством способов. Мы можем расположить вершины кругом, квадратом, в виде звезды или хаотично, распутав и запутав ребра. Визуально это будут совершенно разные картинки, но с точки зрения дискретной математики они могут представлять абсолютно идентичную структуру связей. Задача определения структурного тождества двух графов называется проблемой изоморфизма графов.
Формально два графа G и H называются изоморфными, если существует биекция (взаимно-однозначное соответствие) между множествами их вершин, которая сохраняет смежность. Иными словами, если вершины A и B были соединены ребром в первом графе, то их соответствующие двойники обязательно должны быть соединены ребром во втором графе, и наоборот.
Для доказательства того, что графы не изоморфны, математики используют инварианты — свойства, которые не зависят от визуального представления. Если у графов разное количество вершин, ребер или не совпадает набор степеней вершин (например, в одном есть вершина с 5 соседями, а в другом максимум 4) — они точно не изоморфны. Но если все простые инварианты совпадают, поиск изоморфизма превращается в сложнейшую комбинаторную задачу перебора.
С точки зрения теории сложности вычислений (классы P и NP), задача изоморфизма графов обладает уникальным статусом. Долгие десятилетия она считалась одним из главных кандидатов на попадание в класс NP-intermediate — задач, которые лежат в классе NP, но не являются ни P (решаемыми быстро), ни NP-полными (самыми сложными). В 2015 году Ласло Бабаи произвел сенсацию, предложив алгоритм, работающий за квазиполиномиальное время (чуть медленнее, чем класс P, но кардинально быстрее экспоненциального).
Прикладное значение этой задачи колоссально. В хемоинформатике она используется для поиска молекул (где атомы — вершины, а валентные связи — ребра): если химик синтезировал новое вещество, база данных структурно сравнивает его граф с миллионами известных молекул. В проектировании микросхем (EDA) изоморфизм подграфов применяется для верификации (LVS — Layout Versus Schematic), где система проверяет, соответствует ли топология соединений кремниевых транзисторов на физическом чипе исходной принципиальной схеме инженера.
