Задача китайского почтальона: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Задача китайского почтальона''' (''Chinese postman's problem'') - во взвешенном графе на...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Задача китайского почтальона''' (''Chinese postman's problem'') - | '''Задача китайского почтальона''' (''[[Chinese postman's problem]]'') - во [[взвешенный граф|взвешенном графе]] найти [[цикл]], проходящий через каждое [[ребро]] по крайней мере один раз и такой, что для него суммарная длина (длина каждого ребра учитывается столько раз, сколько это ребро встречается в цикле) минимальна. Если [[граф]] ''[[эйлеров граф|эйлеров]]'', то любой [[эйлеров цикл]] дает оптимальное решение задачи. | ||
во взвешенном графе найти цикл, проходящий через каждое ребро по | |||
крайней мере один раз и такой, что для него суммарная длина (длина | |||
каждого ребра учитывается столько раз, сколько это ребро встречается в | |||
цикле) минимальна. Если граф ''эйлеров'', то любой эйлеров цикл дает | |||
оптимальное решение задачи. | |||
==Литература== | ==Литература== | ||
[Кристофидес] | [Кристофидес] | ||
Версия от 16:17, 20 октября 2009
Задача китайского почтальона (Chinese postman's problem) - во взвешенном графе найти цикл, проходящий через каждое ребро по крайней мере один раз и такой, что для него суммарная длина (длина каждого ребра учитывается столько раз, сколько это ребро встречается в цикле) минимальна. Если граф эйлеров, то любой эйлеров цикл дает оптимальное решение задачи.
Литература
[Кристофидес]