PP_s_way (1076811)
Текст из файла
Семинар 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?.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
