XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 53
Текст из файла (страница 53)
1. Вычисление для заданного ориентированного графа его машрииы достлизсимосши. Эту задачу будем называть задачей построения шранзишивкого эамыканил ориенширо« 5.6. Задаче о вутвх 327 ванного графа. Такое название связано с тем, что матрицу достижимости можно рассматривать как матрицу транзитивного и рефлексивного замыкания бинарного отношения непосредственной достижияости в ориентированном графе. 2.
Вычисление наименьших расстояний между всеми парами вершин в ориентированном графе. Эту задачу будем называть задачей о крапьчайших расстояниях Задачу о кратчайших расстояниях можно сформулировать так. Пусть задан взвешенный ориентированный граф и пусть иэ вершины о достижима вершина ш. Фиксируем какой-либо путь Я, ведущий из о в ш.
Рассгпоянием от вершины о до вершины ш по пути Я называют сумму меток дуг, входящих в этот путь, а наименьшим — минимальное из расстояний между вершинами о и ш по всем возможным путям. Отметим, что задача о кратчайпих расстояниях не всегда имеет решение. Например, если в ориентированном графе есть петля, метка которой — отрицательное число, то по этой петле можно проходить сколько угодно рвэ и тем самым уменьшать сумму меток дуг пути, включающего эту петлю, до любого наперед заданного значения. 3. Перечисление всех путей между двумя произвольными вершинами. Эту задачу будем называть задачей о перечисяении пртпей.
При ее решении требуетсл для любой заданной пары вершин и и о ориентированного графа получить все пути, для которых и является началом, а о — концом. Все укаэанные задачи (перечисленные в порядке возрастания сложности) можно решить в рамках единого подхода, суть которого сводится к следующему.
Ранее мы ввели понятие взвешенного неориентированного (ориентированного) графа и метки ребер (дуг) определили как числа, поставленные в соответствие ребру (дуге). Обобщим зто понятие для ориентированного графа. Определение $.13. Взвеюиенным (или размеченным) ориентпированнмм графом называют пару И' = (С, ~р), где 328 5. ТЕОРИЯ ГРАФОВ С = (У,Е) — обычный ориентированный граф, а ~р: Е ~ Я.— весовая функция (или функиия размекзки) со значениями в некотором идемиотвектном колукольие К = (Я, +,, О, 1), причем (те Е Е)(у(е) ф 0). Мы будем в этом случае также говорить, что ориентированный граф размечен над идемпотентным полукольцом Я..
Часто полукольцо Я. является эамкнутвык, хотя зто требование необязательно. Будем, однако, везде в этом пункте предполагать, что К вЂ” иолукольио с итиераиией. Пусть вершины ориентированного графа каким-либо образом пронумерованы. Тогда взвешенный ориентированный граф может быть задан матрицей А, элемент которой а; равен значению у((з, у) ) весовой функции на дуге (з, у), если из вершины й ведет дуга в вершину у, или нулю колукольиа в противном случае. Эту матрицу будем называть макзриией метвок дуг. Окззываетсн, что вычисление ишераиии А* матрицы А дает решение всех сформулированных вьппе задач, если для каждой задачи выбирать соответствующее полукольцо.
А именно в случае полукольца В (см. пример 3.2) получаем решение задачи о транзитивном замыкании, в случае полукольца Я,+ (см. пример 3.1) — решение задачи о кратчайших расстояниях'. Будем называть задачу вычисления матрицы А' для ориентированного графа, размеченного над произвольным полукольцом с итерацией, в частности над замкнутым полукольцом, общей задачей о кукьяк во взвешенных ориентированных графах.
В такой общности подхода, когда множество, казалось бы, не связанных друг с другом задач решается единым алгоритмом, „настраиваемым" на разные задачи выбором соответствующего идемпотентного полукольца (т.е. разных областей значений весовой функции), состоит несомненное преимущество *О методе решения третьей нз сформуянрованньпс выше задач см. задачу 7.36.
329 5.6. Задачв о путях абстрактно-алгебраического подхода к решению таких задач на графах. Рассмотрим теперь решение общей задачи о путях для провзвольного замкнутого полукольца К. Мешка путин, ведущего иэ вершины гц в вершину е, есть произведение в полукольце К меток входящих в путь дуг в порядке их следования (для пути ненулевой длины) и есть 1 (единица полукольца К) для пути нулевой длины. Стпоимостпь прохождения из вершины гч в вершину о. (или между 1-й и у-й вершинами) — это сумма в полукольце Я, меток всех путей, ведущих иэ вершины и; в вершину и .
Заметим, что сумма, определяющал стоимость прохождения, вообще говоря, есть бесконечнал сумма замкнутого полукольца, т.е. тпочнал верхнлл грань соответствующей последовашельностпи меток. Это связано с тем, что множество всех путей, ведущвх из одной вершины графа в другую, в общем случае бесконечно (но, как можно доказать, не более чем счетно). Аналогично можно определить стоимость прохождения из вершины в вершину по какому-либо множеству путей.
Отме. тим, что если стоимость прохождения между парой вершин по какому-либо множеству путей равна О, то это означает, что не существует пути, принадлежащего данному множеству путей, ведущего из первой вершины рассматриваемой пары во вторую вершину. Матрица меток дуг является элементом полукольца мап1риц над полукольцом Я,. В этом полукольце определены операции сложения и умножения матриц, а также возведение матрицы в неотрицательную степень. Докажем следующее утверждение.
Лемма 5.1. Элемент а; матрицы А, 1 ) О, равен стоимо- (О сти прохождения из вершины сч в вершину о по всем путям длины 1. ч Доказательство проведем индукцией по 1. При 1 = О утверждение очевидно, так как Ае = Е, где Š— единичная матрица, ЗЗО 5. ТЕОРИЯ ГРАФОВ которол будет матрицей стоимости прохождения по всем путям длины О. При 1 = 1 утверждение также очевидно. Далее, я=1 Согласно предположению индукции, элемент а, равен стои- (1-1) мости прохождения из вершины е; в вершину ц, по всем путям длины1 — 1. Множество всех путей длины1из вершины е; в вершину о~, проходящих через фиксированную Й-ю вершину так, что вершина оь связана дугой с вершиной су (оь -+ е,) образуется путем присоединения дуги (еь, е ) к каждому из путей, ведущих из и1 в еь и имеющих длину 1 — 1.
Тогда видно, что написанное вьппе вырао, о~ о1 жение для элемента а;. дает стоимость (1) прохождения из вершины е; в вершину е Рис. 5.26 по всем путям длины 1 (рис. 5.26). ~ Так как стоимость прохождения между парой вершин (е;, о ) равна сумме меток всех путей, ведущих из первой вершины во вторую, а указанную сумму можно можно получить, суммируя последовательно метки путей длины О, длины 1, длины 2 и т.д., то матрица стоимостей взвешенного ориентированного графа с учетом доказанной леммы 5.1 может быть представлена в виде Ао+А1+Аз+ +Аз+ ~~1 Аи А я>о До сих пор мы рассматривали матрицы над замкнутым полукольцом. Однако, если элементы матрицы А принадлежат некоторому полукольцу с итерацией, из теоремы 3.9 следует, что и все элементы матрицы стоимостей С = А' останутся в этом же полукольце. Таким образом, полученные результаты можно перенести на произвольное полукольцо с итерацией.
331 5.6. Задача о путях Теорема 5.4. Матрица стоимостей ориентированного графа С, размеченного над полукольцом с итерацией Я, (в частности, над замкнутым полукольцом), равна итерации матрицы А меток дуг ориентированного графа С. ф Для вычисления С = А' достаточно решить (т.е. найти наименьшее решение) в Я. при всех у = 1, п систему уравнений где е1 Е Я," — у-й единичный вектор, т.е.
вектор, все элементы которого, кроме у-го, равны О, а у-й равен единице полукольца Я,. Наименьшее решение имеет вид С = А'е. (см. 3.3). Тогда столбец с = А'е есть у-й столбец матрицы А". Такой метод вычисления матрицы А' аналогичен известному иэ линейной алгебры методу элементарных преобразований при вычислении обратной матрицы. Выясним теперь смысл матрицы стоимостей С = А" для полуколец В и Я.+. В первом иэ этих полуколец метка отдельного пути всегда равна 1 (так как метка дуги в размеченном над полукольцом графе не может, согласно определению, быть нулем полукольца).
Следовательно, стоимость су — — 1, если существует хотя бы один путь иэ 1-й вершины в у-ю, и с; = О, если иначе. Другими словами, для полукольца В матрица стоимостей совпадает с матрицей достижимости ориентированного графа. В полукольце Я+ метка пути — это арифметическая сумма меток его дуг, так как умножение в К+ — зто обычное арифметическое сложение. Поскольку сложение в Я+ — это взятие наименьшего из слагаемых, то стоимость с; — это наименьшая иэ меток пути среди всех путей, ведущих из 1-й вершины в у-ю, т.е.
это и есть наименьшая длина пути между указанными вершинами. Таким образом, в полукольце Я+ матрица стоимостей является матрицей кратчаишвх расстояний, т.е. наименьших длин путей между всеми парами вершин ориентированного графа. 332 5. ТЕОРИЯ ГРАФОВ Пример 5.9. Рассмотрим граф, изображенный на рис. 5.27, и решим для него задачу вычисления матрицы достижимости. На числовые метки дуг внимания пока не обращаем, считая, что ориентированный граф размечен над г о полукольцом В и метка каждои дуги равна 1, т.е.
ориентированный граф задан матри- 3 цей Рис. 6.27 Запишем систему уравнений в полукольце 8 для определения первого столбца матрицы А'. Отметим, что часто нулевые слагаемые не записывают, как и в системах уравнений в поле действительных чисел. Воспользуемся нетодо,н последовательного исключения неизвестных (см. 3.3). Поскольку в правой части первого уравнения нет переменной хы можно исключить эту переменную вз системы, подставив в остальные уравнения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
