PP_s_way (Семинары)

Семинар 13. ЗАДАЧА О ПУТЯХВО ВЗВЕШЕННЫХ ГРАФАХВзвешенные графыОпределение 13.1. Взвешенным (или размеченным)орграфом называют пару W = (G, ϕ), гдеG = (V, E) — обычный орграф,ϕ : E → R — весовая функция (или функция разметки)со значениями в некотором полукольцеR = (R, +, ·, 0, 1)причем (∀e ∈ E)(ϕ(e) 6= 0) .Будем говорить, что орграф размечен над полукольцом R .1СЕМИНАР 13. ЗАДАЧА О ПУТЯХ2Пусть в орграфе фиксирована некоторая нумерация его вершин.Тогда взвешенный орграф может быть задан матрицей A следующего вида:½ϕ((i, j)), если i → j,aij =0, иначе.Эту матрицу будем называть матрицей меток дуг.СЕМИНАР 13.

ЗАДАЧА О ПУТЯХ3Решение общей задачи о путях для произвольногозамкнутого полукольца R .Определение 13.2. Метка пути, ведущего из вершины vi ввершину vj , есть произведение в полукольце R меток входящихв путь дуг в порядке их следования (для пути ненулевой длины) иесть 1 (единица полукольца R ) для пути нулевой длины.Определение 13.3. Стоимость прохождения из вершиныvi в вершину vj (или между i -ой и j -ой вершинами) — это сумма вполукольце R меток всех путей, ведущих из вершины vi в вершинуvj .Сумма, определяющая стоимость прохождения, есть бесконечная”сумма“ в замкнутом полукольце, т.е.

точная верхняя грань соответствующей последовательности меток, так как множество всехпутей, ведущих из одной вершины графа в другую, конечно илисчетно.СЕМИНАР 13. ЗАДАЧА О ПУТЯХ4Среди задач анализа орграфов весьма важными следующие задачи.1) Вычисление для заданного орграфа его матрицы достижимости.2) Вычисление наименьших расстояний между всеми парамивершин в орграфе, где каждой дуге орграфа сопоставлена числоваяметка — расстояние между вершинами, соединяемыми этой дугой.Эту задачу будем называть задачей о кратчайших расстояниях.Вычисление итерации A∗ матрицы A дает решение всех сформулированных выше задач, если для каждой задачи выбирать соответствующее полукольцо.СЕМИНАР 13.

ЗАДАЧА О ПУТЯХ5Теорема 13.1. Матрица стоимостей C орграфа G , размеченного над полукольцом с итерацией R (в частности, над замкнутымполукольцом), равна итерации матрицы A меток дуг, задающейорграф G .Для вычисления C = A∗ можно решить в R при всех j = 1, . . . , nсистему уравнений видаξ = Aξ + εj ,где εj ∈ Rn — j -ый единичный вектор, т.е. вектор, все элементыкоторого, кроме j -ого, равны 0, а j -ый равен 1 полукольца R .ξ = A∗εjесть j -й столбец матрицы A∗ .СЕМИНАР 13.

ЗАДАЧА О ПУТЯХ6Cмысл матрицы стоимостей C = A∗ для полуколец Bи R+В полукольце B метка отдельного пути всегда равна 1 (таккак метка дуги в размеченном над полукольцом графе не может,согласно определению, быть нулем полукольца).Следовательно, стоимость cij = 1, если существует хотя бы одинпуть из i -ой вершины в j -ую, и cij = 0 иначе.Другими словами, для полукольца B матрица стоимостей совпадает с матрицей достижимости орграфа.СЕМИНАР 13. ЗАДАЧА О ПУТЯХ7В полукольце R+ метка пути — это арифметическая сумма метокего дуг, так как умножение в R+ — это обычное арифметическоесложение.Поскольку сложение в R+ — это взятие наименьшего из слагаемых, то стоимость cij — это наименьшая из меток пути среди всехпутей, ведущих из i -ой вершины в j -ую, т.е.

это и есть наименьшаядлина пути между указанными вершинами.Таким образом, в полукольце R+ матрица стоимостей являетсяматрицей кратчайших расстояний, т.е. наименьших длин путеймежду всеми парами вершин орграфа.СЕМИНАР 13. ЗАДАЧА О ПУТЯХ8Задачи13.1. Для заданных графов решить задачу транзитивного замыкания (в полукольце B ) и задачу вычисления кратчайших расстояний (в полукольце R+ ) для графов, заданных списком дуг с весами.Каждый элемент списка имеет вид (vi, vj , (вес)) :(а) (1, 2, 8) , (1, 1, 2) , (1, 3, 5) , (2, 1, 3) , (3, 2, 2) ;(б) (1, 2, 2) , (1, 4, 10) , (2, 3, 3) , (3, 5, 4) , (5, 4, 5) , (2, 4, 7) , (4, 3, 6) ;(в) (1,2,10) , (1,4,5) , (2,1,6) , (2,3,7) , (2,4,2) , (2,5,9) , (3,3,8) ,(3,4,10) , (4,3,5) , (4,5,4) , (4,2,7) , (5,1,8) , (5,3,4) ;(г) (1, 2, 2) , (1, 3, 3) , (2, 3, 6) , (3, 2, 5) , (2, 4, 6) , (3, 5, 2) , (4, 5, 3) ,(5, 4, 4) , (6,4, 1) , (7,5, 5) , (6, 7, 4) , (7, 2,6) ;(д) (1, 2, 1) , (2, 3, 3) , (3, 4, 4) , (5, 4, 5) , (5, 6, 1) , (6, 1, 1) , (1, 7, 2) ,(2, 7, 1) , (4,7, 1) , (7,3, 2) , (7, 5, 1) , (7, 6,1) ;СЕМИНАР 13.

ЗАДАЧА О ПУТЯХ913.2. Не используя интерпретации на графах, доказать, что дляnXлюбой матрицы A n × n над полукольцом B A∗ =Ak .k=0Рассмотреть A как матрицу смежности некоторого неориентированного графа и дать интерпретацию на графах матриц A2, A3,Ak .Рассмотреть эти матрицы как матрицы бинарных отношений наn -элементном множестве и установить, как связаны эти бинарныеотношения с бинарным отношением, задаваемым матрицей A?.