Аугментальная цепь

Cтраница 2

Циркуляция потока б ( где б - входной поток дуги ( хь, я4)) по этому маршруту, как показано на рис. 11.18, дает максимальный допустимый поток со значением 61 5, и для этого значения получающийся поток показан ( подчеркнутыми числами) на рис. 11.19 а, причем дуга ( хъ, хв) насыщена. Посылая поток б по циклу и передавая его по аугментальной цепи к t, как показано на рис. 11.19 а, получаем поток, изображенный на рис. 11.196 подчеркнутыми числами. [16]

Оптимальный поток. - насыщенные дуги. [17]

Циркуляция потока б ( где б - входной поток дуги ( хъ, я4)) по этому маршруту, как показано на рис. 11.18, дает максимальный допустимый поток со значением 61 5, и для этого значения подучающийся поток показан ( подчеркнутыми числами) на рис. 11.19 а, причем дуга ( хь, хе) насыщена. Посылая поток б по циклу и передавая его по аугментальной цепи к I, как показано на рис. 11.19 а, получаем поток, изображенный на рис. 11.196 подчеркнутыми числами. [18]

Аугменталъное дерево - это альтернирующее дерево относительно данного паросочетания, удовлетворяющее условию: существует ребро от какой-нибудь внешней вершины дерева х0, до некоторой экспонированной вершины хе, не принадлежащей дереву. Единственная цепь, идущая от корня дерева до вершины х0 и далее - по ребру ( х0, ее), будет тогда аугментальной цепью. [19]

Хн, являющиеся концевыми для ребер из АНОО, будут экспонированными. Альтернирующая цепь, начинающаяся в экспонированной вершине х & 6 X - Хн ( или начинающаяся в корне дерева Н, который также является экспонированной вершиной), может только тогда быть аугментальной, когда она оканчивается в другой вершине х X - Хн. Но аугментальная цепь должна содержать нечетное число ребер, а это означает, что если первое ребро этой цепи идет из экспонированной вершины во внутреннюю, то последнее ребро должно идти из внешней вершины в экспонированную. [20]

Поиск аугменталь-ной цепи осуществляется с помощью расстановки пометок в вершинах графа. Пометки указывают, вдоль каких дуг может быть увеличен поток и на сколько. Как только найдена одна из таких цепей, поток вдоль нее увеличивают до максимального значения, все пометки в вершинах стираются и вновь полученный поток используется в качестве исходного при новой расстановке пометок. Алгоритм заканчивает работу и дает максимальный поток, если нельзя найти ни одну аугментальную цепь. Алгоритм применяется следующим образом. [21]

Алгоритм начинает работу с произвольного допустимого потока ( можно взять и нулевой поток), затем стремятся увеличить величину потока с помощью систематического поиска всех возможных аугментальных цепей потока от 5 к I. Поиск аугменталь-ной цепи осуществляется с помощью расстановки пометок в вершинах графа. Пометки указывают, вдоль каких дуг может быть увеличен поток и на сколько. Как только найдена одна из таких цепей, поток вдоль нее увеличивают до максимального значения, все пометки в вершинах стираются и вновь полученный поток используется в качестве исходного при новой расстановке пометок. Алгоритм заканчивает работу и дает максимальный поток, если нельзя найти ни одну аугментальную цепь. Алгоритм применяется следующим образом. [22]

Страницы: 1 2