1. Наука
  2. Видання
  3. Системи обробки інформації
  4. 5(54)'2006
  5. Определение кратчайших гамильтоновых циклов в неориентированном графе

Определение кратчайших гамильтоновых циклов в неориентированном графе

С.В. Листровой, В.А. Пудов, В.В. Калачева
Системи обробки інформації. — 2006. — № 5(54). С. 155-160.
УДК 681.3
Мова статті: російська
Анотації на мовах:


Анотація: Рассматривается актуальная задача коммивояжера, состоящая в нахождении в обыкновенном взвешенном графе гамильтонова пути наименьшего, где вес цикла определяется как сумма весов, входящих в него ребер. Предлагается новый алгоритм определения кратчайших гамильтоновых циклов, который не гарантирует нахождения точного решения, но предположительно является более быстрым, чем существующие. Выводится соответствие кратчайшего гамильтонова цикла в самом графе гамильтонову циклу в структуре клик графа. Доказывается эффективность развала структуры до одного цикла на основе процедуры А.


Інформація про авторів публікації:
Бібліографічний опис для цитування:
Листровой С.В., Пудов В.А., Калачева В.В. Определение кратчайших гамильтоновых циклов в неориентированном графе. Системи обробки інформації. 2006. № 5(54). С. 155-160.