28. Взвешенный граф. Задача о минимальном остовном дереве в связном взвешенном графе. Алгоритм Краскала

Взвешенный граф — это граф, для которого задано отображение w:ER₀, где R₀ — множество действительных неотрицательных чисел.

Минимальное остовное дерево в связанном, взвешенном, неориентированном графе — остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.

Алгоритм Краскала Дан

1.Вначале текущее множество рёбер устанавливается пустым . 2. Формулируем - мн-ва вершин, соотв. Компонентам исходного остовного класса. 3. Сортируем E по возрастанию весов, формируем очередь Q. 4.Если содержит больше 1 эл-та и Q не пуста=> шаг 5 иначе 7. 5. Извлекаем из Q ребро l. Если концы l различным , переходим на шаг 6, иначе отбрасываем ребро и в 4. 6.Объединяем мн-ва вершин удаляем , добавляем в ребро l в H, на шаг 4. 7.Множество H-мн-во ребер полученного дерева.

29. Задача о достижимости в ориентированном графе. Связь матрицы достижимости и матрицы смежности.

Матрица смежности вершин — это квадратная матрица B n-го порядка, элементы которой определяются для неориентированного графа следующим образом:

Замечание: в k-ой строке матрицы орграфа количество единиц равно полустепени исхода вершины , а количество единиц в k-ом столбце — полустепени захода . Для неорграфа матрица смежности вершин симметрична.

Матрица достижимости — это матрица C размера |V||V|, каждый элемент которой

Согласно определению достижимости, элементы . Матрица достижимости несет очень важную информацию о графе. C для любой пары индексов даёт номера вершин, образующих бикомпоненту, а для любых i, j или даёт номера вершин, образующих компоненту.

Лемма: Элемент матрицы меток дуг равен стоимости прохождения из i в j по всем путям длины l.

Т.к. стоимость прохождения между парой вершин равна сумме меток всех путей, ведущих из первой вершины во вторую, а указанную сумму можно получить, суммируя последовательно метки путей длины 0, длины 1, длины 2 и т.д., то матрица стоимостей взвешенного орграфа может быть представлена в виде . Матрица меток дуг, размеченная над булевым полукольцом — матрица смежности. Решая в систему уравнений при всех , где — j-й единичный вектор, получаем наименьшее решение вида . Тогда столбец есть j-й столбец матрицы достижимости С=A*.

30. Задача о кратчайшем пути в ориентированном взвешенном графе. Связь матрицы матрицы смежности (с весами) и матрицы стоимости кратчайших путей.

Взвешенный орграф — это пара , где — обычный орграф, а — весовая функция со значениями в некотором замкнутом полукольце . Задача о кратчайшем пути — вычисление наименьших расстояний между всеми парами вершин в орграфе (вычисления матрицы стоимостей А^* для взвешенного орграфа, размеченного над произвольным полукольцом с итерацией, в частности над замкнутым полукольцом).

-связь матрицы стоимостей и матрицы достижимости.

(Лемма: Элемент матрицы меток дуг равен стоимости прохождения из i в j по всем путям длины l. )

Решая в полукольце систему уравнений при всех , где — j-й единичный вектор, получаем наименьшее решение вида . Тогда столбец есть j-й столбец матрицы стоимости кратчайших путей С=A*.