Рассматривается актуальная задача коммивояжера, состоящая в нахождении в обыкновенном взвешенном графе гамильтонова пути наименьшего, где вес цикла определяется как сумма весов, входящих в него ребер. Предлагается новый алгоритм определения кратчайших гамильтоновых циклов, который не гарантирует нахождения точного решения, но предположительно является более быстрым, чем существующие. Выводится соответствие кратчайшего гамильтонова цикла в самом графе гамильтонову циклу в структуре клик графа. Доказывается эффективность развала структуры до одного цикла на основе процедуры А.
Бібліографічний опис для цитування:
Листровой С. В.
Определение кратчайших гамильтоновых циклов в неориентированном графе / С.
В.
Листровой
,
В.
А.
Пудов
,
В.
В.
Калачева
// Системи обробки інформації. — 2006. — № 5. — С. 155-160.
ENG
