Основы дискретной математики В.А. Осипова (552659), страница 21
Текст из файла (страница 21)
Заменим в матрице смежности все недиагональные нулевые элементы символом оо. Полученную матрицу обозначим че- Р(о) (ф) в 2, Вычислим последовательность матриц Р(~) = Ц (О 1 = 1, 2, ..., и порядка и, элементы которых определяются по следующей итерационной формуле: Обосновать этот алгоритм можно с помощью рассуждений, приведенных при доказательстве утверждения 4.3, показав, что а1," равен длине кратчайшей простой цепи, соединяющей (О вершизйу и; с и( и проходящей лишь через вершины множества 1ип иэ, ..., ц), если такая цепь существует, и д, = оо в (О противном случае.
В п. 4.1 были определены понятия односторонней и сильной связности для ориентированного графа. Пусть С =< $; Г )— граф с множеством вершин»т = (им и2, ..., иа). Квадратная матрица Т = ~(Ц )) порядка и, у которой 1, если вершина о; достижима из цн ( О, в противном случае называется матрицей односторонней связности (достижимости). Квадратная матрица Я = (~з, (( порядка и, у которой 1, если вершина и достижима из о; и з; = и достижима из и;, 3 1 ч О, в противном случае называется матрицей сильной связности.
Используя алгоритм Уоршелла можно определить матрицы Т и Я односторонней и сильной связности для ориентированного графа С. Пусть А — его матрица смежности. Тогда Т = Я("), Я = = Т3еТ~, где через «2» обозначена операция транспонирования матрицы. Матрицы связности дают ответ на вопрос: существует ли путь (цепь) из одной вершины графа в другую. Ответ на вопрос как определить такой путь рассматривается в следующем пункте. Задачи и упражнения 1. Найти матрицу смежности и матрицу инциденций для графов: 118 Глава 4.
ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ 2. Изобразить графы, заданные матрицей смежности А и матрицей инциденций В А= 3. Найти матрицу связности для графа, заданного матрицей смежности 01101 00111 А= 1 0 0 1 О 10000 00000 4. Найти матрицу достижимости и сильной связности графов, заданных матрицей смежности 0 1 1 1 0000 О 1 О 0110 0 1 1 0 0101 0000'0000 0101'1101 110 0 0100 5.
Доказать, что в графе не существует контуров тогда и только тогда, когда начиная с некоторого й А" = О, где А— матрица смежности графа б. Определить, имеют ли контуры графы с матрицами смежности, приведенными в упражнении 4. 7. Доказать, что если  — матрица инциденций ориентированного графа, то его матрица смежности получится из ВВ~ путем замены всех элементов на диагонали нулями. 4.3. Поиск путей в графе 4.3.1. Алгоритмы нахождения путей и экстремальных путей в графе. Примеры прикладных задач Для данного графа С и двух его вершин а и 6 можно поставить следующие задачи: 10111 00110 1 0 0 1 О,В= 11010 00101 — 1 0 0 0 1 — 1 0 — 1 0 О 0 0 — 1 1 1 — 1 0 — 1 0 0 0 0 — 1 0 0 0 О 1 1 0 Π— 1 — 1 О 1 0 0 1 0 0 4.3. Поиск путей в графе Задача 1.
Найти путь (цепь), ведущий из а в 6. Задача 2. Найти кратчайший путь (цепь), ведущий из а в 6. К решению Задачи 1 для неориентированного графа сводится, например, решение известной задачи о поиске выхода из лабиринта: путешественник, находящейся в а, ищет выход из лабиринта Ь, двигаясь но коридорам. Выход из лабиринта — это цепь, ведущая из вершины а в вершину 6 в графе, где множество вершин — множество перекрестков лабиринта, а у е Гп, когда перекрестки и и у непосредственно соединены коридором.
Опишем алгоритм для решения Задачи 1 для неориентированного графа С =< г', Я >. Алгоритм 4.3. 1. Идем из вершины а по произвольной цепи, помечая каждый раз ребра, которые мы прошли, до тех пор, пока не попадем в вершину аь все ребра инцидентные которой уже помечены. Если по пути встретилась вершина 6, то задача решена, если нет, то переходим к следующему шагу. 2.
Возвращаемся из вершины а1 в первую из возможных вершин, у которой помечены не все инцидентные ей ребра. При этом ребра, пройденные дважды, помечаются еще раз. Из этой вершины опять идем по произвольной цепи с непомеченными ребрами, действуя как в шаге 1.
Действуя таким образом, мы через конечное число шагов достигнем верпзины 6. При этом цепь из а в Ь будет состоять из ребер, помеченных по одному разу. Пример 4.7. Применим алгоритм 4.3 к графу, изображенному на рис. 4.7 для поиска цепи из вершины а в вершину 6. Один из возможных вариантов движения из вершины а соответствует цепи а, пь пз. Затем возвращаемся в вершину пь помечая при этом ребро (пп пз) дважды. Далее идем по цепи гп пз, п4, ез и возвращаемся в вершину пз. Продолжаем движение по цепи ез, ет, ез, пз.
Единственная возможная вершина,, у которой помечены не все инцидентные ей ребра — пь Возвращаемся в нее и переходим в вершину 6. Цепь (а, пь пз, пз, пн 6), состоящая из ребер помеченных один раз, и будет цепью из вершины а в 6. Опишем алгоритм решения Задачи 2 для ориентированного графа С =< и', Г >. Алгоритм 4.4.
(алгоритм афронта волныа): 1. Пометим вершину и индексом О. 2. Все вершины, принадлежащие образу вершины а, помечаем индексом 1 и множество этих вершин обозначаем И 1(а). 120 121 4.3. поиск путей в графе Рис, 499 Рис. 4.7. Рис. 4.8. Рис. 4ЛО.
01 ь2 'пЗ 'п4 'сь со 2 9 со 7 оо со оо со 3 оо 9 оо со со со оо 1 со оо оо со 3 1 со с1 Ю2 из п« св ) Ц-, если <и;,сд>еГ, ) со, в противном случае. Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ 3. Далее действуем по правилу: индексом й помечаем все те непомеченные вершины, которые принадлежат образам вершин, помеченных индексом и — 1. Множество таких вершин обозначаем И'ь(а). Если Ь ф И'ь(а), й = 1, 2, ..., и — 1, то вершина Ь не достижима из вершины а. Если для некоторого й, 1 < й < п — 1, Ь е е И'ь(а), то существует путь из а в Ь длины й и это путь наименьшей длины.
Последовательность вершин а, юм юз, ..., юь м Ь, ГДЕ Ю» 1 Е И"» 1(а) ПГ (Ь), юй 2 Е Ить 2(а) ПГ (юь — 1), ю1 Е И'г(а) П Г 1(ю2) и составляет этот путь. Заметим, что множество вертпин Ить(а) в алгоритме 4.4, называют «фронтом волны» Й-го уровня. Пример 4.8. Пользуясь алгоритмом 4.4 найдем кратчайший путь из вершины п1 в вершину п« в графе, изображенном на рис. 4.8. Здесь И'"1(91) = (пз), И'2(с1) = (с2», Из(с1 ) = (пз), И'4(с1) = (94, ьв), Следовательно, путь (пы св, сз, пз, с«) имеет наименыпую длину, равную 4. На рис.
4.9 показан «фронт волны» для данного примера. Нагруа~сенныл«гра92ол«назовем такой ориентированный граф С =< К Г >, каждой дуге которого поставлено в соответствие неотрицательное число Цд, называемое весом или длиной дуги. Нагруженный граф можно задать матрицей весов. Магарицей весов (длин дуг) нагруженного графа С с множеством вершин см п2, ..., с„называется квадратная матрица С = ))~ '9 порядка н у которой Весом (длиной) пути в нагруженном графе назовем сумму весов (длин) его дуг. Путь с наименьшей (наибольшей) суммой весов (длин) дуг называется минимальным (максимальным). Пример 4.9. Вес (длина) пути (иы с2, пз) в графе, изображенном на рис. 4.10 равен 5.
Матрица весов имеет вид: Рассмотрим примеры прикладных задач, сводящихся к поиску минимальных и максимальных путей в графе. 4.3. Певек путей в графе 122 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ 123 Пример 4.10. Различные организации п1, пз, ..., Си обмениваются некоторой информацией (при этом каналы связи могут быть направленными).
Если между организациями пз и пз возможен непосредственный обмен информацией, то затраты на него составляют Цз рублей. Возможен ли обмен информацией между двумя определенными организациями? Если возможен, то как осуществить этот обмен с минимальными затратами? Рассмотрим граф, вершинам которого соответствуют организа- ЦИИ П1, из, ..., Пи, а ДУГаМ вЂ” ПаРЫ ОРГаНИЗаЦИй < ЕИ Е > МЕжду которыми равным возможен обмен информацией. Положим вес дуги < и;, п > равным (з . Тогда минимальный путь между вершинами в этом графе соответствует обмену с минимальными затратами.
Рассмотрим проект, состоящий из набора операций (работ). Технологическая зависимость между операциями задается в ви- ДЕ ГРафа, ВЕРШИНаМ КОТОРОГО П1, П2, ..., Ьи СООтВЕтСтВУЮт МО- менты последовательного выполнения операций, а дугам — операции. Для казКЛой операции < ьи о > задана ее продолжительность 111. Тогда продолжительность выполнения проекта определяется величиной пути максимальной длины от вершины п1 до пи (критический путь). Задача определения продолжительности проекта является одной из задач календарно-сетевого планирования. Итак, наряду с Задачами 1 и 2 возникает Задача 3. В нагруженном графе найти минимальный (максимальный) путь из вершины а в 6.
Найти минимальный путь в нагруженном графе С позволяет алгоритм Данцига. Опишем его для случая, когда ищется минимальный путь из вершины п1 в произвольную вершину пь Алгоритм 4.5. Каждой вершине и; на й-м шаге приписы(й) ваем индекс Л, по следующему правилу: (о) (о) 1. Положим Л, = со для всех вершин, кроме п1, Л( = О. 2. Пусть Л, ) найдены. Тогда Л, вычисляются по фор(й) (й+1) мулам Л, = ппп (Л( +с;ч) для всех вершин, кроме п1, (й+1) * . (й) 1~~(и Л(+) =О. 1 3. Полагаем й = й+ 1.
Если )е = п — 1, процесс заканчивается, иначе переходим к п. 2. В результате работы алгоритма формируется таблица индек(й) (й) сов Л( . При этом Л( ) определяет вес (длину) минимального пути из первой вершины в г-ю, содержащего не более Й дуг. Последовательность вершин п1 = ои, ..., пш, пп = и; образующая путь минимального веса из с1 в пе получается 1ю следующему правилу: последняя вершина пути пз = п11, .вершина пзз предшествует вершине п11, если выполнено соотношение (и — 1) (и — 1) Л, = Л,2 + с1211, вершина пзз предшествует вершине пзз, (и-1) (и-1) если Лгз — — Лгз + С1212 и т, д., пока не выполнится пи = п1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
