29. Сети и потоки в сетях. Задача о максимальном потоке и алгоритм Форда–Фалкерсона.

Пусть - некоторый орграф и f: B→R – вещ-но-значная f-я на мн-ве ребер, тогда пара наз-ся сетью, а f-я f наз-ся f-цией пропускной способ-ти сети. Если f-я g: B→R удовлетворяет нерав-ву: gf, то g наз-ся потоком в сети. Пусть L: B→R – любая f-я и U, VА, символ h(U,V) будет обозначать сумму знач-й f-и h на ребрах (х,у)В, таких что хU, yV. Если U состоит из одной вершины a, то h(a,V) обозначает сумму весов ребер, начин-щихся в U и заканч-щихся в вершинах из V, аналогично h(U,a) – сумма знач-й f-и h на ребрах, начин.в U и заканч.в вершине а. Поток g: B→R в сети ,f наз-ся стационарным, если 2вершины U, VA и число WR такие, что выполн-ся след.усл-я: 1)g(U,A)-g(A,U)=W. 2)g(V,A)-g(A,V)=-W. 3)g(x,A)-g(A,x)=0 (д/любых хА, но U и V. Известна след.классич.задача о max потоке: в дан.сети д/дан.источника и д/дан.стока найти стац.поток max-возможной величины. Можно док-ть, что дан.задача всегда имеет реш-е. Д/реш-я этой задачи сущ-ет много различ.алг-мов, одним из ктр явл-ся алг-м Форда-Фалкерсона. Постановка задачи: Д/опр-я max потока от некоторой вершины S графа (источника) к нектр вершине t графа (сток) использ-ся много различ.алг-мов. При этом кажд.дуге (орграф) (i,j) приписана нектр пропуск.способ-ть с(i,j), опр-щая max знач-е потока, ктр может протекать по дан.дуге. Алг-м Ф-Ф основан на «технике меток». Введем опр-я: разрезом наз-ся мн-во дуг, удаление ктр из сети приводит к разрыву всех путей, ведущих из S в t. Пропуск.способ-ть разреза – Сум.пропуск.способ-ть дуг его составляющих. Разрез с min пропуск.способ-тью наз-ся min разрезом. Т.Ф-Ф: величина кажд.потока из S в t не превосходит пропуск.способ-ти min разреза, разделяющего S и t, причем сущ-ет поток, достигающий этого знач-я. Если поток min, то по Т.Ф-Ф max поток не будет превышать 4ед-цы. Найти max поток, т.е. его распред-е по дугам, можно опр-ть методом перебора. Удачный выбор данных позволяет сделать программ.код компактным, но очевидно, что этот метод прим-м только д/небольших сетей. Техника меток Ф-Ф заключ-ся в послед-ном (итерацион.) построении max потока путем поиска на кажд.шаге увелич-щейся цепи, т.е. пути послед-ти д/потоков, по ктр можно увеличить. При этом узлы (вершины графа) спец.образом помеч-ся.

20. Определение паросочетаний в графе и их разновидностей. Двудольные графы и алгоритм выбора наибольшего паросочетания в двудольном графе.

Пусть Г = [А,В] – граф и S  D – некот-е множ-во ребер в нем. Множество S назыв-ся паросочетанием, если любые два ребра из него не имеют общей вершины. Множ-во из одного ребра тоже будет назыв-ся паросочетанием, как и всякое пустое множ-во. Паросочетание называется максимальным, если к нему нельзя добавить ни одного ребра так, чтобы снова получ-сь паросочет-е. Паросочетание назыв-ся наибольшим, если оно состоит из наиб-го возможного колич-ва ребер. Очевидно, каждое наибольшее паросочетание явл. максимальным; обратное неверно.

Пример:

здесь красные ребра – максим-е, но не наибол-е паросочетание, а черные ребра – наибольшее паросочетание. Графы можно представлять матрицами. Матричные представления графов использ-ся при решении прикладных задач, особенно в тех случаях, когда при моделировании предметной области применяются алгебраические доказательства. Поиск наибольшего паросочетания в графе представляет собой классическую алгоритмическую задачу. Далее будет рассматриваться пример решения такой задачи для графов частного вида – графов двудольных. Граф Г = [А,В] называется двудольным, если его множество вершин А можно представить в виде объединения двух его непустых подмножеств А₁, А₂ без общих элементов так, что любое ребро из В будет иметь один конец в А₁, а другой конец – в А₂. таким образом, нет ни одного ребра, которое соединяло бы вершины из А₁ или соединяло бы вершины из А₂. Если считать, что А₁ = {x₁,…,x_r}, А₂ = {y₁,…,y_r}, то двудольный граф можно описать не только матрицей смежностей, но и матрицей двудольного графа: эта матрица – размером rs и если обозначать ее общий элемент через m_ij. Ясно, что такая матрица описывает граф однозначно, хотя является намного меньше по объему, чем матрица смежностей графа в этом случае. Когда множество А₁ состоит из n вершин, а множество А₂ состоит из m вершин и в двудольном графе проведены все возможные ребра, то говорят, что двудольный граф Г = [А,В] является полным двудольным графом и обозначают его символом K_m,n. Далее описан алгоритм выбора наибольшего паросочетания в двудольном графе, опираясь на только что введенное понятие матрицы двудольного графа. Шаг 0. По матрице М = (m_ij), i = 1,…, p, j = 1, 2,…, p данного двудольного графа строим рабочую таблицу: она представляет собой матрицу тех же размеров, в клетку с номером (ij) поместим символ «» и назовем ее недопустимой, если в матрице двудольного графа m_ij = 0; если же m_ij = 1, то в клетку рабочей таблицы не запишем ничего и назовем такую клетку допустимой. Слева от рабочей таблицы расположим для удобства номера ее строк, а сверху над таблицей расположим номера ее столбцов. Шаг 1. Просмотрим слева направо первую строку и в первую же допустимую клетку первой строки поставим символ «1». Если в первой строке все клетки недопустимы, то перейдем ко второй строке и в первую же (при просмотре слева направо) допустимую клетку поставим «1». Если же нет допустимых клеток и во второй строке, то проставим указанным выше способом «1» в третьей строке. Если окажется, что во всей табл-е все клетки недоп-мы, то на этом все действия заканчиваются и выдается ответ: «в графе нет ребер». Если же все-таки удастся поставить первую «1», то после этого просмотрим все остал-е строки таблицы в порядке возрастания их номеров. В каждой очередной строке просматриваем ее клетки слева направо и фиксируем первую по ходу просмотра допустимую клетку такую, кот-я является незав-й по отношению к допустимым клеткам, в которых уже стоит символ «1», и проставляем в эту клетку «1», после чего переходим у тем же действиям в следующей строке. Если в строке такой клетки не окажется, то переходим к следующей строке и выполняем в ней ту же проверку. Фиксируем набор ребер в графе, соответствующих проставл-м в таблице символам «1». (Под ребром, соответствующим символу «1»в рабочей таблице, подразумевается следующее: если «1» стоит в клетке с номером (ij), то соответствующим будет ребро (x_i, y_j)). Легко заметить, что этот набор ребер – максим-е парос-е. Если в рез-те проведения всех действий по этому шагу в каждой строке рабочей таблицы окажется символ «1», то ребра из указанного только что паросочетания и составляют наибол-е паросочетание, и действия окончены. Если же в резул-те проведения первого шага остались строки без «1», то пометим их справа от таблицы символом «-». Переходим к следующему шагу. Шаг 2. Просмотрим все помеченные строки в порядке возрастания их номеров. Просмотр очередной строки состоит в следующем: в строке отыскивают допустимые клетки, и столбцы, в которых эти клетки расположены, помечаются номером просматр-й строки. При этом соблюдается принцип (): если пометка уже стоит, то на ее место вторая не ставится. Пометки, о которых только что было сказано, физически выставляются внизу, под таблицей. Если в резул-те этого шага ни один из столбцов не будет помечен, то это означает, что уже имеющ-ся паросоч-е (полеченное на Шаге 1) явл-ся искомым большим и все действия прекращ-ся. Если же среди столбцов появятся помеченные, то переходим к следующему шагу. Шаг 3. Просмотрим помеченные столбцы в порядке возрастания их номеров. Просмотр столбца состоит в следующем: в столбце отыскив-ся символ «1» и строка, в кот-й он расп-н,. Помечается номером просматр-го столбца. Физически пометки выставляются справа от таблицы, на уровне соответствующих строк. Всегда соблюдается принцип (). Если в резул-те действий по этому шагу возникнет ситуация, когда в просматриваемом столбце нет символа «1», то действия на данном шагу прерываются и надо перейти к следующему шагу – Шагу 4. если же в результате действий по этому шагу будут просмотрены все помеченные ранее столбцы и, тем самым, возникнет набор помеченных строк (они будут помечены символом «-», другие – номерами столбцов), то следует вернуться к Шагу 2 и повторить предусмотренные им действия. Если в результате этих действий по Шагу 2 не возникнет новых помеченных столбцов, то это означает, что имеющееся паросочетание является искомым и процесс останавл-ся. Если же среди помечаемых столб-в возникнут новые помеч-е столбцы, то следует повторить Шаг 3 с новым набором помеченных столбцов. Если в результате этих действий не возникнет новых помеч-х строк, то это означает,. Что имеющ-ся паросочетание явл-ся искомым. Шаг 4. Рассматр-ся столбец, имеющий пометку и не содержащий символа «1». Мы сейчас изменим набор символов «1», располож-х в рабочей таблице. В рассматр-й столбец поставим символ «1» в строку, номер кот-й равен пометке этого столбца. Затем в этой строке отыщем «старый» символ «2» и переместим его по его столбцу в строку, номер которой равен пометке при этом столбце (описанное действие всегда осуществимо). Затем в строке, куда попал последний символ «1» отыщем «старый» символ «1» и с ним проделаем то же самое. В итоге очередной перемещаемый «старый» символ «1» окажется в строке, где больше символов «1» нет. Возник новый набор символов «1», в котором уже элементов на один больше, чем в исходном наборе символов «1». По этому новому набору можно построить паросочетание так же, как это делалось в самом начале и после этого повторить все сначала. В итоге возникает из указанных выше условий прекращения действий по алгоритму и наибольшее паросочетание будет найдено.

22. Методы хранения графов в памяти ЭВМ. Взвешенный граф. Кратчайшие пути во взвешенном графе и алгоритм Форда построения кратчайших маршрутов.

В ЭВМ удобно представлять графы в виде матриц смежнотей: если направление ребра противоположено, то в матрицу составим (-1). Графом называется пара множеств Г=[А,В], где А – любое непустое множество, а В – множество, которое является подмножеством множества V(A). Элементы из А называются вершинами графа, а элементы из В – его ребрами. Например, А={1,2,3,4,5}, В={(1,2),(2,3),(3,4),(1,5),(1,4),(3,1)}. Неупорядоченная пара вершин – ребро, а упорядоченная пара – дуга. дугам графа приписываются числа, называемые весом, стоимостью, или длиной этой дуги. В этом случае граф называется графом со взвешенными дугами. А если вес приписывается вершинам графа, то тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам и вершинам, то он называется просто взвешенным. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины s принад-т x до заданной конечной вершины, при условии, что такой путь существует t принад-т R(s (здесь R(s)-множество, достижимое из вершины s.) и все циклы в графе имеют неотрицательный суммарный вес. Так как если в графе будет присутствовать цикл с отрицательным суммарным весом и хi- некоторая его вершина, то, двигаясь от s к х_i, обходя этот цикл достаточно большое число раз и попадая, наконец в t, получится путь со сколь угодно малым ( ) весом. Таким образом, в этом случае кратчайшего пути не существует. Так что неориентированные дуги (ребра) графа G не могут иметь отрицательные веса. Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается. Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до академии), также используется в системах автопилота, используется для нахождения оптимального маршрута при перевозках коммутации информационного пакета Internet и многого другого. Кратчайший путь рассматривается при помощи математического объекта – графа. Граф задается множеством точек (вершин) и множеством линий (ребер), соединяющих все или часть этих точек. Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути: 1) алгоритм Дейкстры. Используется для нахождения оптимального маршрута между двумя вершинами. 2) алгоритм Флойда. Используется для нахождения оптимального маршрута между всеми парами вершин. 3) алгоритм Форда. Используется для нахождения оптимального маршрута между двумя вершинами. Для заданной начальной вершины s необходимо найти кратчайшие пути между s и всеми другими вершинами х_i X. Необходимо найти кратчайшие пути между всеми парами вершин. Самый распространенный пример подобных задач, это нахождение кратчайшего расстояния между двумя вершинами. В этом случае, весом дуги (х_i, х_j) будет являться расстояние между вершинами хi и хj, ну, а если такая дуга отсутствует, то ее вес полагается равным бесконечности. Существует классический алгоритм Форда поиска кратчайших путей в графе. Основан он на следующем простом факте: если имеется кратчайший путь между какими-либо двумя вершинами, то его часть между любыми двумя вершинами на нем же самом также является кратчайшем путем. Алгоритм Форда позволяет найти кратчайшие пути из какой-либо одной вершины графа во все остальные. Эту исходную вершину можно выбрать произвольно, но, сделав выбор, далее уже исходить из того, что будут описаны кратчайшие пути именно из этой вершины во все остальные. Шаг0. Занумеруем все вершины из Г=[А, В], так что А={1,2,…,p} и при этом номер «1» имеет именно та вершина, из которой будут найдены кратчайшие пути во все остальные вершины. Рассмотрим матрицу М=(m_ij), i, j=1,2, …,p, положив

Шаг1. Около первой строки матрицы М, слева от матрицы, поставим числовую пометку «0» и такую же пометку проставим над первым столбцом матрицы. Затем проставим помеченную строку слева направо и всякий раз, встречая клетку с числом, прибавим это число к пометке строки и суму проставим над столбцом, в котором эта клетка находится. Отразим пометки столбцов относительно главной диагонали. С каждой из помеченных строк проделаем тоже самое: просмотрим помеченную строку слева направо и всякий раз, встречая клетку с числом, прибавим это число к пометке строки и сумму поставим в качестве пометки над столбцом, в котором эта клетка стоит. При этом будем соблюдать принцип: «имеющуюся пометку не менять». Пометки столбцов отразим относительно главной диагонали и с помеченными строками вновь проделаем то же самое. И так далее, пока не окажутся помеченными все строки и все столбцы. Шаг2. Просмотрим строки таблицы в порядке возрастания их номеров. В каждой строке просматриваются клетки слева направо и всякий раз, когда встречается число, оно складывается с пометкой столбца, в котором найденное число расположено. Если сумма оказалась меньше, чем пометка столбца, то эта пометка столбца заменяется на упомянутую сумму. Если же сумма оказалась больше или равной пометке, то ничего не меняется. После такого просмотра всех строк новые пометки столбцов отражаются относительно главной диагонали и вся процедура повторяется. И так до тех пор пока не прекратятся какие то бы ни было изменения в пометках. Шаг3. Теперь по пометкам можно построить кратчайшие пути из первой вершины во все остальные. Фиксируем произвольную вершину k (k=2,3, …,p) и опишем кратчайший путь из первой вершины в вершину k. Во-первых длина этого кратчайшего пути равна пометке , стоящей над столбцом номер k. Во –вторых предпоследняя вершина в кратчайшем пути из первой вершины в вершину k находится так: в столбце номер k отыскиваем число, сумма которого с пометкой строки, в которой оно расположено, равна . Пусть номер строки, в которой найденное число оказалось, равен l, тогда предпоследней вершиной в кратчайшем пути из 1 в k будет вершина l, надо отыскивать как предпоследнюю в кратчайшем пути из 1 в l и так далее.