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

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

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

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