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

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

Даты:

Поступила в редакцию:	9 окт. 2025 г.
Принята к публикации:	27 нояб. 2025 г.
Опубликована в печати:	18 мар. 2026 г.

Идентификаторы БД: Нет идентификаторов