Аугментальная цепь
Cтраница 1
Аугментальная цепь в графе G является теперь цепью Р, где дуги из Р в А. А являются обратными дугами. [1]
Допустим, что существует аугментальная цепь Р, и пусть Р обозначает также множество ребер этой цепи. [2]
Допустим, что существует аугментальная цепь Р, и пусть Р обозначает также множество ребер этой цепи. Но так как оба концевых ребра из Р не лежат в М, то Р - Р П М содержит на одно ребро больше, чем Р П М, и поэтому М М 1, так что М не является наибольшим паросочетанием. [3]
Улучшить текущее паросочетание, поменяв вдоль аугментальной цепи ребра, принадлежащие паросочетанию и ему не принадлежащие. [4]
Улучшить текущее паросочетание, взаимно поменяв ( вдоль аугментальной цепи) ребра, принадлежащие ему и ему не принадлежащие. [5]
Пусть М - Паросочетание, относительно которого нет ни одной аугментальной цепи в графе G, и пусть М - наибольшее Паросочетание. Построим остовный подграф Gp, образованный ребрами из М U М - МП М вместе с соответствующими им вершинами. [6]
Пусть М - паросочетание, относительно которого нет ни одной аугментальной цепи в графе С, и пусть М - наибольшее паросочетание. [7]
Так как столбец 8 не имеет отмеченных нулей, то найдена аугментальная цепь, показанная стрелками в вышеприведенной матрице. Меняя отмеченные и неотмеченные нули вдоль этой цепи, получаем новое, улучшенное, паросочетание. [8]
В обоих случаях б задает максимальную величину дополнительного потока, который может протекать от s к xt вдоль построенной аугментальной цепи потока. Сначала все вершины не имеют пометок. [9]
В обоих случаях б задает максимальную величину дополнительного потока, который может протекать от х к х1 вдоль построенной аугментальной цепи потока. Присвоение пометки вершине х, соответствует нахождению аугментальной цепи потока от 5 к Я. Сначала все вершины не имеют пометок. [10]
Алгоритм начинает работу с произвольного допустимого потока ( можно взять и нулевой поток), затем стремятся увеличить величину потока с помощью систематического поиска всех возможных аугментальных цепей потока от 5 к I. Поиск аугменталь-ной цепи осуществляется с помощью расстановки пометок в вершинах графа. Пометки указывают, вдоль каких дуг может быть увеличен поток и на сколько. Как только найдена одна из таких цепей, поток вдоль нее увеличивают до максимального значения, все пометки в вершинах стираются и вновь полученный поток используется в качестве исходного при новой расстановке пометок. Алгоритм заканчивает работу и дает максимальный поток, если нельзя найти ни одну аугментальную цепь. Алгоритм применяется следующим образом. [11]
I получила пометку, то в графе № () найдена цепь Р от я к I. Аугментальная цепь в графе О является теперь цепью Р, где дуги из Р в Л 1 являются прямыми дугами, а дуги из Р в 4 являются обратными дугами. [12]
Хн, являющиеся концевыми для ребер из AHGO, будут экспонированными. Но аугментальная цепь должна содержать нечетное число ребер, а это означает, что если первое ребро этой цепи идет из экспонированной вершины во внутреннюю, то последнее ребро должно идти из внешней вершины в экспонированную. [13]
В обоих случаях б задает максимальную величину дополнительного потока, который может протекать от х к х1 вдоль построенной аугментальной цепи потока. Присвоение пометки вершине х, соответствует нахождению аугментальной цепи потока от 5 к Я. Сначала все вершины не имеют пометок. [14]
 |
Оптимальный поток. - насыщенные дуги. [15] |
Страницы: 1 2