Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 125
Текст из файла (страница 125)
И ПРИМЕР 16.14. Найдите максимальный поток для сети, изображенной на рис.!6.14. ь 4 9Р" 6 9 Р (6 (4 Первые несколько проходов ничем не примечательны, поэтому опишем их вкратце. На первом проходе помечаем а( —,оо), Ь(а,9), (((а,8), с(Ь,4), е(Ь,4) и г(0,4). Это дает а — з путь (9,0) (4,0) (8,0) а — Ь -4 с — г, и поскольку резерв вершины 8 равен 4, добавляем 4 к каждому потоку, получая (9,4) (4,4) (8,4) а — '4 Ь -4 с — г, что изображено на рис.
16.15. РЯЗДЕ// 76. 1. Сети и потоки 703 ф (),() е е (),() Рис. /6./6 На втором проходе помечаем а( —, со), Ь(а, 5), с/(а,8), с(4/,4), е(((,8) и з(е, 7). Это дает а — з путь (8,0) [9,9) (7,0) а — ' (/ — е -+ и поскольку резерв вершины г равен 7, добавляем 7 к каждому потоку, получая (8,7) (9,7) (7,7) а -4 С( — ~ Е -' г, что изображено на рис. 16.16. Рис. 16./6 На третьем проходе помечаем а( —, оо), Ь(а, 5), (/(а, 1), с(4/, 1), е((1, 1) и з(с, 1). Это дает а — з путь (8,7) (4,0) (8,4) а — (( --) с -+ г, и поскольку резерв з равен 1, добавляем 1 к каждому потоку, получая (8,8) (4Л) (8,5) а — ) с/-'~с что изображено на рис. 16.!7. Рис.
/6.17 Теперь начинается кое-что поинтересней, поэтому дальнейшее описание будет более подробным. Пометим Ь(а,5), но (/ пометить нельзя; помещаем Ь в Я. При выборе вершины Ь из множества Я нельзя пометить вершину с, но можно 704 ГЛЯВЛ 16. Сети пометить е(Ь,5); помещаем вершину с во множество Я. Выбирая е из о, нельзя пометить вершину з, но т.к.
4( еще не помечена, ее можно пометить. Поскольку ребро ()(,е) ориентировано неправильно, полагаем резерв вершины )1 равным ппп(7,5) = 5. Устанавливаем е в качестве предшественника вершины 21 и помещаем вершину б( во множество Я. Выбирая вершину 4( из множества о, имеем единственную возможность — пометить вершину с(И, 3) и поместить с в Я. Выбираем вершину с из множества о и помечаем з(с, 3). Это дает а — з путь (9,4) (б,е) (9,7) (4Л) (8,8) а -'-+ Ь -2 е 2-'- 41 -'-) с и поскольку резерв з равен 3, прибавляем 3 к каждому потоку, исключая ребро ()(, е). Это ребро ориентировано неправильно; вычитаем 3 из его потока, получая (9,7) (б,б) (9,4) (4,4) (8,8) а -' 6 -2 е 2'- г( — '2 с -'2 г, что изображено на рнс.
16.18. ф ,)2.2) (4,1) Гв~ а (чо2) 2 ф а(С,З) (ь, ф ~Фе 2 —.)2,2) (е,б) (9,4) Рис. 16.18 Начинаем последний проход. Сначала Я = (а). Удаляем вершину а из множества Я, помечаем вершину Ь(а,2) и помещаем 6 в Я. Удаляем вершину 6 из множества Я, помечаем е(6,2), с(Ь,2) и помещаем вершины с,е во множество Я. Удаляем е из Я, помечаем )1(е,2), поскольку резерв )1 равен минимуму из потока ребра ()(, е) и резерва вершины )1.
Помещаем )1 в Я. Затем из Я удаляем )1, но ни один из оставшихся шагов нельзя выполнить, поэтому возвращаемся к шагу 2. Следующим из Я удаляем с, но мы не можем выполнить ни один из оставшихся шагов и возвращаемся к шагу 2. Множество Я пусто, поэтому алгоритм завершен. Результат изображен на рис. 16.!9.
9 )2,2) (4,1) Е) л ГВв~,. а(-, ) ~~ Гб а(7с) Гв Ф' 'Ф аУл )2,2) (г) 3) (9,4) Рис. 1б.19 ТЕОРЕМА 16.15. Алгоритм максимального потока строит максимальный поток для сети. РАЗДЕЛ 16.1. Сети и потоки 705 ДОКАЗАТЕЛЬСТВО. Пусть о — множество всех вершин, помеченных во время последнего прохода алгоритма, и Т = Ъ' — о. Множество о не пусто, поскольку а Е л. Если е — ребро из 5 в Т, например, е = (з, г), так что Г не помечено, то )(е) = с(е), так как иначе с могла быть помечена.
Если е — ребро из Т в о, скажем, е = (с, е), так что с не помечена, то ) (е) = О, так как в противном случае с могла быть помечена. Согласно следствиям 16.11 и 16.12 поток )' — максимальный, и (о, Т) — минимальное сечение. Следствие 16.12 утверждает, что если юа1()) = С(Я,Т) для некоторого потока )' и а — з сечения (Я,Т), то )' — максимальный поток, а С вЂ” минимальное сечение. В изложенном выше алгоритме показано, как находить минимальное сечение (о',Т), так что ) — максимальный поток, иа1()) = С(о',Т).
Соединяя все вместе, приходим к теореме. ТЕОРЕМА 16.16. Поток ) на заданной сети )т' является максимальным тогда и только тогда, когда существует сечение (о, Т) такое, что иа1()) = С(о, Т). Заметим, что в примере 16.13 множество о состоит из всех вершин, которые можно пометить при последнем проходе, поэтому о = (а,Ь,И) и Т = (с,з), В примере 16.14 о = (а,Ь,с,д,е) и Т = (г). ° УПРАЖНЕНИЯ 1. Для сети, изображенной на рис. 16.20, а) проверить сохранение потока в вершинах Ь, с и 4; б) найти иа1()), величину потока; в) найти значение С(о, Т), где о = (а, Ь, с, Н); г) найти значение С(5,Т), где о' = (а,И,е); д) найти значение С(о, Т), где о = (а, Ь, а). Ь вЂ” ' — юс бз,з) 4 — — ~с 0 Й4) Рис.
)б.20 2. Для сети, изображенной на рис. 16.21, а) проверить сохранение потока в вершинах Ь, Ы и е; б) найти иа1()), значение потока; в) найти значение С(о, Т), где о = (а, Ь,с,й); г) найти значение С(5, Т), где 5 = (а, Ь,а, е); д) найти значение С(о, Т), где о = (а, Ь,е). 706 ГПАВА 1б. Сети 3. Дополнить поток в сети, изображенной на рис. 16.22, так чтобы имело место сохранение потока. 4. Дополнить поток в сети, изображенной на рис. 16.23, так чтобы имело место сохранение потока. И (1,1) е Рис. !б.22 Рис.
!б,23 5. Найти максимальный поток в сети, изображенной на рис. !6.24. 6. Найти максимальный поток в сети, изображенной на рис. 16.25. Ь вЂ” с 3 Ь вЂ” с 1О Рис. !б.24 Рис. !б.2б 7. Найти максимальный поток в сети, изображенной на рис. 16.26. 8. Найти максимальный поток в сети, изображенной на рис. 16.27. и ° ° — -+ Ф г (1,1) е Рис. !б.2б Рис.
!б.27 Ь (б) Ы вЂ” е е (1, 1) ь е 5 а г 2 РяздЕЛ тб.2. Паросочетание 707 9. Найти минимальное сечение для потока в сети из упражнения 5. 10. Найти минимальное сечение для потока в сети из упражнения 8. 11. Найти минимальное сечение — разрез для потока в сети из упражнения 7. 12. Найти минимальное сечение — разрез для потока в сети из упражнения 8. 16.2. ПАРОСОЧЕТАНИЕ Теория потоков в сети имеет непосредственное применение в теории графов. Вспомним, что граф С = (Ъ; Е) назывется двудольным графом, если Ъ' можно выразить как несвязное объединение непустых множеств, например, Ъ' = Аи В, так что каждое ребро имеет вид 1а,6), где а Е А и Ь Е В.
Таким образом, каждое ребро соединяет вершину из А с вершиной из В, и не существует двух вершин из одного и того же множества (А или В), которые соединены друг с другом. Подмножество М множества Е называется ларосочетанием, если никакие два ребра из М не имеют общей вершины.
Таким образом, никакие два ребра не являются инцидентными. Если 1а, Ь) — ребро в паросочетании, тогда как а, так и 6 имеет ааросочетающие ребра. При этом вершины а и Ь называются паросочетанными. Например, для двудольного графа, изображенного на рис. 16.28, паросочетающие ребра, обозначенные на рисунке жирной линией, образуют паросочетание. ь, Ьз а2 ь, Ь Рис. 16.28 Наглядным примером может служить соответствие между множеством работников и множеством заданий для них. Ребра графа показывают, какие задания может выполнить тот или иной работник. Еще один пример — паросочетание множества юношей и множества девушек.
Паросочетающие ребра соединяют совместимые пары. (Будем считать, что эти множества образуют двудольный граф, и воздержимся от дальнейших комментариев.) ОПРЕДЕЛЕНИЕ 16.17. Паросочетание М на двудольном графе С = (К Е) назывется максимальным, если никакое другое паросочетание на С не содержит ребер больше, чем М. ОПРЕДЕЛЕНИЕ 16.18. Паросочетание М на двудольном графе С = (1г, Е), где Ъ' = А и В, называется полным, если для каждого а е А существует 6 е В такое, что (а,6) Е М. 708 ГЛАВА 16. Сеизи ПРИМЕР 16.19. Граф, изображенный на рис. 16.29, максимальный, но не полный. а, Ьз аз ь, аз Рис.
!6.29 Очевидно, нам нужен метод нахождения максимального паросочетания. Для упрошения задачи заменим рассматриваемый двудольный граф ориентированным графом, ребра которого имеют начало в вершинах множества А и заканчиваются в вершинах множества В. Добавим также две новые вершины а и з и ребра из вершины а в каждую вершину множества А, и ребра из каждой вершины множества В в вершину з. Граф, изображенный на рис.
16.30, превратится в граф, изображенный на рис. 16.3!. ь, а, ь, аз Рис. т6.3! Рис. !6.30 Теперь двудольный граф превращен в сеть. Такая сеть называется сетью паросочетаний. Для каждого а, 6 А обозначим через е, ребро из а в аз. Положим пропускную способность с(е,) = 1 для всех е,. Аналогично, для каждого Ь, 6 В обозначим через е, ребро из Ь, в г и положим пропускную способность с(ез) = 1 для всех с;. Для ребра )с,з из а; в Ь положим с(!сзз) = !А~ + 1, так что пропускная способность больше, чем количество вершин в А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
