назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [ 73 ] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


73

ный. Для того чтобы убедиться в этом, рассмотрим два случая: 1) последовательность С содержит только дуги прямого направления; 2) последовательность С содержит дуги как прямого, гак и обратного направления.

В каждом из этих случаев мы покажем, как получить поток большей величины, чем данный.

Рассмотрим случай 1. Пусть / (х, у) - максимальная величина, на которую может быть увеличен поток по дуге без нарушения ограничения на пропускную способность. Положим к = min i{x,y).

Тогда к> 0. Для того чтобы модифицировать поток в сторону увеличения, увеличим значения величин потоков на всех дугах из С на величину к, В этом случае ни одно из ограничений на пропускные способности нарушено не будет. Легко видеть, что условия сохранения потока для всех вершин также будут удовлетворяться. Следовательно, новый поток, с одной стороны, является допустимым, а с другой стороны, имеет величину на к большую, чем исходный.

Рассмотрим случай 2. В этом случае в последовательность С входят как дуги прямого направления так и обратного. Пусть г {х,у) - максимальная величина, на которую поток может быть уменьшен по дуге (х,у).

Положим также к\ = min г(х,у) и к2= min i(x,y).

(x,y)GCrR{х,у)СЫ

Обе величины к и , а следовательно, и min ( Atj , 2) > 0. Для того чтобы модифицировать поток в сторону увеличения, увеличим значения величин потоков на всех дугах из С прямого направления на величину min (1, 2) сех дугах из С обратного направления уменьшим величину потока на эту же величину min (i, Л:2). В этом случае ни одно из ограничений на пропускные способности нарушено не будет. Легко видеть, что условия сохранения потока для всех вершин также будут удовлетворяться. Следовательно, новый поток, с одной стороны, является допустимым, а с другой стороны, он имеет величину на min ( Atj , А:2) большую, чем исходный.

Если сток не может быть помечен, то это означает, что поток является максимальным. Для обоснования этого рассуждения рассмотрим понятие разреза.

Определение 1. Выберем любое множество F, содержащее сток, но не содержащее источник. Тогда множество дуг (х,у) для которых х F, а yeV называется разрезом сети.



Определение 2. Величиной разреза называется сумма пропускных способностей дуг, входящих в разрез.

Разрез - это множество дуг, удаление которых из сети приводит к тому, что невозможно пройти из источника в сток по оставшимся дугам. В сети существует несколько разрезов. Например, для сети, изображенной на рис. 8.5 существуют следующие разрезы:

1)для множества F = {2,4} разрез состоит из множества дуг {(1,2),(3,4)}.

Величина разреза равна 2 + 1=3;

2)для множества F = {1,2,4} разрез состоит из множества

дуг{(1,2),(1,3)}.

Величина разреза равна 2 + 8=10.

Лемма 1 и лемма 2 устанавливают связь между разрезами и максимальным потоком.

Лемма 1. Величина любого допустимого потока из источника в сток не больше, чем величина любого разреза.

Доказательство. Рассмотрим произвольный разрез, определяемый множеством V, Пусть W- все остальные вершины сети, не входящие в множество V. Пусть xy - величина потока для дуги (у), а z - общая

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

Sx-Zx.=z.(8.3)

ieW ieW JgV jeV

Учитывая, что первая сумма из данного соотношения не больше величины разреза, можно сделать вывод о справедливости леммы 1.

Лемма 2. Если сток не может быть помечен, то величина некоторого разреза сети равна величине потока.

Доказательство. Пусть V- множество непомеченных вершин, а W - множество помеченных вершин. Рассмотрим дуги (у), для которых ieW, 3, 7 € К, тогда для них справедливо = су. Это следует из того,

что в противном случае мы смогли бы пометить вершину j из множества V (так как дуга (ij) является дугой прямого направления), что противоречило бы определению множества V.



Рассмотрим дуги (iJ), для которых ieV, а JeW, тогда для них справедливо ху = О. Это следует из того, что в противном случае мы

смогли бы пометить вершину / из множества К(так как дуга (iJ) является дугой обратного направления), что противоречило бы определению множества V.

Тогда из соотношения (3) видно, что величина разреза равна величине потока.

8.4. Задача о минимальном остове

Пусть дан связный неориентированный граф Г = (V,R\ где как обычно К={1, «}. Каждому ребру (у) е R приписано некоторое число Су > О. Назовем остовом графа Г любое такое подмножество R множества ребер R, что Г = (V,R) есть связный (неориентированный) граф. Длиной остова R назьшается величина

(iJ)eR

т.е. сумма длин ребер, входящих в R.

Требуется найти остов графа Г, имеющий наименьшую длину.

Задачи такого вида часто возникают на практике.

Пример. В городе имеются шесть вычислительных центров, между каждыми двумя из которых необходимо установить связь, возможно, через другие центры. На рис. 8.6 показано, между какими центрами можно установить непосредственную связь и какими при этом будут затраты на прокладку кабеля с учетом городских условий.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [ 73 ] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]