Решение задачи о назначениях Гамильтонов цикл

,=(1,2,5;

43,4,6)

Рис. 10.21. Преобразование гамильтоновых циклов при стягивании, (а) Решение задачи о назначениях, (б) Гамильтонов цикл.

На рис. 10.21 (а) гамильтонов цикл показан жирной линией, в то время как решение задачи о назначениях показано тонкой линией. После стягивания получается граф, изображенный на рис. 10.21 (б), с двумя дугами, инцидентными 5],з и 1,4, и четырьмя дугами, инцидентными и 2,2-

Если теперь использовать неравенство треугольника, то получим

с, (5 4, 5 з)<с,(5 4, S ,)-bCi(5 2)-l-q(5i,2, 5i,3), (10.21)

и, следовательно, назначение из рис. 10.22 (в котором дуги (-51,4, 1, i) (1,1. (1,2, i.a) заменены дугой (Si, 4, 1,3)) имеет значе-

ние, не превосходяш;ее величины назначения из рис. 10.21 (б). Так как назначение на рис. 10.22 имеет по две дуги, инцидентны? каждой вершине, и решение задачи о назначениях для стянутогс графа имеет меньший вес назначения, то значение решения задач! назначениях, скажем V (ЛPi), является нижней границей дл>

через все п вершин, будет иметь но крайней мере две дуги (одну нанравленную внутрь цикла х, другую - наружу), инцидентные вершинам, не лежаш;им в Sii, и нриходяш;ие в одну или более вершин из Sj, . Число таких дуг будет, очевидно, четным.

Рис. 10.22. Назначение, соответствующее рис. 10.21 (б), с двумя дугами в каждой вершине.

после первого стягивания (т. е. в случае назначения, соответствующего рис. 10.21 (б)) эйлеров цикл, то его всегда можно преобразовать в граф с меньшим (или равным) весом, в котором каждой вершине индицентны только две дуги. Это делается с помощью замены цепи, образованной дугами, ведущими из одной верпшны в другую, единственной дугой между этими вершинами (как было продемонстрировано выше).

Если, с другой стороны, матрица относительных весов Cj не удовлетворяет условию треугольника, то соотношение (10.21) может быть не выполнено. В этом случае матрица должна быть сначала подвергнута компрессии. Значение решения задачи о назначениях с компрессированной матрицей следует взять тогда в качестве нижней границы величины приращения веса, что необходимо при объединении циклов. Это так, ибо компрессия матрицы может лишь уменьшить или оставить без изменения вес любого назначения для первоначальной матрицы.

Аналогично V (АР2) - вес решения задачи о назначениях после второго стягивания является нижней границей веса связываемых циклов, получаемых при этом стягивании, и так далее для третьего, четвертого и остальных стягиваний. Поэтому величина

L = S ViAPi), (10.22)

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

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

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

Рис. 10.23. Первое решение задачи о назначениях.

Рис. 10.24. Решение после первого стягивания.

Рис. 10.25. Решение после второго стягивания.

Стягивание графа из рис. 10.23 дает граф с 4 вершинами, матрица весов которого может быть вычислена по (10.19), и она дана в табл. 10.5 (а). Эта матрица весов не удовлетворяет условию треугольника и поэтому подвергается компрессии. Результат дан в табл. 10.5 (б).

Решение задачи о назначениях с матрицей из табл. 10.5 (б) дает величину V {АР) = 20. Результирующая матрица относительных весов дана в табл 10.6, а решение задачи о назначениях дается графом на рис. 10.24.

Пример вычисления границы

Рассмотрим задачу коммивояжера с 10 вершинами, матрица весов которой симметрична и приведена в табл. 10.3.

Решение начальной задачи о назначениях дает величину V {АРо) = 184. Результирующая матрица относительных весов дана в табл. 10.4, а решение дается графом на рис. 10.23.