Задача китайского почтальона: различия между версиями

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

Навигация