Дискретная математика

167 Теорема 5.25. Для любой (транспортной) сети величина максимального потока равна наименьшей пропускной способности разрезов. Эта теорема является подтверждением английской пословицы; <<цепь не крепче своего самого слабого звена». Если хотя бы для одного разреза её пропускная способность мала, например равна р, то максимальный поток не больше р. Алгоритм нахождения максимального (полного) потока в (транспортной) сети. Пусть имеем (транспортную) сеть 5 и пусть поток ф в сети и пропускные способности дуг принимают целочисленные значения. Для нахождения максимального потока в сети S выполняем следующие действия. Шаг 1. Полагаем, что начальный поток (р равен нулю, т. с. для любой дуги X сети ср(х)=0. Полагаем S*=S. Шаг 2. Удаляем из орграфа S* все дуги, являющиеся насыщснш>1мн при потоке (р в сети S*. Полученный орграф вновь обозначим через i"?*. Шаг 3. Ищем в S* простой путь Z(vo,vt) из Уд в vj.. Если такого пз'ти нег, то р - искомый поток в сети S. Иначе идем к следующему шаг}'. Шаг 4. Увеличиваем поток (р(х) на каждой дуге л- из КУГ . Л ' О на одинаковую величину а, а>0, такзто, что, по крайней мере, одна дуга из Z(vi),vk) оказывается насыщенной, а потоки по остальным дугам из Z( vu.vi. ) не превышают их пропускных способностей. При этом величина потока (р также увеличивается на а и поток (р остается в S допустимым. После этого переходим к шагу 2. § 20. Вопросы и темы для самопроверки 1. Основные типы графов. 2. Различные способы задания графа. 3. Изоморфизм графов. 4. Число ребер графа. 5. Цепи и простые цепи. 6. Связные компоненты. 7. Матрица смежности графа и орграфа. 8. Можно ли опредепилъ покальт1ые степени вершин графа по ее матрице смежности? 9. Операции над матрицами смежности. 10. Матрицы смежности и достижимости графа и орграфа, 11. Критерии изоморфизма фафов. 12. Матрица инциденций графа и орграфа.