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

Следствие. Рассмотрим выпуклый многогранник С, определяе­

мый условиями Ах ^ Ь, х ^3=О, где матрица А целочисленна. Тогда

следующие три условия являются эквивалентными.

1'. Матрица А абсолютно унимодулярна.

2'. Все крайние точки многогранника С целочисленны при любом целочисленном векторе Ь.

3'. Каждая невырожденная подматрица матрицы Аобладает целочисленной обратной матрицей.

Положим А = (А, I). Можно легко доказать эквивалентность условий 1 и 1', 2 и 2', 3 и 3'. Покажем, например, что из условия 1' следует условие 1. Пусть М — произвольная невырожденная под­ матрица матрицы А, имеющая ранг т — к. Тогда некоторый базис

Вматрицы А можно представить (после перестановки столбцов)

вследующем виде:

Аналогичными преобразованиями можно получить все осталь­ ные результаты, впервые приведенные в работе [103]. Заметим, что если хотя бы одна из матриц А, Ат, —А, (А, А) или (А, I) абсолютно унимодулярна, то этим свойством обладают и все остальные^выписанные матрицы. Более подробный материал, касающий­ ся рассмотренных преобразований, можно найти в работах [103], [199].

Чтобы проверить, обладает ли матрица А свойством абсолют­ ной унимодулярности, надо провести большую работу, если пере­ бирать все миноры матрицы А. Существуют, однако, достаточные (но не необходимые) условия абсолютной унимодулярности мат­ риц, которые проверяются гораздо легче.

Теорема 8.9. Матрица А абсолютно унимодулярна, если вы­ полняются следующие условия.

1. Каждый ее элемент равен 0, + 1 или —1.

2. Каждый ее столбец содержит не более двух ненулевых эле­ ментов *).

3. Строки матрицы А можно разбить на два непересекающихся множества /?( и Й2 таким образом, что

г) Можно показать, что если матрица А обладает свойством 2, то усло­

вия 1, За, 36 необходимы для абсолютной ушшодулярности матрицы А .—

Прим. ред.

иТ . Ху

а) если столбец из А содержит два ненулевых элемента одного, знака, то один из них входит в Rt, а другой — в R 2,

б) если столбец из А содержит два ненулевых элемента с про­ тивоположными знаками, то оба они входят либо в R\, либо в R 2.

Д оказательство. (Предложено Гофманом в добавлении к рабо­ те [99].) Легко видеть, что любая подматрица матрицы А в свою очередь удовлетворяет условиям теоремы. Поэтому достаточно доказать, что определитель любой квадратной матрицы, удовлет­ воряющей условиям теоремы, равен 0, -(-1 или —1. Доказатель­ ство проведем индукцией по размеру матрицы. Для матрицы размера 1 x 1 теорема выполняется согласно условию (1). Пред­ положим теперь, что теорема верна для матрицы размера (п — 1 ) X,

X (п — 1), и пусть А — матрица размера п X п. Если в некото­ ром столбце все элементы равны 0, то det А = 0. Если в какомнибудь столбце матрицы А только один ненулевой элемент, то разложим определитель матрицы А по элементам этого столбца. Тогда det А = ± А ', где А' — алгебраическое дополнение нену­ левого элемента, равное 0 или ± 1 по индуктивному предположе­

нию. Остается рассмотреть случай, когда каждый столбец матри­ цы А имеет ровно два ненулевых элемента. Тогда из условий (1) —

Упражнения

1. Используя метод расстановки пометок, найти максимальный поток из N s в N t в сети, изображенной на рис. 8.13. В качестве исходного потока взять xsi = xi2 = хгъ — x3t = 2 , остальные xij — 0- (Число, написанное около дуги, обозначает ее пропуск­ ную способность.)

2.Найти минимальное связывающее дерево для сети, изобра­ женной на рис. 8.13, принимая числа, указанные рядом с дугами, за их длины.

3.При доказательстве теоремы о максимальном потоке и мини­

мальном разрезе множество X определялось следующими прави­

х) Действительно, в этом случае строки матрицы А линейно зависимы.—

Прим. ред.

4. Задана сеть, содержащая ориентированные и неориентиро­ ванные дуги; величина максимального потока из N s в N t равна v. Изменится ли величина максимального потока, если заменить

каждую неориентированную дугу пропускной способности Ъ па­ рой ориентированных дуг с противоположными направлениями (причем каждая из них имеет ту же пропускную способность 6)?

Почему?

5. Задана сеть, в которой величина максимального потока из N s в N t равна v. Какова будет величина максимального пото­ ка, если в сеть добавить неориентированную дугу пропускной способности Ь? Что изменится, если дугу с пропускной способ­ ностью Ъ, наоборот, удалить из исходной сети?

Дополнение

1. При получении максимального потока с помощью метода расстановки пометок все пометки стираются после нахождения некоторого пути, увеличивающего поток. В модификации этого метода, предложенной Скоинсом [177] и Джонсоном [119], каждый узел получает 3 пометки. После нахождения некоторого пути, увеличивающего поток, стирается только одна ветвь некоторого дерева, содержащего найденный путь, увеличивающий поток. В работе Джонсона проводится также обсуждение свойств базис­ ных решений в сетевых терминах.

2.В работах Минти [151—154] подробно обсуждаются резуль­ таты, связанные с использованием потоковых задач в электриче­ ских цепях.

3.Всякая сеть может быть описана матрицей инциденций узлов по отношению к дугам. Таким образом, можно определить, что такое разрез для матрицы инциденций узлы — дуги. Рассмотрим теперь произвольную матрицу действительных чисел. Можно ли для нее определить, что такое разрез? Обобщение сетевых понятий на более абстрактные и общие системы проведено в работах Фалкер-

сона [69], Эдмондса и Фалкерсона [57].

11*