КР 3 Графы_11. Построим изображение графа
![]()
|
![]() Построим изображение графа ![]() Видим, что из 6 вершины выходит стрелка только в 6. Значит, нельзя из 6 попасть в 1, например и граф не сильно связный. Далее видим, что из 4 вершины можно попасть во все, и из любой вершины кроме 6 можно попасть в 4 по стрелкам. Из 1,2,4,5 - по дуге, а из 3 по паре дуг ![]() Их матрицы смежности:
И
Изображения компонент сильной связности: ![]() ![]() ![]() Решение: Матрица весов дуг симметрична. То есть граф неориентированный, и можно просто ставить ребра без стрелок вместо двух дуг. Действуем жадным алгоритмом. Выбираем произвольным образом вершину. Пусть это будет ![]() ![]() ![]() Среди всех не взятых еще ребер, которые выходят из ![]() ![]() ![]() Получаем на данном шаге пока подграф ![]() Среди всех невыбранных ребер, с вершинами в выбранных вершинах ищем ребро минимального веса. Это ребро ![]() ![]() Среди всех невыбранных ребер, с вершинами в выбранных вершинах ищем ребро минимального веса. Это ребро ![]() ![]() ![]() Прибавляем, получаем поддерево: ![]() В нём не хватает только 3 вершины. Чтобы не получить цикл для ускорения процесса сразу ищем самое легкое ребро из вершины 3 (потому что на данном этапе остальные вершины уже выбраны и следующее добавленное точно будет из вершины 3). Самое легкое такое ребро это ребро ![]() ![]() Считаем его вес ![]() ![]() Решение: Используем алгоритм Дейкстры. Присваиваем вершинам временные метки из 1 строки таблицы
Рассматриваем первую смежную вершину ![]() По 2 строке таблицы видим, что она смежна с вершинами ![]() ![]() ![]() Считаем сумму расстояния до них и метки до вершины ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]()
Рассматриваем следующую смежную вершину ![]() По 3 строке таблицы видим, что она смежна с вершинами 2,4,5,7( из не рассмотренных). Считаем сумму расстояния до них и метки вершины ![]() ![]() ![]() ![]() ![]()
Рассматриваем следующую смежную вершину ![]() По 4 строке таблицы видим, что она смежна с вершинами 2,3,5,7 Считаем сумму расстояния до них и метки вершины ![]() ![]() ![]() ![]() ![]()
Рассматриваем следующую вершину ну ![]() По 5 строке таблицы видим, что она смежна с вершинами 3,4,6,7 Считаем сумму расстояния до них и метки вершины ![]() ![]() ![]() ![]() ![]() Рассматриваем последнюю вершину ну ![]() По 6 строке таблицы видим, что она смежна с вершинами 2,4,5 Считаем сумму расстояния до них и метки вершины ![]() ![]() ![]() ![]() ![]() ![]() ![]() Не рассматривали ребра, входящие в V1 и выходящие из ![]() ![]() ![]() ![]() Найти максимальный поток и минимальны разрез в транспортной сети: ![]()
Решение: Все ребра идут у нас из вершины с меньшим номером в вершину с большим. Поэтому не будем ставить на них стрелки, и так понятно направление. Изобразим граф нашей транспортной сети: ![]() Источник ![]() ![]() Рассматриваем путь ![]() ![]() ![]() Берем путь ![]() ![]() ![]() Берем путь ![]() ![]() ![]() Берем путь ![]() ![]() ![]() Берем путь ![]() ![]() ![]() Берем путь ![]() ![]() Наконец берем путь ![]() ![]() ![]() Больше нет путей из ![]() ![]() Максимальный поток равен сумме потоков на каждом шаге. ![]() Находим минимальный разрез. Из нашего алгоритма выходит, что это ![]() ![]() ![]() Ответ: максимальный поток равен 27.Он состоит из потоков: 5 по ветке ![]() ![]() ![]() 5 по ветке ![]() ![]() ![]() 1 по ветке ![]() ![]() . ![]() Решение: Граф ![]() ![]() ![]() Добавили ребра 2-1 и 2-3. Ребра 3-1 и 3-2 и так уже были в ![]() ![]() Задаем граф объединения списком ребер: ![]() ![]() ![]() ![]() ![]() ![]() Затем строим матрицу инцидентности. Для этого пронумеруем все ребра графа следующим образом: ![]() В матрице инцидентности будет 4 строки, соответствующих вершинам и 5 столбцов, соответствующих ребрам. В каждом столбце ставим -1 в строке вершины, из которой выходит соответствующее ребро, 1 – в которую входит и ноль в остальных строках. Получаем матрицу инцидентности: ![]() Определяем частичные полустепени исхода и захода вершин (сколько дуг выходит/входит).
Проверка: суммы в строках должны быть равны и равны количеству ребер. ![]() Строим какой-нибудь частичный граф: Для этого просто уберем часть ребер. К примеру, уберем только ребро ![]() ![]() Строим какой-нибудь подграф. Для этого, например, уберем вершину 1 и все ребра, которые в неё заходят или из неё выходят. Получим: ![]() Построим дополнительный орграф к последнему подграфу. Он будет состоять из всех ребер исходного графа, кроме тех, что принадлежат предыдущему подграфу. Получим: ![]() ![]() Решение: Возьмем следующие графы ![]() ![]() ![]() Находим их прямое произведение. В нем будут вершины ![]() Смотрим , какие из них смежны. ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Получаем произведение: ![]() Сумма графов ![]() ![]() |