Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
12 билет
1)Транспортные сети. Разрезы транспортных сетей.
Определение.
В теории графов транспортная сеть — ориентированный граф , в котором каждое ребро имеет неотрицательную пропускную способность и поток . Выделяются две вершины: источник и сток такие, что любая другая вершина сети лежит на пути из в . Транспортная сеть может быть использована для моделирования, например, дорожного трафика.
Целочисленная транспортная сеть — транспортная сеть, все пропускные способности ребер которой — целые числа.
Разрез (s-t cut) — разбиение множества всех вершин V на два подмножества, A и B, таких что , .
Пропускная способность разреза (A,B) (the capacity of an s-t cut (A,B) ) — сумма пропускных способностей всех рёбер из A в B .
Поток через разрез (A,B) — сумма всех потоков из A в B . Он не превышает пропускную способность разреза, поскольку .
Минимальный разрез - разрез с минимальной пропускной способностью.
Свойства.
1)Поток через любой разрез равен сумме потоков из источника.
2)Сумма потоков из источника равна сумме потоков в сток.
3)Максимальный поток положителен тогда и только тогда, когда существует путь из источника в сток, проходящий по рёбрам с положительной пропускной способностью.
4)Поток максимален тогда и только тогда, когда нет увеличивающего пути в остаточной сети.
5)Теорема Форда-Фалкерсона. Величина максимального потока равна пропускной способности минимального разреза.
Пример.
Здесь изображена транспортная сеть с источником , стоком и четырьмя дополнительными узлами. Поток и пропускная способность обозначены соответственно . Поток из источника к стоку равен 5, что легко видно, так как поток из равен 5, что есть также в .
Остаточная сеть для показанного сверху потока, показывающая остаточные пропускные способности.
Ниже показана остаточная сеть для данного выше потока. Обратите внимание, что существует ограничивающая пропускная способность для некоторых ребер, тогда как в исходной сети она равна нулю. Например, ребро . Этот поток не максимален. Есть увеличивающие пути , и . Остаточная пропускная способность первого пути
Применение.
Самый частый пример использования транспортных сетей — нахождение максимального потока, который означает максимальный суммарный поток от к Для нахождения максимального потока в сети может быть использован алгоритм Форда — Фалкерсона, алгоритм Эдмондса — Карпа и другие.
2) Найти максимальный поток и значения потоков в ребрах сети для заданного орграфа.
Рассмотрим ребро (i, j) с (начальной) пропускной способностью (Cij,Cji). В процессе выполнения алгоритма части этих пропускных способностей "забираются" потоками, проходящими через данное ребро, в результате каждое ребро будет иметь остаточную пропускную способность. Будем использовать запись (cij, cji) для представления остаточных пропускных способностей. Сеть, где все ребра имеют остаточную пропускную способность, назовем остаточной.
Для произвольного узла j, получающего поток от узла i, определим метку [aj, i], где aj - величина потока, протекающего от узла j к узлу i. Алгоритм нахождения максимального потока предполагает выполнение следующих действий.
Шаг 1. Для всех ребер (i, j) положим остаточную пропускную способность равной первоначальной пропускной способности, т.е. приравняем (cij, cji) = (Cij, Cji). Назначим a1 = бесконечностии пометим узел 1 меткой [бесконечность, -]. Полагаем i = 1 и переходим ко второму шагу.
Шаг 2. Определяем множество Si как множество узлов j, в которые можно перейти из узла i по ребру с положительной остаточной пропускной способностью (т.е. cij > 0 для всех j, принадлежащих Si). Если Si не пустое множество, выполняем третий шаг, в противном случае переходим к шагу 4.
Шаг 3. В множестве Si находим узел k, такой, что cik = max {cij} для всех j, принадлежащих Si. Положим ak = cik и пометим узел k меткой [ak, i]. Если последней меткой помечен узел стока (т.е. если k = n), сквозной путь найден, и мы переходим к пятому шагу.
Шаг 4 (Откат назад). Если i = 1, сквозной путь невозможен, и мы переходим к шагу 6. Если i не равно 1, находим помеченный узел r, непосредственно предшествующий узлу i, и удаляем узелi из множества узлов, смежных с узлом r. Полагаем i = r и возвращаемся ко второму шагу.
Шаг 5 (Определение остаточной сети). Обозначим через Np = {1, k1, k2, …, n} множество узлов, через которые проходит p-й найденный сквозной путь от узла источника (узел 1) до узла стока (узел n). Тогда максимальный поток, проходящий по этому пути, вычисляется как fp = min {a1, ak1, ak2, ..., an}.
Остальные пропускные способности ребер, составляющих сквозной путь, уменьшается на величину fp в направлении движения потока и увеличиваются на эту же величину в противоположном направлении. Таким образом, для ребра (i, j), входящего в сквозной путь, текущие остаточные стоимости (cij, cji) изменятся следующим образом:
Далее восстанавливаем все узлы, удаленные на шаге 4. полагаем i = 1 и возвращаемся ко второму шагу для поиска нового сквозного пути.
Шаг 5 (Решение).
Процесс отката назад на четвертом шаге выполняется тогда, когда алгоритм должен "убить" промежуточный узел до момента реализации сквозного пути. Коррекцию пропускных способностей, выполняемых на шаге 5, можно пояснить на примере простой сети, показанной на рис. 1. На рис. 1а найден первый сквозной путь N1 = {1, 2, 3, 4} с максимальным потоком f1 = 5. После этого остаточные пропускные способности ребер (1, 2), (2, 3) и (3, 4) изменятся соответственно с (5, 0) на (0, 5). На рис. 1б показан второй сквозной путь N2 = {1, 3, 2, 4} с максимальным потоком f2 = 5. После коррекции пропускных способностей получаем сеть, показанную на рис. 1в, где уже невозможно построить сквозной путь. Почему так получилось? При вычислении остаточных пропускных способностей на шаге 5 при переходе от сети (б) к сети (в) невозможна организация потока в направлении 2 -> 3. Получается, что алгоритм как бы "помнит", что поток в направлении 2 -> 3 уже был в предыдущих сквозных путях, и поэтому снова (на пятом шаге) изменяет пропускную способность с 0 до 5 в направлении от узла 3 к узлу 2.
Рис.1. Иллюстрация сквозных путей
3) Определить для двудольного графа максимальное паросочетание
Пусть дан неориентированный граф G = (V, Е). Паросочетанием (matching) называется подмножество ребер М є Е, такое что для всех вершин v е V в М содержится не более одного ребра, инцидентного v.
Максимальным паросочетанием называется паросочетание максимальной мощности, т.е. такое паросочетание М, что для любого паросочетания М': |М| >= |М'|.
Ограничимся рассмотрением задачи поиска максимальных паросочетаний в двудольных графах. Мы предполагаем, что множество вершин можно разбить на два подмножества V = L U R, где L и R не пересекаются, и все ребра из Е проходят между L и R. Далее мы предполагаем, что каждая вершина из V имеет по крайней мере одно инцидентное ребро.
С помощью метода Форда-Фалкерсона можно найти максимальное паросочетание в неориентированном двудольном графе G = (V,E) за время, полиномиально зависящее от |V| и |Е|. Определим для заданного двудольного графа G соответствующую транспортную сеть G' = (V', Е') следующим образом. Возьмем в качестве источника s и стока t новые вершины, не входящие в V, и пусть V' = V U {s, t}. Если разбиение вершин в графе G задано как V = L U R, ориентированными ребрами G будут ребра Е, направленные из L в R, а также |V| новых ребер. Чтобы завершить построение, присвоим каждому ребру Е' единичную пропускную способность.
Ниже показан двудольный граф и соответствующая ему транспортная сеть. Выделенные ребра обеспечивают максимальный поток и определяют максимальное паросочетание