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

'''Задача китайского почтальона''' (''[[Chinese postman's problem]]'') - во [[взвешенный граф|взвешенном графе]] найти [[цикл]],  проходящий  через  каждое  [[ребро]]  по крайней мере один раз и такой, что для него суммарная длина (длина каждого ребра учитывается столько раз, сколько это ребро встречается в цикле) минимальна. Если [[граф]] ''[[эйлеров граф|эйлеров]]'', то любой [[эйлеров цикл]] дает оптимальное решение задачи.

[Кристофидес]