30501

Сеть. Поток в сети. Задача о максимальном потоке в сети. Алгоритм нахождения максимального потока

Доклад

Математика и математический анализ

Тогда очевидно что между вершинами t и s существует цепь состоящая из направленных ребер – прямых и обратных дуг соединяющая эти вершины Выступление: Сетью называется связный граф в котором заданы “пропускные способности†ребер т. Это числа большие или равные нулю причем qij = 0 тогда и только тогда когда нет ребра соединяющего вершины i и j. количество условного “груза†перевозимого из вершины с номером i в вершину с номером j удовлетворяющих четырем условиям: 1 числа сij  0 причем если сij ...

Русский

2013-08-24

29.14 KB

21 чел.

  1.  Сеть. Поток в сети. Задача о максимальном потоке в сети. Алгоритм нахождения максимального потока.

Доска:

Сток (т. е. вершина с номером s) не входит в множество вершин Y. Тогда обозначим множество вершин, не входящих в через Z. Наш граф по условию является связным, поэтому из Y, в идут некоторые ребра. По правилам построения все эти ребра являются прямыми насыщенными дугами

Вершина также входит в Y, и пусть второе число ее пометки  > 0. Тогда, очевидно, что между вершинами и существует цепь (состоящая из направленных ребер – прямых и обратных дуг), соединяющая эти вершины

ts

Выступление:

Сетью называется связный граф, в котором заданы “пропускные способности” ребер, т. е. числа qij. Это числа большие или равные нулю, причем qij 0 тогда и только тогда, когда нет ребра, соединяющего вершины i и j. Таким образом, можно считать, что пропускные способности ребер заданы для любой пары вершин. В дискретной математике пропускные способности ребер, как и все возникающие константы, считаются целыми числами (или рациональными, что одно и то же, так как рациональные числа отличаются от целых только единицами измерения).

Потоком в сети между вершиной (источникоми (стокомназывается набор чисел сij, (т. е. количество условного “груза”, перевозимого из вершины с номером i в вершину с номером j), удовлетворяющих четырем условиям:

1) числа сij   0, причем если сij 0, то сji 0 (нет встречных перевозок);

2) числа cij   qij (соответствующих пропускных способностей ребер);

3) если вершина с номером i – промежуточная (не совпадает с источником и стоком), то

,

т. е. количество “груза”, вывозимого из вершины i, равно количеству “груза”, ввозимого в эту вершину;

4)  количество “груза”, вывозимого из источника t, должно быть равно количеству груза, ввозимого в сток s:

.

Число А называется величиной данного потока или просто потоком между и s.

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

Теорема Форда – Фалкерсона (1955). Максимальный поток между вершинами t и s равен величине минимального сечения между этими вершинами.

Дополнительно:

Теорема Форда – Фалкерсона (1955). Максимальный поток между вершинами t и s равен величине минимального сечения между этими вершинами.

Доказательство этой теоремы является конструктивным (т. е. показывает, как найти нужный максимальный поток), поэтому приводится ниже.

  1.  Докажем сначала, что любой поток между вершинами и s меньше или равен величине любого сечения. Пусть дан некоторый поток и некоторое сечение. Величина данного потока складывается из величин “грузов”, перевозимых по всем возможным путям из вершины в s. Каждый такой путь обязан иметь общее ребро с данным сечением. Так как по каждому ребру сечения суммарно нельзя перевести “груза” больше, чем его пропускная способность, поэтому сумма всех грузов меньше или равна, сумме всех пропускных способностей ребер данного сечения. Утверждение доказано.

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

  1.  Докажем теперь обратное неравенство. Пусть имеется некоторый поток cij (какой-то поток всегда существует, например, нулевой, когда все cij = 0). Будем помечать вершины графа, причем считаем, что все помеченные вершины образуют множество Y. Пометки вершин производятся от источника. Каждая пометка вершины (если эта вершина может быть помечена) состоит из двух чисел: первое – это “+” или “–” номер вершины (из Y), c которой связана новая помечаемая вершина, и второе – (обязательно должно быть положительным) – это фактически та добавка к потоку, которая может быть дополнительно “довезена” в эту вершину из источника по сравнению с исходным потоком.

Более точно, множество помеченных вершин образуется следующим образом:

источник принадлежит и его пометка (0, ); второе число, условно говоря, равно бесконечности – что для дискретной математики означает, что это настолько большое число, как нам понадобится;

если вершина принадлежит Y и cij < qij (дуга (i,j) – прямая и ненасыщенная), то вершина также принадлежит и пометка вершины равна (+i, j), где j>0 равно jmin {i, qij – cij}. Заметим, что здесь число i – это второе число уже помеченной вершины i, а знак + перед номером означает, что дуга, связывающая вершины (i, j) является прямой (и ненасыщенной);

если вершина к принадлежит и сjk > 0 (обратная дуга), то вершина с номером также должна принадлежать и ее пометка равна (– кj), где знак минус означает, что вершина jсвязана с уже помеченной вершиной к обратной дугой, jmin{k, qjk+cjk}, причем очевидно, что также строго больше нуля. Таким образом, построение множества являетсяиндуктивным, т. е. новая вершина добавляется в Y, если она связана с некоторой вершиной уже входящей в либо прямой ненасыщенной дугой, либо обратной дугой.

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

1. Сток (т. е. вершина с номером s) не входит в множество вершин Y. Тогда обозначим множество вершин, не входящих в через Z. Наш граф по условию является связным, поэтому из Y, в идут некоторые ребра. По правилам построения все эти ребра являются прямыми насыщенными дугами (рис. 7).

Ребра, идущие из множества в Z, образуют сечение между вершинами и s. Видно также, что сумма пропускных способностей ребер этого сечения (а все эти ребра являются прямыми, насыщенными) равна потоку из в s. Значит, данный поток является максимальным (так как он равен величине некоторого сечения), а данное сечение является минимальным.

2. Вершина также входит в Y, и пусть второе число ее пометки  > 0. Тогда, очевидно, что между вершинами и существует цепь (состоящая из направленных ребер – прямых и обратных дуг), соединяющая эти вершины

Схематично это представлено на рис. 8.

ts

Рис. 8

Заметим, что дуга, выходящая из источника, и дуга, входящая в сток, должны быть обязательно прямыми. Прибавим  к cij для прямых дуг этой цепи (по построению видно, что полученное число будет меньше или равно qij) и вычтем это  s из cij для обратных дуг (может получиться отрицательное число, но оно обязательно будет по абсолютной величине меньше qij, так как по построению  s   cij+qij , а это означает, что обратная дуга меняет направление, становится прямой дугой и его “нагрузка” будет равна модулю числа Тогда новые числа для дуг, входящих в нашу цепь, а также “старые” cij для всех дуг, не входящих в нашу цепь, образуют новый поток из вершины в вершину s(легко проверить простым рассуждением, что для новых чисел выполняются условия (1)–(4)). Кроме того, величина нового потока по сравнению со старым увеличилась на s > 0  . Для нового потока снова проведем ту же процедуру и т. д.

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

Рассуждение теоремы Форда – Фалкерсона фактически является алгоритмом нахождения максимального потока между двумя вершинами (или доказательством того, что этот поток является максимальным). Подробный пример на эту тему приведен в разд. 15 “Решение типовых задач”.

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

Рассмотрим еще некоторые вопросы (достаточно общего характера) из теории графов. Заметим, что в следующих разделах мы приводим только самые простые доказательства, а основные доказательства приведены в книге Р. Уилсона [6].


 

А также другие работы, которые могут Вас заинтересовать

53303. Національно-визвольна війна українського народу проти Речі Посполитої середини ХVІІ ст 64.5 KB
  Нагадую правила гри: за кожне порушення дисципліни викрики підказку журі має право зняти з команди від 2 до 5 балів. Кому розпочинати гру визначається за допомогою жеребкування Отже у нас все готове до початку КВК залишилось побажати тільки успіхів учасникам гри і оголосити склад журі. Оголошується склад журі Змагання сьогоднішнє я відкриваю 1 щиро усіх вас вітаю. Команда Ерудити Любить КВК наш дружний клас І оголосить засідання зараз Ось болільники а ось журі.
53304. Украинско-московский межгосударственный договор 1654 года. Продолжение Национально-освободительной войны 76.5 KB
  Цели: выяснить предпосылки и определить основные положения и значение украинско-московского договора 1654 года, а также дать историческую оценку событиям Национально-освободительной войны в 1654-1655 годах; развивать у учащихся жизненные умения и навыки: работать с историческими источниками и на основе их делать выводы и обобщения, давать оценку историческим событиям, высказывать свою точку зрения по отношению к ним...
53305. Україна в умовах десталінізації (1953 – 1964 рр.) 242.5 KB
  Назвіть події з історії України, які відбувалися після подій всесвітньої історії, визначених у першій колонці, але раніше, ніж події, визначені у третій колонці.
53306. НІКОПОЛЬЩИНА В РОКИ ДРУГОЇ СВІТОВОЇ ВІЙНИ 133 KB
  МЕТА: Проаналізувати події другої світової війни на Нікопольщині, удосконалювати навички самостійної роботи з додатковою літературою, картою, продовжити формувати вміння учнів, аналізувати, узагальнювати історичний матеріал, виховувати учнів у дусі патріотизму, гордості за бойові та ратні подвиги наших земляків.
53307. Порядок начисления и учета амортизации нематериальных активов 22.39 KB
  Амортизация – это процесс систематического, ежемесячного переноса стоимости на себестоимость продукции либо за счет собственных источников и накопление амортизационного фонда для замены изношенных экземпляров.
53308. Український національний рух на території Польщі (20-30-і рр. ХХ ст.) 85 KB
  Метод Припущення на основі запропонованих слів Учитель перераховує кілька слів із біографії Дмитра Донцова ідеолога право радикального руху. Учитель. Що далі Учитель. Учитель вислуховує пари із похвалою але не каже схожі вони чи ні на те що має бути почути.
53309. Україна в роки Другої світової війна (1939 -1945 рр.). Велика Вітчизняна війна (1941-1945 рр.) 131.5 KB
  Виховувати почуття гордості до історичного минулого України. Доповніть текст: Приєднання Західної України та Західної Білорусії до СРСР розпочалося після вступу Червоної армії на територію Польщі. Закон про включення Західної України до складу СРСР і возз’єднання її з Українською РСР було прийнято: а Верховними Радами СРСР та УРСР у листопаді 1939 р.; б Народними зборами Західної України у жовтні 1939 р.
53310. Московська держава 74.5 KB
  МЕТА: Ознайомити учнів із внутрішній та зовнішній політикою Івана IV. Вінчання Івана IV на царство. Судебник Івана IV. ТИП УРОКУ: комбінований СТРУКТУРА УРОКУ Організаційний момент Актуалізація Вивчення нового матеріалу ІванIV Грозний; Реформи царя Івана IV; Опричнина та її наслідки для розвитку Росії; Зовнішня політика Івана IV.
53311. Двомовне вивчення історії у 5 класі як засіб формування громадянської свідомості учнів 56.5 KB
  Методи та прийоми: інформаційно-повідомлюючий пояснювально-спонукальний частково пошуковий; бесіда колективна та самостійна робота з підручником атласом; практичне завдання в контурній карті; інтерактивні вправи дидактичні ігри. В низинах Дніпра за дніпровськими порогами пролягали безкрайні...