Об одной задаче комбинаторного поиска

В работе исследуется задача поиска неориентированных гамильтоновых циклов в полном графе на $n$ вершинах при помощи безусловных реберных тестов. Доказывается, что минимальный тест содержит в точности $n(n-3)/2-\lfloor n/3\rfloor+1$ ребер. Предлагается явная характеризация всех минимальных различающих наборов ребер.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проекты 02–01–00985 и 00–15–96103, программы “Университеты России” и ФЦП “Интеграция”.