Abstract: Изучаетсягенерическаясложностьдвухвариантовпроблемыизоморфизма графов с n вершинами, у которых ребра раскрашены в n цветов: проблемы распознавания и проблемы поиска. В проблеме распознавания нужно установить факт наличияилиотсутствия изоморфизма, а впроблемепоиска нужно по паре изоморфных графов найти хотя бы один изоморфизм. К проблеме распознавания изоморфизма цветных графов полиномиально сводится классическая проблема изоморфизма графов, для которой неизвестны полиномиальныеалгоритмы. Доказывается, что для проблемыраспознавания изоморфизма цветных графов существует полиномиальный генерический алгоритм, которыйрешаетеедляпочтивсехвходов.Сдругойстороны,приусловиитрудноразрешимости проблемы поиска изоморфизма цветных графов строится ее подпроблема, для которой не существует генерического полиномиального алгоритма.

Cite: Рыбалов А.Н.
О генерической сложности проблемы изоморфизма цветных графов
Вестник Омского университета. 2026. Т.31. №1. С.13-19.

Dates:

Submitted:	Oct 9, 2025
Accepted:	Nov 27, 2025
Published print:	Mar 18, 2026

Identifiers: No identifiers