Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

узлов, попавших в С, то узел с пометкой j — 1 также должен

разделяющие в цикле те же множества узлов, что и дуга ltj в де­ реве.

Упражнения

1.Найти потоко-эквивалентное дерево для сети, изображен ной на рис. 9.1.

2.Привести алгоритм, превращающий потоко-эквивалентное

дерево в потоко-эквивалентный путь. Например, дерево на рис. 9.18 является потоко-эквивалентным пути на рис. 9.27.

Ри с . 9.27.

3.Решить задачу синтеза сети с минимальной пропускной спо­ собностью, если заданы требования, представленные на рис. 9.28:

а) найти доминирующую сеть;

Решить задачу синтеза многополюсной сети с минимальной про­ пускной способностью, чтобы при этом требования точно выпол­ нялись как равенства.

Дополнение

1. Предположим, что имеется неориентированная сеть с п узла­ ми и требуется найти максимальные потоки между р узлами неко • торого заданного подмножества узлов. Алгоритм, предложенный Аккерсом [2], заключается в упрощении сети таким образом, что­ бы упрощенная сеть оставалась потоко-эквивалентной исходной

Р и с . 9.30.

сети по отношению к заданному подмножеству узлов. Пусть N t — некоторый узел, не принадлежащий заданному подмножеству узлов и инцидентный некоторым трем узлам, как показано на рис. 9.30 (а). Тогда узел N t может быть удален из сети, а сеть примет вид, изображенный на рис. 9.30 (б). Если применить этот

ваниям к потоку (см. Гомори и Ху [90]).

Нерешенные задачи

1. Пусть пропускные способности дуг в неориентированной сети принимают только значения 0 и 1. Каковы необходимые и до­ статочные условия, которым должны удовлетворять элементы квадратной матрицы, чтобы они являлись величинами максималь­ ных потоков между всеми парами узлов в некоторой сети? (Заме-

190 ГЛ. 9. МНОГОПОЛЮСНЫЕ МАКСИМАЛЬНЫЕ ПОТОКИ

тим, что неравенство треугольника в этом случае является необ­ ходимым условием, но не достаточным.)

2. При синтезе сети минимальной пропускной способности в оптимальном решении пропускные способности дуг могут быть полуцелыми числами. Как построить сеть минимальной пропуск­ ной способности, чтобы пропускные способности дуг были бы все целыми числами?

3. Задана сеть с ограниченными пропускными способностями

от N I-, N 2 ', . . . , N h> и обладающее минимальной пропускной спо­ собностью с (1 , 2 , . . . , к\ 1 ', 2 ', . . . , к').

4. Задана неориентированная сеть с ограниченными пропуск­ ными способностями дуг. Найти множество дуг, удаление которых из сети разбивает ее на к компонент, причем это множество долж­ но обладать минимальной пропускной способностью. (Заметим, что при к = 2 и к — п — 1 задача тривиальна.)

5. Пусть пропускные способности дуг не ограничены, а зада­ ны ограниченные пропускные способности узлов. Рассмотреть для этого случая задачи реализации, анализа и синтеза сети.

192 ГЛ. 10. КРАТЧАЙШИЕ ЦЕПИ И ПОТОКИ МИНИМАЛЬНОЙ СТОИМОСТИ

Попытаемся удалить из этого графа как можно больше дуг так, чтобы при этом сохранилось по одной цепи из N s в каждый узел N t. (Если существует только одна кратчайшая цепь из узла N s в узел N t, то нельзя уже удалить ни одной дуги.) Если имеется, напри

цепи — Ам или А и). После удаления всех таких «лишних» дуг останется граф, который будет деревом. Таким образом, если некоторая дуга А и принадлежит этому дереву, то кратчайшей цепью из N t в N j будет сама эта дуга А ц. Алгоритм, рассматривае­ мый ниже, позволяет получить такое дерево.

Итак, надо построить дерево, которое содержит кратчайшие цепи из узла N s во все остальные узлы сети. Дуги сети, принад­ лежащие этому дереву, будем называть дугами дерева, а дуги, не принадлежащие ему — дугами вне дерева. После того как дерево будет построено, каждая кратчайшая цепь будет состоять из дуг дерева. В начале алгоритма все дуги сети считаются дугами вне дерева. В процессе работы алгоритма количество дуг дерева посте­ пенно увеличивается от 0 до п — 1 , где п — число узлов данной

сети.

Работа алгоритма начинается следующим образом: полагаем, что узел N s принадлежит искомому дереву. Предположим теперь, что найдено т дуг дерева (т = 0, 1, . . ., п — 2). Длину кратчай­ шей цепи из узла N s в узел N h обозначим Lsk. Рассмотрим цепи из N a в Nh, содержащие, кроме дуг дерева, не более одной дуги вне дерева. Длину кратчайшей среди таких цепей обозначим L'sh. Если все цепи из N s в N h содержат на некотором шаге алгоритма больше одной дуги вне дерева, то полагаем L'sk = оо. Заметим, что величина L'sh зависит от т : она изменяется по мере увеличе­