Задача китайского почтальона: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Задача китайского почтальона''' (''Chinese postman's problem'') - во взвешенном графе на...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Задача китайского почтальона''' (''Chinese postman's problem'') | '''Задача китайского почтальона''' (''[[Chinese postman's problem]]'') — во [[взвешенный граф|взвешенном графе]] найти [[цикл]], проходящий через каждое [[ребро]] по крайней мере один раз и такой, что для него суммарная длина (длина каждого ребра учитывается столько раз, сколько это ребро встречается в цикле) минимальна. Если [[граф]] ''[[эйлеров граф|эйлеров]]'', то любой [[эйлеров цикл]] дает оптимальное решение задачи. | ||
во взвешенном графе найти цикл, проходящий через каждое ребро по | |||
крайней мере один раз и такой, что для него суммарная длина (длина | |||
каждого ребра учитывается столько раз, сколько это ребро встречается в | |||
цикле) минимальна. Если граф ''эйлеров'', то любой эйлеров цикл дает | |||
оптимальное решение задачи. | |||
==Литература== | ==Литература== | ||
* Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978. | |||
Текущая версия от 13:25, 11 февраля 2011
Задача китайского почтальона (Chinese postman's problem) — во взвешенном графе найти цикл, проходящий через каждое ребро по крайней мере один раз и такой, что для него суммарная длина (длина каждого ребра учитывается столько раз, сколько это ребро встречается в цикле) минимальна. Если граф эйлеров, то любой эйлеров цикл дает оптимальное решение задачи.
Литература
- Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.