Слайд 8
Локальные инварианты
Примеры инвариантов вершин:
Степень вершины
Количество путей заданной длины,
проходящих через вершину
Количество циклов, проходящих через вершину
…
Примеры локальных инвариантов:
Количество
путей заданной длины, принадлежащих фрагменту
Цикломатическое число фрагмента
Хроматическое число фрагмента
…
Слайд 9
Алгоритм распознавания изоморфизма графов
Основная процедура – генерация перестановок,
осуществляющих изоморфизм
До запуска этой процедуры производится проверка равенства инвариантов
рассматриваемых графов; если обнаружено неравенство, графы не изоморфны
Каждая перестановка-кандидат проверяется на сохранение локальных инвариантов
Для простоты будем рассматривать только инварианты вершин
