Аннотация:
В работе исследуется задача поиска неориентированных гамильтоновых циклов в полном
графе на $n$ вершинах при помощи безусловных реберных тестов. Доказывается, что минимальный тест содержит в точности $n(n-3)/2-\lfloor n/3\rfloor+1$ ребер. Предлагается явная характеризация всех минимальных различающих наборов ребер.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проекты 02–01–00985 и 00–15–96103, программы “Университеты России” и ФЦП “Интеграция”.
Статья поступила: 24.05.2002
Реферативные базы данных:
УДК:519.6
Образец цитирования:
Е. В. Дебрев, “Об одной задаче комбинаторного поиска”, Дискрет. матем., 14:3 (2002), 8–17; Discrete Math. Appl., 12:4 (2002), 325–335