Дискретная математика (998286), страница 41
Текст из файла (страница 41)
К Т = о г)геп гегпгпт негде выделять ) 228 Глава 8. Связность епй 1Е е +- Т; е — > Т ( стоим в вершине е) 1Е Г[в] Г1 У = Ш тЪев С:=ССМ[е] ( зто КСС ) У: = У ~ (е) ( удалить вершину ) и +- Т ( снять'е со стека ) КСС ( возврат из тупика ) еЬе Еог и н Г[е] оо 1Е е[и! = О тоеп и -ь Т ( положить и в стек ) с[и]: = 1 ( отметить и ) еЬе гереаг ге +- Т ( ге — склеиваемая вершина ) У: = У 1 (ги) ( удалить ее ) Г[о]: = Г[и] С Г[ге] ( запомнить смежность ) М[о]: = М[и] О М[ге]( склеивание вершин ) нптй и = ге ге -ь Т( чтобы не убрать ту вершину ) У: = У О (ш) ( к которой слили ) епо!Е КСС ( поиск в глубину ) епг( Еог епо 1Е 8.7. Кратчайшие пути Задача нахождения кратчайшего пути в графе имеет столько практических применений н интерпретаций, что читатель, без сомнения, может сзм легко привести множество примеров.
Здесь рассматриваются два классических алгоритма, которые обязан знать каждый программист. 8.7.1. Длина дуг Алгоритм Уоршалла позволяет ответить на вопрос, существует ли цепь (о,о). Часто нужно не только определить, существует ли цепь, но и найти эту цепь. Если задан орграф С[У, Е), в котором дуги помечены числами (эти числа обычно называют весами, или длинами, дуг), то этот орграф можно представить в виде матрицы весов (длин) С: О, дляв=у С[г',у] = с;,, конечная величина, если есть дуга из Е в.у, со, если нет дуги из ( в,1.
Длиной пути называется сумма длин дуг, входящих в этот путь. Наиболее часто на практике встречается задача отыскания краягчшаиего пути. 229 8.7, Кратчайшие пути В.7.2. Алгоритм Флойда А лгоритм Флойда находит кратчайшие пути между всеми парами вершин в (ор)графе. В этом алгоритме для хранения информации о путях используется матрица Н[1..р, 1,.р], где )с, если !с — первая вершина, достигаемая на кратчайшем пути из г в Я Н[г,Я = О, если из ! в ) нет пути. ОТСТУПЛЕНИЕ Матрица Н размера 0(рз) хранит информацию обо всех (кратчайших) путях в графе.
Заметим, что всего в графе 0(рз) путей, состоящих из 0(р) вершин. Таким образом, непосредственное представление всех путей потребовало бы памяти объема 0(рз). Экономия памяти достигается за счет яптерпрепшции предсищелеяия, то есть динамического вычисления некоторой части информации вместо ее хранения в памяти.
В данном сяучае любой конкретный путь (и, е) легко извлекается нз матрицы с помощью следующего алгоритма. щ: = и; угеЫ ге( первая вершина ) и ййе ге ~ е до ю: =Н[ш,и] у!е(г( ги( следующая вершина ) спи майе Алгоритм 8.3. алгоритм Флойда Вход: матрица С[1..р,1..р] длин дуг. Выход: матрица Т[1..р,1..р) длин путей и матрица Н[1..р,1..р] самих путей. Гог ! 6ощ 1 Го р йо Гог У 6ощ 1 Го р йо Т[ь',Я: С[АУ] ( инициализация ) Ы С[1„Я = оо Гйеп Н[6 Я: = О ( нет дуги нз 1 в У ) еЬе Н[6 У]: = У ( есть дуга из 1 в У ) епй Е ев1 (ог епй гог йгг 1 6 ого 1 Го р йо (ог у 6 ощ 1 Го р йо 6и к 6 ощ 1 Го р до !!1~;х.ту,г] ~ 8 1м йх,т[1;й] р и(ту й] = гту й] > ту,е]+т[йй]) Гйеп НУ, Й]: = НУ, 1] ( запомнить новый путь ) Ту, я]:=Ту,г]+ Т[6'я] ( и его длину ) еЫ !г еш! 6>г епд Гог Гог у 6ощ 1 Го и Оо 11 Ту, Я < О Г1геп 230 Глана З.
Связность асор ( нет решения: вершина у входит в цикл отрицательной длины ) епй 1( епй гог епй 1ог ЗАМЕЧАНИЕ Если в С есть цикл с отрицательным весом, то решения поставленной задачи не сушествует, так как можно чнакручиватья на этом цикле сколь угодно короткий путь. ОБОСНОВАНИЕ Алгоритм Флойда имеет много общего с алгоритмом Уоршалла (алгорнтм 1.8). Покажем по индукции, что после выполнения (-го шага основного цикла пр ( элементы матриц Т[Г', Й] и Н[у,(с] содержат, соответственно, длину кратчайшего пути и первую вершину на кратчайшем пути нз вершины г' в вершину й, проходящем через промежуточные вершины из диапазона 1.л, База: з' = О, то есть до начала цикла элементы матриц Т и Н содержат информацню.о кратчайших путях (если таковые есть), не проходящих ни через какие промежуточные вершины.
Пусть теперь перед началом выполнения тела цикла на (-м шаге Т[г', к] содержит длину кратчайшего пути от г' к ]г, а Н[г', к] содержит первую вершину на кратчайшем пути из вершины 1 в вершину ]с (если таковой есть). В таком случае, если в результате добавления вершины ( к диапазону промежуточных вершин находится более короткий путь (в частности, если это вообще первый найденный путь), то он записывается. Таким образом, после окончания цикла, когда ( = р, матрицы содержат кратчайшие пути, проходящие через промежуточные вершины 1..р, то есть искомые кратчайшие пути. Алгоритм не всегда выдает решение, поскольку оно не всегда существует.
Дополнительный цикл по у' служит для прекращения работы в случае обнаружения в графе цикла с отрицательным весом, П 8.7.3. Алгоритм Дейкстры Алгоритм Дейкстры находит кратчайший путь между двумя данными вершинами в (ор)графе, если длины дуг неотрицательны. Алгоритм 8.4. алгоритм Дейкстры Вход: орграф с(г', и), заданный матрицей длин дуг с: апау [1..р, 1..р] о( геа]; з и к— вершины графа Выход: векторы Т: аггау [1..р] ог" геа]; и Н: аггау [1..р] ог О..р. Если вершина е лежит на кратчайшем пути от з к д то Т[е] — длина кратчайшего пути от в к е; Н[е] — вершина, непосредственно предшествующая е на кратчайшем пути.
гог е ггош 1 Го р по Т[е]: = со ( кратчайший путь неизвестен ) Х[е]: = О ( все вершины не отмечены ) епг] Гог Н[в]: = О ( в ничего не предшествует ) Т[в]: =О ( кратчайший путь имеет длину О ... ) аз1 В.т. Кратчайшие пуги Х[в]: = 1 ( ... и он известен ) и: = з ( текущая вершина ) М: ( обновление пометок ) Еог и Е Г1е) йо ЕЕ Х [и[ = О 3 Т[ 4 > Т[и[+ С[и, и[ Свеи Т[и): =Т[е[+ С[и, и] ( найден более короткий путь из з в и через е ) Н[и[: = е ( запоминаем его ) епп ЕЕ евй Еог С:=со;э:=О ( поиск конца кратчайшего пути ) Еог и Егош 1 Со р Йо 1Е Х[и) =ОС Т[и) < С Сйеп и: = и; С: = Т[и[ ( вершина и заканчивает кратчайший путь вз и) еш1 1Е евб Еог !Е и = О СЬеп згор ( нет нутн из 8 в С) епс( 1Е 1Е и = С СЬеп аСор ( найден кратчайший путь нз з в 1) евд 1Е Х[и): = 1 ( найден кратчайший путь из з в и) його М ЗАМЕЧАНИЕ Для применимости алгоритма Дейкстры достаточно выполнения более слабого условия, чем положительность длин дуг.
А именно, достаточно выполнения иеравеиства треугольника: Чи,юш Е У и(и,и) < о(и,ш) +о(ти,и), которое, очевидно, выполняется, если длины дуг неотринательны. ОБОСНОВАНИЕ Для доказательства корректности алгоритма Дейкстры достаточно заметить, что при каждом выполнении тела цикла, начинаюшегося меткой М, в качестве е используется вершина, для которой известен кратчайший путь нз вершины 3. Другими словами, если Х[е[ = 1, то Т[е[ = И(з, е), и все вершины на пути (з, и), определяемом вектором Н, обладают тем же свойством, то есть 'г'и Т[и[ = 1 ~ Т[и] = Щз, и) 8с Т[Н[и[[ = 1. Действительно (по индукции), первый раз в качестве е используется вершина з, для которой кратчайший путь пустой и имеет длину О (непустые пути не могут быть короче, потому что длины дуг неотрицательны). Пусть Т[и[ = И(з,и) для всех ранее помеченных вершин и.
Рассмотрим вновь помеченную вершину е, которая выбрана из условия Т[е[ = пйп Т[н[. Заметим, что если известен л1.1=о 2З2 Глава З. Связность путь, проходящий через помеченные вершины, то тем самым известен кратчайший путь. Допустим (от противного), что Т[п] >Д(з, и), то есть найденный путь, ведущий из з в и, не является кратчайшим. Тогда на этом пути должны быть непомеченные вершины.
Рассмотрим первую вершину ш на этом пути, такую что Т[ш] = О. Имеем: Т[ш] = Ы(з,ш) < й(з,с) < Т[н], что противоречит выбору вершины и. П ЗАМЕЧАНИЕ Известно, что алгоритм Флойда примерно на 50зь менее трудоемок, чем применение алгоритма Дейкстры дли всех пар вершин. Комментарии Изложение центрального результата этой главы — теоремы Менгера 8.3.2 и сопутствующего материала — в основном следует в [23]. Алгоритм нахождения максимального потока в сети заимствован из [11] с небольшими модификациями.
Алгоритм выделения компонент сильной связности приведен в [5], где имеется весьма полный обзор различных алгоритмов обхода и анализа графов, применяемых в программировании. Алгоритмы Флойда и Дейкстры нахождения кратчайших путей принадлежит к числу классических общеизвестных алгоритмов, описание которых можно найти в большинстве учебников по дискретной математике, в частности, в [14, 11]. Упражнения 8.1. Доказать, что если б(С) > (р — 1)/2, то граф С связен. 8.2. Доказать вторую теорему подраздела 8.2.1.
8.3. Доказать, что наибольшее число непересекающихся множеств вершин, разделяющих вершины и и и, равно 8(и, и) — 1. 8.4. «Задача о гареме». Имеется конечное множество юношей, каждый из которых знаком с некоторым конечным подмножеством множества девушек. Каждый юноша желает взять в жены более чем одну знакомую девушку Найти необходимое и достаточное условия решения этой задачи. 8.5. Пусть в сети С(1г, Ь) помимо пропускной способности дуг заданы пропускные способности узлов, то есть задана нагрузка на вершины Р: Ъ" -+ Е+ Для допустимого потока сумма потоков через входящие дуги не должна превышать пропускной способности вершины тп н к ~~~ у(н>В) ~~ Р(ю). 1Ы(и,е)ен1 Найти максимальный поток в такой сети.
Упражнения 2ЗЗ 8.6. Как может измениться количество компонент сильной связности орграфа прн добавлении к нему одной дуги7 8.7. Пусть в графе С(Ъ;Б) заданы вероятности успешного прохождения дуг, 0 ( РЯ ( 1. Вероятность успешного прохождения пути определяется как произведение вероятностей составляющих его дуг. Построить алгоритм нахождения наиболее надежного (то есть имеющего наибольшую вероятность) пути от вершины з к вершине й ГЛАВА 9 Деревья Деревья заслуживают отдельного и подробного рассмотрения по двум причинам. > Деревья являются в некотором смысле простейшим классом графов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
