Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 26
Текст из файла (страница 26)
Рассмотрим теперь несколько хорошо известных результатов из комбинаторики, которые могут быть сформулированы в терминах максимального потока и минимального разреза. Подробности можно найти в [67]. Граф называется деудольным "), если его узлы моткпо разбить на два непересекающихся множества Я и Т ф = [Я; ), 1 = 1, 2,... ..., т, и Т = [Тт), ! = 1, 2,..., и), так, что капгдая дуга графа соединяет некоторый узел из Я с узлом из Т. ') В книге [67[ такие графы называются двусторовпимп.— Прил. нерее.
8.3. пгиложвния 155 Множество узлов называется (Я, Т)-рассекающим множеством, если удаление из графа этих узлов вместе с инцидептпыми им дугами разрывает все цепи из Я в Т. Твогвма 8.4 (теорема Кенига — Эгервари). Пусть С вЂ” двудольный граф. Максимальное число дуг графа С, попарно не имеющих общих узлов, равно минимальному числу узлов в (Я, Т)-рассекающем множестве узлов. Твонвма 8.5 (теорема Ментора). Пусть Я и Т вЂ” два непересекающихся подмножества узлов графа. Максимальное число цепей из Я в Т, попарно не имеющих общих узлов, равно минимальному' числу узлов в (Я, Т)-рассекающем множестве узлов.
Граф называется ориентированным, если оп содер'кит только ориентированные дуги. Граф называется ациклическим, если он не содержит циклов. Пусть С вЂ” ациклический ориентированный граф. Разложение графа С на цепи есть такое разбиение множества узлов и дуг графа 6 на цепи, что каждый узел из ь" принадлежит одной и только одной цепи (или говорят, что множество цепей покрывает граф). Разложение с минимальным числом цепей назовем минимальным.
Будем говорить, что Хэ больше, чем Х;, если имеется цепь, ведущая из Л~ в Лг (это отношение порядка будем обозначать следующим образом: 1У~ > 1Уз). Два узла ациклического графа называются несравнимыми, если пе выполняется ни Ф; ) .--Я,, ни 1У, ~Л~,. Твогвма 8.6 (теорема Дилворта). Максимальное число взаимно несравнимых узлов в ациклическом ориентированном графе равно числу цепей в минимальном разложении графа. Пусть 1У = (У„1Уг,..., Х„) — заданное множество элементов; Я = (Я„Яг,..., Я,„) — некоторое семейство подмножеств данного множества 1ч'. Набор Л различных элементов множества 1У П=(Руз )Уэг, . 'Уэ ) называется системой различных представителей семейства Я, если 1Ун ~ Я„1 = 1,..., т. Например, пусть У = (1, 2, 3, 4, 5), Я, = (2, 4, 5), Яг = =(1, 5), Я,=(3, 4),Я,=(3, 4).
Тогда В=(5, 1, 3, 4) есть система различных представителей для Я = (Яы Яг, Я г, Яь). Твогвма 8.7 (теорема Холла). Система различных представителей для семейства Я существует в том и только том случае, если объединение любых й множеств из Я содержит по крайней мере )с различных элементов, й = 1, 2,..., т. 1'Л. 8. МАКСИМАЛЬИЫН ПОТОК 156 8 й!. Линейное программирование и потоки в сетях Введем сначала несколько элементарных понятий теории графов.
Деревом называется неориентироваппый связный граф, не содержащий циклов. Следовательно, между л!обымп двумя узлами дерева имеется единственная цепь, их соедипялощая. Граф Н, содержащий и узлов, является деревом, если въполпя!отса любые два нз следу!ощих трех условий: 1) граф Н связный, 2) граф Н не имеет циклов, 3) число дуг в Н равно и — 1. Г1одграф Н графа С называется связывающим деревом '), если Н является деревом и каждый узел из С принадлежит Н.
Если граф С содержит и узлов, то всякий подграф графа С, являющийся деревом и содержащий и узлов, будет являться связываюп1ил! деревом. Если каждой дуге графа илн сети поставить в соответствие некоторое число 81; (длину дуги), то молкно ввести понятие минимального (или максимального) связывающего дерева. Минимальным (или макеималюмм) св зывающии деревом графа (сети) называется такое связывающее дерево, у которого сумма длин дл; всех дуг минимальна (или максимальна) среди всех связывающих деревьев этого графа (сети).
Вернемся к задаче о максимальном потоке. В 3 8.1 при ее изучении пе использовались понятия линейного программирования. Но в действительности задачи о потоке в сети представляют собой специальный класс задач линейного программирования, и каждая потоковая задача может быть сформулирована как задача линейного программирования. Многие алгоритмы решения потоковых задач основаны на принципах двойственности липейного программирования.
Рассмотрим, например, сеть, изображенную на рис. 8.1. Дуговые потоки в сети будем рассматривать в качестве 6 переменных: Х„„Х„,..., Хве ХОТЯ П ВЫРалнаетСЯ ЧЕРЕЗ ХЫ, (и = Х.З + Х. З) будем считать и седьлюй переменной. Задачу о максимальном потоке можно сформулировать как задачу линейного програлыирования следующих! образом: максимизировать а= ох при условиях А'х = О, А"х(Ь, х)0, 1) В литературе связывающее дерево часто называют деревом-остовом.— Прим. перев. зл, ли~Бинов пгогглммнеовлник н пОтОки В остях где х= [а, хзз хзз, азз хзю хм хзз) с = (1, О, О, О, О, О, 0), — 1 1 1 0 0 0 0 0 — 1 0 1 — 1 1 0 0 0 — 1 — 1 1 0 1 1 0 0 0 0 — 1 — 1 А'= 100000 010000 0 0 0 1 0 0 0 0 0 О 0 1 0 0 О О О О О 1 0 0 0 0 0 0 0 1 ') В литературе такие матрицы также называют вполне упнмедулярззымп.— Прим. ред.
[Матрица А' имеет размер и и (т — ', 1), А" — размер т х (т. 81), . )з=[Ьмь Ьзз, Ьзз Ьзз Ьм. Ьз~[; здесь и — число узлов, т — число дуг в сети.) Структура матрицы А' представляет особый интерес. Каждый ее столбец содер кит два ненулевых элемента, а именно +1 и — 1. Ьлагодаря такой структуре матрица А', состоящая из и строк, имеет ранг и — 1. Это можно пояснить следующим образом. Каждая строка матрицы А' соответствует условию сохранения потока в некотором узле сети.
Если сложить все уравнения (1) нз $ 8.1, то получится нулевой вектор. Значит, условие сохранения потока в одном нз узлов являотся следствием условий сохранения потока в остальных и — 1 узлах. Таким образом, не нарушая общности, можно отбросить одну из строк матрицы А'. Остальные строки, как легко видеть, линейно независимы. Рассмотрим матрицу А, образованную из строк матриц А' ГИ' ц и А": А = ~ „~. Опа.обладает одним свойством, пе столь очевид- [А-!.
ным. Лзобои минор матрицы А равен либо О, либо +-1. Такие матрицы называются абселютине унимодулярными '). Именно свойство абсолютной упимодулярностн матрицы А гарантирует, что оптимальное решение задачи линейного программирования с ограничениями (1) будет целочисленным, если все номпонепты вектора )з — целые числа.
В задачах линейного программирования переменные, связанные с пекоторымп столбцамй матрицы ограничений, называются ГЛ. В. МАКСИМАЛЬНЫЙ ПОТОК небазисными, или независимыми переменными, так как опи могут принимать произвольные значения. Тогда значения базисных переменных определяются однозначно по значениям небазисных переменных.
Рассмотрим сеть без ограничений на пропускные способности дуг. Если дуговым потокам в ней присвоить произвольные значения, то условия сохранения в некоторых узлах могут не выполняться. Следовательно, дуговой поток по одной из дуг, инцидентных некоторому узлу, не может быть произзольпыы, а определяется из условия сохранения потока в атом узле. Если выделить. все такие дуги, потоки по которым определяются однозначно через потоки по остальным дугам, то оки образуют связывающее. дерево.
Чтобы убедиться в этом, будем рассуждать следующим образом. Среди всех потоков по дугам, инцидептпых некоторому узлу, один из дуговых потоков должен определяться через остальные дугоные потоки, иначе нарушится условие сохранения потока в атом узле. Поскольку имеется п — 1 независимых условий сохрапения потока, значит, всего существует п — 1 таких дуг. Эти п — 1 дуг пе могут образовывать никакие циклы, так как потоки в цикле можно, например, увеличить, пе ивменяя других потоков и не нарушая условий сохранения в узлах цикла, а зто будет противоречить тому, что потоки в выбранных п — 1 дугах определены однозначно черзз остальные дуговые потоки, оставшиеся теми же.
Следовательно, выбранные п — 1 дуг образуют связывающее дерево. Легко убедиться, что верно и обратное утверждение: в сети без ограничений на дуговые пропускные способности дуговые потоки в любом связывающем дереве являются базисными переменными '). Рассмотрим сеть без ограпичепий на пропускные способности дуг, т. е. потребуем, чтобы в (1) выполнялись только условия А'х = О и х ) О.
Пусть каждой дуге поставлено в соответствие. число, которое является стоимостью перевозки единицы товара. по атой дуге. Если нужно перевезти заданное количество товара из источника в сток с минимальными затратами, то ясно, что весь поток надо пропустить по одной цепи, а именно по цепи минимальной стоимости. Так как цепь из источника в сток содержит обычно меньше чем п — 1 дуг, то число ненулевых базисных переменных будет меньше чем и — 1.
Это значит, что задачи имеет оптимальное базисное решение, которое вырождено. В сети с ограничениями на пропускные способности дуг неравенства А"х ~ й в (1) следует превратить в уравнения. Это приведет к появлению т слабых переменных г„лз,..., г,„, где т— число дуг в сети.
Тогда мы будем иметь п — 1 + т независимых з) Не следует забывать, что одной нз переменных (компонент вентора м) нвлнется и.— Прим. ред, 8.5. СВОЙСТВО АБСОЛЮТНОЙ УНИМОДУЛЯРНОСТИ 159 уравнений Ах = Ъ, где х = (с, х„хз,..., х, 8„88, ..., г ), А — матрица размера (н+т) Х (2т + 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
