Изоморфизм графов: переименование, инварианты и предел уточнения

Если уже отличаешь инвариант от сертификата - переходи к «Теперь сам».

Как думаешь: одинаковые степени означают одинаковый граф?

В базе молекул дважды появились шесть атомов. У каждого по две связи, всего шесть связей. Одна запись описывает кольцо из шести атомов, другая - два отдельных треугольника. Список степеней совпадает. Прежде чем читать программу, ответь: может ли переименование атомов превратить кольцо в два треугольника?

Нет: связный граф останется связным после переименования. Совпавшие степени были только необходимым условием. Программа, которая считает такой отпечаток доказательством равенства, потеряет одну из разных молекул. Поэтому быстрый фильтр и окончательная проверка должны иметь разные роли.

На что это похоже

Представь карту метро, где станции переименовали, а линии оставили. Перестановка подписей не меняет маршруты. Сравнивать две карты по алфавиту названий бесполезно: надо сопоставить станции так, чтобы каждое соединение сохранилось. Если важен цвет линии или тип станции, эти метки тоже входят в условие. Переименование не даёт права превратить пересадочный узел в обычную станцию.

Механизм: от степеней к уточнению цветов

Пусть графы простые, неориентированные и без петель. Ищем перестановку p номеров, для которой v соседствует с u ровно тогда, когда p[v] соседствует с p[u]. Слово «ровно» сохраняет не-рёбра тоже. Это отличает изоморфизм целых графов от поиска произвольного подграфа.

Сначала каждой вершине назначают цвет по её степени. Затем собирают сигнатуру: прежний цвет вершины и отсортированный список цветов соседей. Одинаковые сигнатуры получают один новый цвет, разные - разные. Старый цвет в сигнатуре не позволяет снова склеить уже различённые классы. Повторяем, пока разбиение вершин на цветовые классы перестанет меняться. Это одномерное уточнение Вейсфейлера-Лемана, сокращённо 1-WL.

При сравнении двух графов словарь сигнатур общий: одинаковый номер цвета должен иметь одинаковый смысл. Если размеры цветовых классов различаются, изоморфизма нет. Если все классы одноэлементные, цвета задают единственное возможное сопоставление; его проверяют по рёбрам. Если остались классы с несколькими вершинами, алгоритм ещё не решил задачу. Обычно выбирают одну неопределённую вершину, пробуют соответствия и повторяют уточнение.

При полном переборе вариантов n!; проверка одной перестановки по всем парам занимает O(n²). Это учебный алгоритм, не описание лучших реализаций. Результат Бабаи даёт квазиполиномиальную общую верхнюю границу exp((log n)^O(1)). Слово «квазиполиномиальная» здесь существенно: показатель степени у n не обязан быть постоянным. Полиномиальная проверка сертификата сама по себе не доказывает ни полиномиальное решение, ни NP-полноту.

Правило

Различие инварианта опровергает изоморфизм. Совпадение инвариантов оставляет вопрос открытым. Положительный сертификат - конкретная биекция, сохраняющая все рёбра и не-рёбра. Если в приложении есть метки вершин, рёбер или направления, добавь их в определение сертификата до выбора алгоритма.

Разбор: кольцо и два треугольника

Запусти файл: он сравнивает цветовые отпечатки и отдельно перебирает биекции. Затем вершины кольца переименовываются заведомой перестановкой. Граф с новым именованием должен пройти обе проверки.

from itertools import permutations


def graf(n, rebra):
    g = [set() for _ in range(n)]
    for a, b in rebra:
        g[a].add(b)
        g[b].add(a)
    return g


def cveta(g, h):
    oba = g + [{u + len(g) for u in s} for s in h]
    c = [len(s) for s in oba]
    for _ in range(len(oba)):
        sig = [(c[v], tuple(sorted(c[u] for u in s)))
               for v, s in enumerate(oba)]
        slovar = {s: i for i, s in enumerate(sorted(set(sig)))}
        novye = [slovar[s] for s in sig]
        staroe_chislo = len(set(c))
        c = novye
        if len(set(c)) == staroe_chislo:
            break
    n = len(g)
    return sorted(c[:n]) == sorted(c[n:])


def izomorfny(g, h):
    n = len(g)
    if n != len(h):
        return False
    for p in permutations(range(n)):
        if any(len(g[v]) != len(h[p[v]]) for v in range(n)):
            continue
        if all((u in g[v]) == (p[u] in h[p[v]])
               for v in range(n) for u in range(n)):
            return True
    return False


cikl = graf(6, [(i, (i + 1) % 6) for i in range(6)])
dva = graf(6, [(0, 1), (1, 2), (2, 0),
               (3, 4), (4, 5), (5, 3)])
p = [3, 0, 5, 1, 4, 2]
kopiya = graf(6, [(p[i], p[(i + 1) % 6]) for i in range(6)])
print("кольцо / треугольники:", cveta(cikl, dva),
      izomorfny(cikl, dva))
print("кольцо / копия:", cveta(cikl, kopiya),
      izomorfny(cikl, kopiya))

кольцо / треугольники: True False
кольцо / копия: True True

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

Разбор: почему подграф меняет сложность

Нужно ли найти треугольник внутри большого графа или сопоставить два графа целиком? Это разные вопросы. Изоморфизм подграфа допускает выбор части вершин и, в непорожденной версии, удаление лишних рёбер. При поиске клики размера k просят найти внутри графа полный граф на k вершинах. Поэтому общая задача изоморфизма подграфа включает NP-полные задачи, даже если сравнение двух целых графов к ним не причислено. Название библиотеки «graph matching» не фиксирует нужную постановку.

Что ломается без этого

Хеширование списка степеней склеивает разные структуры. Сравнение матриц смежности без переименования, наоборот, объявляет разными копии одного графа. При помеченных графах игнорирование типа атома создаёт ложное совпадение даже при верной структуре связей. Исправление начинается с точной спецификации равенства, затем выбираются фильтры и проверка сертификата.

Зачем это в работе

Удаление повторов схем, сравнение зависимостей сборок и поиск повторяющихся молекул требуют равенства структуры. Перед дорогим поиском удобно сравнить размеры, компоненты и цветовые отпечатки. Для успешного сравнения сохрани найденную перестановку: она позволяет объяснить пользователю, какой объект сопоставлен какому, и независимо перепроверить ответ.

Теперь сам

Даны цикл из восьми вершин и два цикла по четыре вершины. Пройдёт ли проверка степеней? Различит ли их 1-WL с одинаковыми начальными цветами? Изоморфны ли они?