Новиков Ф.А. Дискретная математика для программистов (860615), страница 54
Текст из файла (страница 54)
Кратчайшие пути289end forfor г from 1 to p dom : = оо { поиск конца нового кратчайшего пути }for и G V doif Х[и] = 0 к Т[и} < га thenv: = u,m: = Т[и] { вершина и заканчивает новый кратчайший путь из s }end ifend forfor и e F(v) doT[u]: = m i n ( T [ u ] , T [ v ] + C [ v , u ] ){ пересчет оценки длины пути из s в и через v }end forX[v]: = l { найден кратчайший путь из s в v}end forПриведённый вариант алгоритма основан па той же идее, что ипредшествующий: па очередном шаге нужно выбрать вершину v, до которой мыточно знаем кратчайший путь от s, и пересчитать оценки путей для вершин,смежных с v. Такой вершиной па первом шаге окажется вершина s (для нее T[s] =— 0).
На следующих шагах новой вершиной v является вершина, которая еще нерассмотрена= 0) и для которой оценка пути минимальна. Действительно,даже если в будущем мы обнаружим другой путь, ведущий в v, его длина можетбыть разве что больше.•ОБОСНОВАНИЕТаким образом, грубая оценка трудоёмкости алгоритма Дейкстры составляет0(р2), поскольку вложенные циклы выполняются 0(р) раз. Заметим, что во внутреннем цикле явно совершается излишняя работа: вершины, далекие от s, немогут повлиять на выбор v на ранних шагах и их не стоит рассматривать раньше времени.
Известно, что, более тщательно подбирая структуры данных дляпредставления графа, можно уменьшить трудоёмкость алгоритма Дейкстры до0{q log2 р).ЗАМЕЧАНИЕПоследнее замечание этого подраздела относится к его названию. Совокупность путей отвершины s к другим вершинам образует корневое дерево в смысле подраздела 9.2.1. Действительно, никакой кратчайший путь, очевидно, не содержит контуров (напомним, чтодлины дуг положительны). Всякий узел достижим из корпя по построению.
Более того,этот путь единственный, поскольку даже если в вершину ведет несколько кратчайшихпутей одинаковой длины, алгоритм выберет из них только один. Отсюда и из определений подраздела 9.2.1 немедленно следует, что традиционное название, использованноедля данного подраздела, оправданно.8.6.5. Кратчайшие пути в бесконтурном орграфеАлгоритм Дейкстры применим, если длины дуг неотрицательны.
Существуетэффективный алгоритм, который позволяет пайти дерево кратчайших путей в290Глава 8. Связностьорграфе, даже если длины дуг могут быть отрицательными, но известно, чтоорграф не содержит контуров.В произвольном бесконтурном орграфе G(V,E) узлы можно перенумеровать так, что V (vi,Vj) е Е (г < j).ЛЕММАП О теореме 7.5.2 отношение достижимости в бесконтурном графе есть строгое частичное упорядочение на конечном множестве. Применяя алгоритм топологической сортировки 1.12, получаем требуемую нумерациюузлов.•ДОКАЗАТЕЛЬСТВОДопустим теперь, что узлы в бесконтурном орграфе перенумерованы так, чтокаждая дуга ведёт из узла с меньшим номером в узел с бблыиим номером, аисточник этого орграфа, из которого нужно построить дерево кратчайших путей,имеет номер 1.
Тогда алгоритм 8.6 находит кратчайшие пути от узла 1 до всехдостижимых узлов.Алгоритм 8.6 Определение расстояний от источника в бесконтурном графеВход: орграф G(V, Е), заданный матрицей длин дуг С : array [1 ..р, 1 ..р] of real исписками предшествующих узлов Г - 1 ; источник имеет номер 1.Выход: вектор Т : array [l..p] of real длин кратчайших путей от источника,for i from 1 to p doT[i]: = C[l, z] { начальное приближение определяется матрицей }end forfor i from 2 to p dofor j e r - 1 ( z ) doT[i]: = min(T[z], T\j] + C[j,i]) { пересчёт оценки длины пути }end forend forОБОСНОВАНИЕДокажем индукцией по г, что основной цикл имеет инвариантV j е l..z (T[j] = d(l,j)). База: если j = 1, то Т[1] = 0 = d ( l , l ) . Пусть теперьV j < i (T\j] = d(l,j)).
В кратчайшем пути (l,z) все промежуточные узлы имеютномера больше 1 и меньше z по построению орграфа, в частности, вершина j,предшествующая г на кратчайшем пути, будет выбрана во внутреннем цикле, длянеё по индукционному предположению T\j] = d(l, j), и значит, Г [г] = d(l,z).•ЗАМЕЧАНИЕВ алгоритме используется множество «предшествования»T-\V) ^{ « 11; € Г ( « ) } ,которое совпадает со списками смежности Г(и) для графов и не пересекается с T(v) длянаправленных орграфов.Упражнения291КомментарииИзложение центрального результата этой главы — теоремы Менгера (8.2.2) исопутствующего материала — в основном следует [28]. Алгоритм нахождениямаксимального потока в сети заимствован из [21] с небольшими модификациями.
Алгоритм выделения компонент сильной связности приведен в [4] и [20], гдеимеется весьма полный обзор различных алгоритмов обхода и анализа графов,применяемых в программировании. Алгоритмы Флойда и Дейкстры нахождениякратчайших путей принадлежит к числу классических общеизвестных алгоритмов, описание которых можно найти в большинстве учебников по дискретнойматематике, в частности, в [8], [27], [9].Упражнения8.1 а. Доказать, что если 6(G) > (р - 1)/2, то граф G связен.8.1 б.
Доказать вторую теорему подраздела 8.1.2.8.2. Доказать, что наибольшее число непересекающихся множеств вершин, разделяющих вершины и и v, равно d(u, v) - 1.8.3. «Задача о гаремах». Имеется конечное множество юношей, каждый из которых знаком с некоторым конечным подмножеством множества девушек.Каждый юноша желает взять в жены более чем одну знакомую девушку.Найти необходимое и достаточное условие решения этой задачи.8.4.
Пусть в сети G(V, Е) помимо пропускной способности дуг заданы пропускные способности узлов, то есть задана нагрузка на вершины D : V —• R + .Для допустимого потока сумма потоков через входящие дуги не должнапревышать пропускной способности вершины:Найти максимальный поток в такой сети.8.5. Как может измениться количество компонент сильной связности орграфапри добавлении к нему одной дуги?Сравните ответ с ответом на аналогичный вопрос для графов.8.6. Пусть в графе G(V,E) заданы вероятности успешного прохождения дуг,Ve G Е (0 ^ Р[е] ^ 1). Вероятность успешного прохождения пути определяется как произведение вероятностей составляющих его дуг. Построить алгоритм нахождения наиболее падёжного пути (то есть имеющего наибольшуювероятность прохождения) от вершины s к вершине t.Глава 9ДеревьяДеревья заслуживают отдельного и подробного рассмотрения по двум причинам:• Деревья являются в некотором смысле простейшим классом графов.
Для нихвыполняются многие интересные утверждения, которые не всегда выполняются для графов в общем случае. Применительно к деревьям многие доказательства и рассуждения оказываются намного проще. Выдвигая какие-то гипотезыпри решении задач теории графов, целесообразно сначала их проверять надеревьях.• Деревья являются самым распространённым классом графов, применяемых впрограммировании, причём в самых разных ситуациях. Более половины объёма этой главы посвящено рассмотрению конкретных применений деревьевв программировании.9.1. Свободные деревьяИзучение деревьев целесообразно начать с самых общих определений и установления основных свойств.9.1.1.
ОпределенияГраф без циклов называется ациклическим, или лесом. Связный ациклическийграф называется (свободным) деревом. Таким образом, компонентами связностилеса являются деревья.ЗАМЕЧАНИЕПрилагательное «свободное» употребляется в том случае, когда нужно подчеркнуть отличие деревьев от других объектов, родственных деревьям: ориентированных деревьев,упорядоченных деревьев и т. д.В связном графе G выполняется неравенство q{G) ^ p(G) - 1 (см. 8.1.4). Граф G(пе обязательно связный!), в котором q(G) = p{G) - 1, называется древочисленным.2939.1.
Свободные деревьяВ ациклическом графе G z(G) = 0. Пусть и, v — несмежные вершины графа G,х = (и, v) 0 Е. Если граф G + х имеет ровно один простой цикл, z(G + х) = 1, тограф G (не обязательно ациклический!) называется субциклическим.ЗАМЕЧАНИЕГрафы К $ и К \ и K3UK2 являются древочислепными и субциклическими и в то же времяпе являются пи связными, пи ациклическими.Пример На рис. 9.1 показаны диаграммы всех различных (свободных) деревьев с 5 вершинами, а па рис. 9.2 — диаграммы всех различных (свободных)деревьев с 6 вершинами.Рис. 9.1. Свободные деревья с 5 зершинамиРис. 9.2.
Свободные деревья с 6 зершинами9.1.2. Основные свойства деревьевСледующая теорема устанавливает, что два из 1 етырех свойств — связность,ацикличность, древочисленпость и субцикличиос гь — характеризуют граф какдерево.ТЕОРЕМА Пусть G(V, Е) — граф ср вершинами, qребрами, к компонентами связности и z простыми циклами. Пусть далее х — ребро, соединяющее любую парунесмежных вершин в G. Тогда следующие утверждеь ия эквивалентны:1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
