Задача листоноші
Матеріал з Вікіпедії — вільної енциклопедії.
Задача (китайського) листоноші (англ. Chinese postman problem або англ. Route inspection problem) — задача пошуку найкоротшого циклу в графі, що включає всі ребра. Існують варіанти задачі для орієнтованих та неорієнтованих графів та для графів, частина ребер яких орієнтована, а частина — ні.
Задача отримала назву завдяки Алану Голдману (англ. Alan Goldman) з NIST, оскільки першим дослідником цієї задачі був китайський математик Мей-Ку Кван (англ. Mei-Ku Kuan, 1962).[1]
Посилання [ред.]
Дивіться також [ред.]
Література [ред.]
- Майника Э. (1981). Алгоритмы оптимизации на сетях и графах. М.: Мир. Проігноровано невідомий параметр
|сторінок=(довідка)
