Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 123
Текст из файла (страница 123)
Имеем О 2 О 8 О О О О О О 5 О О О О О е 2 О 4 О О О О 3 О О 3 О У У О 3 О О О 6 О 6 О О 1 4 О О О О О 5 О О О У О 8 е О О 5 О О О 4 О О 3 3 О О 8 О О 5 О О О 4 О О 3 3 О 666 ГЛАВА 15. Деревья Теперь выбираем наименьшее ненулевое значение из 1-ой, 4-ой или 5-ой строки. В данном случае это значение, равное 1 в столбце 2 строки 4. Таким образом, в качесте следующего ребра выбрано (ох ьа). Остальные значения в столбце полагаем равными 0 и в восьмой строке этого столбца устанавливаем значение, равное У. Помещаем * в восьмом столбце строки 2, показывая, что эти элементы можно теперь использовать, как и элементы строк 1, 4 и 5, поскольку эти строки представляют ребра из юг от о4 и гв в смежные вершины. Имеем 0 8 х 0 0 х 5 0 0 0 4 0 0 3 3 0 Используя ту же процедуру, выбираем значение 4 в строке 4 столбца 3 и значение 4 в строке 5 столбца 6, что дает ребра (ох, оз) и (оз, ов), соответственно, и матрицы Наконец, выбираем значение 3 в строке 6 столбца 7, что дает ребро (ое,ет) и матрицу 0 0 0 0 0 0 0 0 4 0 0 3 О 0 5г а также остовное дерево, изображенное на рис.
!5.133. 0 0 0 0 0 0 0 1 0 0 0 0 0 0 У У 0 0 2 0 0 0 0 0 0 4 0 0 0 2 0 0 0 0 0 0 0 У У У 0 0 0 0 2 0 0 6 0 0 0 0 0 0 0 0 1 4 0 0 0 0 0 2 0 0 0 5 0 0 0 О 0 0 О ипил 0 8 х 0 0 5 0 х 0 0 4 0 х 0 3 3 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 1 4 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 У У У (7 У 0 0 0 0 0 0 0 У 0 0 0 0 0 0 1 4 0 0 0 0 0 0 У У 0 2 0 0 0 0 0 0 0 0 0 0 2 0 4 0 0 0 0 0 0 иихф 8 х 0 0 х 0 0 3 х 0 РАЗДЕЛ 16.6. Минимальные вотивные деревья 889 Рис. 16.133 ° УПРАЖНЕНИИ 1.
Заданы взвешенные графы, изображенные на рис. 15.!34 и !5.135, найдите минимальные остовные деревья, воспользовавшись: а) алгоритмом Крускала; б) алгоритмом Прима. в) матричным алгоритмом Прима; а 4 с е г Ь 3 е 6 3 Рис. 16.134 Рис. 16.136 2. Заданы взвешенные графы, изображенные на рис. 15.13б и 15.137, найдите минимальные остовные деревья, воспользовавшись; а) алгоритмом Крускала; б) алгоритмом Прима; в) матричным алгоритмом Прима. а 3 Ь 3 с 1 б 4 3 3 1 г Ь е 1 Рис. 16.136 Рис.
16.137 3. Заданы взвешенные графы, изображенные на рис. 15.138 и 15.139, найдите минимальные остовные деревья, воспользовавшись: а) алгоритмом Крускала; б) алгоритмом Прима; 690 глдм тб. деревьв в) матричным алгоритмом Прима. а Ь с Ь В с 3 Ь Ы с Рис. 15.133 Рис. 15.139 4. Заданы взвешенные графы, изображенные на рис. 15.140 и 15.141, найдите минимальные остовные деревья, воспользовавшись: а) алгоритмом Крускала; б) алгоритмом Прима; в) алгоритмом Прима с матрицами. 4 Ь 3 Н 10 В В ь 3 Рис.
15.141 Рис. 15.140 692 ГЛКВА 1б. Сети Например, граф, изображенный на рис. !6.1, является примером сети, где числа на каждом ребре обозначают пропускную способность. Для этой сети, которая представлена как нефтепровод, введем понятие потока (количество нефти, проходящее через трубы нефтепровода). Таким образом, для каждого ребра е имеется значение г" (е), которое является потоком через конкретное ребро или трубу. Очевидно, величина потока не может превысить пропускную способность трубы. Потребуем также, чтобы поток, входящий в вершину, был равен потоку, выходящему из вершины, за исключением вершин а и х.
Это называется сохранением потока. Пусть !п(е) — множество ребер, для которых е — конечная вершина, и оШ(о) — множество ребер, для которых о— начальная вершина. Таким образом, опг(о) — множество ребер, выходящих из вершины и, и гп(п) — множество ребер, входящих в вершину ш Следовательно, имеем следующее определение.
Допустим, имеется фиксированный поток. Пусть поток(а) = ~.е,„м, г"(е), т.е, лоток(а) — поток, вытекающий из источника а, и поток(х) = ~ееы1, г(е), т.е. поток(х) — поток, втекающий в сток х. Пример потока в сети, где первый элемент упорядоченной пары на каждом ребре — пропускная способность, а второй — поток, демонстрирует рис.
16.2. РАЗМЕЛ 16.1. Сети и потока 693 Поток через каждое ребро меньше, чем его пропускная способность. Обратите внимание, что для вершины Ь поток, втекаюший в Ь, равен 4 и поток, вытекаюший из Ь, равен 4. Таким образом, оба потока совпадают, и в вершине Ь имеет место сохранение потока. Это верно также и для всех других вершин, за исключением вершин а и з.
Воспользуемся принципом сохранения потока для доказательства того, что интуитивно кажется очевидным. А именно, поток из а равен потоку в з, т.е. лоток(а) = поток(з), что и утверждает приведенная ниже теорема. Рассмотрим сначала конкретную сеть. Заметим, что для потока на рис. 16.2 выполняется равенство лоток(а) = погпок(з) = 6. Пусть Я вЂ” множество вершин (Ь, с, и), а Т = Ъ' — Я вЂ” множество вершин (а, г',з). Если просуммировать потоки в 5, то согласно приведенной ниже таблице получим, что входящий поток равен 9 и выходящий поток равен 9. Таким образом, разность потоков равна О. Если во множество 5 добавить вершину а, получим, что разность 15 (выходящий поток) и 9 (входяший поток) равна 6 = поток(а).
Заметим, что ребра (а,Ь), (Ь,с) и (Ь,Н) присутствуют в колонке для входящего и выходящего потока, потому что обе вершины каждого ребра принадлежат Я. При вычитании эти ребра сокращаются, поэтому, удалив их из обеих частей, получаем 694 Глд8А 16.
сети Снова разница входящего и выходящего потока равна 6. Но поскольку ребра, обе вершины которых принадлежат 5, удалены, то выходящий поток — это сумма потоков ребер, которые идут из 5 в Т, а входящий поток — это сумма потоков ребер, которые идут из Т в 5. Аналогичные рассуждения будут использованы в приведенной ниже теореме. ТЕОРЕМА 16.3. Для любого фиксированного потока ) лоток(а) = з г"(е) = ~ ~)(е) = поток(г). еяоое(а) еЕ1о(е) ДОКАЗАТЕЛЬСТВО.
Пусть 5 — подмножество множества Ъ', содержащее а, но не содержащее з, а Т = Ъ' — 5. Для е Ф а,з из условия сохранения потока имеем ~ „еы(„),)(~) = ~.е,„,(„),) (е). Следовательно, суммирование по вершинам, принадлежащим 5 — (а), дает )(е) = ~~ ~ )(е) оЕЯ-(а) еяооо(о) ояз-(а) ея)а(о) или )(е) — ~ ~ )(е) = О. оЕЯ-(а) ея)а(о) оЕЯ-(а) есоаа(о) Поэтому, если включить а, получим ) (е) — ~~ ~~ )'(е) = ~~ ) (е). она ея(а(о) еяоое(а) она евере(о) Пусть (5,Т) — множество всех ребер из 5 в Т, т.е.
(5,Т) = (е: начальная вершина е принадлежит 5, а конечная вершина е принадлежит Т). Аналогично, пусть (Т,5) — множество всех ребер из Т в 5. Рассмотрим опять )'(е) — ,'> ~~~ ) (е). оса еаза(о) оЕЯ еяоое(а) РЯЗДЕГ) 1б.1. Сети и потоки 695 В случае, когда начальная и конечная вершины ребра е принадлежат Я, е появляется в обеих суммах и, следовательно, взаимно сокращается. Если исключить такие ребра, то слева получим только ребра, идущие из Я в Т, а справа — только ребра, идущие из Т в Я. Таким образом, имеем 1(е) — ~~» ~ ) (е) = ~) 1(е) — ~~» )(е). еея ееш(е) ее(я,т) ее(т,я) евя евое»(е) Следовательно, ) (е) — ~ 1(е) = р Г"(е), ее(я,т) ее(т,я) евое»(е) т.е, для любого заданного множества вершин 5, содержащего а, но не содержащего з, разность выходящего из Я и входящего в 5 потоков равна поток(а), т.е.
потоку, выходящему из источника а. Теперь пусть Я = Ъ' — (з), так что Т = (з). Тогла ~, (ят) 1(е) есть пРосто поток, вливающийсЯ в з, так что )'(е) = »» )'(е) = поток(з) ее(я,т) ешь(е) и ~, (т, я) ) (е) = О, поскольку это поток, вытекающий нз з. Следовательно, т(е) — ~ т'(е) = ~~» г" (е) = поток(з) ее(я,т) ее(т,я) еЕ»о(е) и поток(а) = поток(а). При доказательстве теоремы попутно доказано такое следствие.
СЛЕДСТВИЕ 16.4. Пусть 5 — подмножество множества Ъ', содержащее а, но не содержащее з, и Т = $' — 5. Тогда 1'(е) — ~~» Г" (е) = поток(а) = поток(з). ее(я,т) ее(т,я) ОПРЕДЕЛЕНИЕ 16.6. Величина потока т, обозначаемая как оа((г"), равна лоток(а) = поток(г). ОПРЕДЕЛЕНИЕ 16.6. Пусть Я вЂ” подмножество множества»г и Т = (г — 5.
Тогда (е: е Е (Ь',Т)) называется сечением. Если а е Я и з е Т, то сечение называется а — а сечением. ОПРЕДЕЛЕНИЕ 16.7. Величина С(Я,Т) = ~, (я т) с(е) называется пропуск- ной способностью сечения. 696 ГЛЯВЯ 16. Сети ОПРЕДЕЛЕНИЕ 16.8.
Поток ( в сети называется максимальным лолгоком, если эа((() > еа1()) для любого возможного потока г" в сети. ОПРЕДЕЛЕНИЕ 16.9. а — з сечение (Б,Т) называется минимальным сечением, если С(5',Т) не больше пропускной способности любого другого а — з сечения. ТЕОРЕМА 16.10. Пусть о — подмножество множества )г, содержащее а, но не содержащее з, и Т = Ъ' — о. Тогда оа1(() < С(о',Т). ДОКАЗАТЕЛЬСТВО.
па(Я = ~~),((е) — ~~~ ((е) < ~> )(е) < ~ с(е) = С(5, Т). ° е1я,т! .е1т,з> .е1з,т> е1 з,т> СЛЕДСТВИЕ 16.11. Если оа!()') = С(5,Т) для некоторого потока (, а а — а сечения (5',Т), то )' — максимальный поток, а С вЂ” минимальное сечение. СЛЕДСТВИЕ 16.12.
Для некоторого потока )' и а — сечения (Я,Т) равенство эа1(г") = С(5,Т) имеет место тогда и только тогда, когда ((е) = с(е) для всех е Е (о, Т) и )(е) = 0 для всех е Е (Т, 5). Опишем способы определения максимального потока сети. Рассмотрим сеть, изображенную на на рис. 16.3. Максимальный поток (не обязательно единственный) легко найти способом, про- иллюстрированным на рис. 16.4. (6,5) Ь вЂ” ~ с ~1/ ф Д2) (44) Рис 164 В данном случае известно, что поток максимальный, потому что величина потока, выходящего из а, не может превысить сумму пропускных способностей ребер, выходящих из а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
