Определение кратчайших гамильтоновых циклов в неориентированном графе
Наукові видання Харківського національного університету Повітряних Сил
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Определение кратчайших гамильтоновых циклов в неориентированном графе
Визначення найкоротших гамільтонових циклів в неорієнтованому графі Determination of the shortest Hamiltonian cycles in the unoriented count |
|
| Creator |
С.В. Листровой
В.А. Пудов В.В. Калачева С.В. Лістровий В.А. Пудов В.В. Калачова S. Listrovoj V. Pudov V. Kalachova |
|
| Subject |
Математичні моделі та методи
УДК 681.3 |
|
| Description |
Рассматривается актуальная задача коммивояжера, состоящая в нахождении в обыкновенном взвешенном графе гамильтонова пути наименьшего, где вес цикла определяется как сумма весов, входящих в него ребер. Предлагается новый алгоритм определения кратчайших гамильтоновых циклов, который не гарантирует нахождения точного решения, но предположительно является более быстрым, чем существующие. Выводится соответствие кратчайшего гамильтонова цикла в самом графе гамильтонову циклу в структуре клик графа. Доказывается эффективность развала структуры до одного цикла на основе процедуры А.
Розглядається актуальне завдання комівояжера, що полягає в знаходженні в звичайному зваженому графі гамільтонова шляху найменшого, де вага циклу визначається як сума ваг вхідних в нього ребер. Пропонується новий алгоритм визначення найкоротших гамільтонових циклів, який не гарантує знаходження точного рішення, але імовірно є швидшим, ніж існуючу. Виводиться відповідність найкоротшого гамільтонова циклу в самому графі гамільтонову циклу в структурі клік графа. Доводиться ефективність розвалу структури до одного циклу на основі процедури А. The actual task of traveling salesman, consisting of finding in the usual self-weighted count of Hamiltonian way of the least, is examined, where weight of cycle concernes as sum of scales, ribs incoming in him. The new algorithm of determination of the shortest Hamiltonian cycles, which does not guarantee finding of exact decision, is offered, but probably is more rapid, than existing. Accordance of the shortest Hamiltonian cycle hatches in a count to the Hamiltonian cycle in the structure of cliques of count. Efficiency of disintegration of structure is proved to one cycle on the basis of procedure of А.. |
|
| Publisher |
Харківський національний університет Повітряних Сил ім. І. Кожедуба
Харьковский национальный университет Воздушных Сил им. И. Кожедуба Kharkiv national Air Force University named after I. Kozhedub |
|
| Date |
2006
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion Рецензована стаття |
|
| Format |
application/pdf
|
|
| Identifier |
http://www.hups.mil.gov.ua/periodic-app/article/5180
|
|
| Source |
Системи обробки інформації. — 2006. — № 5(54). 155-160
Системы обработки информации. — 2006. — № 5(54). 155-160 Information Processing Systems. — 2006. — № 5(54). 155-160 1681-7710 |
|
| Language |
rus
|
|
| Relation |
http://www.hups.mil.gov.ua/periodic-app/article/5180/soi_2006_5_29.pdf
|
|