5.1. Некоторые родственные задачи

Сразу же вспоминается ряд вопросов, связанных с тем, имеется ли в неориентированном графе эйлеров цикл. Например:

(i) Каково наименьшее число цепей или циклов необходимо для того, чтобы каждое ребро графа содержалось точно в одной цепи или в одном цикле? Очевидно, что если имеет эйлерову цепь или эйлеров цикл, то ответом будет число один.

(ii) Ребрам графа приписаны положительные веса. Требуется найти цикл, проходящий через каждое ребро графа по крайней мере один раз и такой, что для него общий вес (а именно сумма величин где число показывает, сколько раз

проходилось ребро вес ребра) минимален. Очевидно, что если содержит эйлеров цикл, то любой такой цикл будет оптимальным, так как каждое ребро проходится только один раз и вес этого цикла равен тогда 2 с

Сформулированпая выше задача (ii) называется задачей китайского почтальона [18], и ее решение имеет много потенциальных приложений, как например:

(A) Сбор мусора. Рассмотрим проблему сбора домашнего мусора. Допустим, что определенный район города обслуживается единственной машиной. Ребра графа представляют дороги, а вершины — пересечения дорог. Величина с вес ребра — будет соответствовать длине дороги. Тогда проблема сбора мусора в данном районе сводится к нахождению цикла в графе проходящего по каждому ребру по крайней мере один раз. Требуется найти цикл с наименьшим километражем. В действительности емкость машины и продолжительность рабочего дня накладывают ограничения на число улиц, которые может обслужить одна машина за день. То, что действительно может требоваться, — это не нахождение отдельного цикла, а некоторого числа циклов, обслуживаемых по одному в день, скажем, за период в дней; при этом циклы могут быть выбраны так, что не нарушаются вышеупомянутые ограничения [1, 2, 4, 11, 22].

(Б) Доставка молока или почты. Еще две задачи, когда требуется определить маршрут, проходящий хотя бы один раз по каждой из улиц, возник" при доставке молока или почты. Здесь задача состоит в нахождении маршрута, минимизирующего общий километраж (или время, стоимость и т. д.).

(B) Проверка электрических, телефонных или железнодорожных линий. Проблема инспектирования распределенных систем (лишь некоторые из которых названы выше) связана с непременным требованием проверки всех «компонент». Поэтому она также является проблемой типа (ii) или близка к ней.

Другие приложения могут быть связаны с разбрасыванием смеси песка и соли на главных дорогах зимой для предотвращения обледенения, с наилучшим методом работы автоматических вентиляционных устройств, с уборкой помещений и коридоров в больших учреждениях и даже с наилучшим маршрутом осмотра музея!