Главное меню

Вход на сайт

Кто на сайте?

Сейчас один гость и ни одного зарегистрированного пользователя на сайте

Дан исходный граф G = (X, V) (рис. 1). Построить порождённый подграф G' = (X', V'), который получается из исходного после удаления указанных вершин и инцидентных им ребер. Найти в G' кратчайший остов.
Вершина, которую необходимо удалить - Х8, Х9

Image

Решение

Image

Начиная с произвольной вершины (например {X1}). Находим ребро минимального веса (X1, X7) и включим его в остов. Теперь из вершин { X1, X7} находим инцидентное им ребро минимального веса, соединяющего { X1, X7} с “невключенной” ещё вершиной. Это будет (X7, X2) или (X7, X6). Получим множество { , X2, X7}. Просматриваем далее, выбирая ребра с минимальным весом и включая новые вершины, пока все они не будут включены в список.
Вес кратчайшего остова равен сумме всех использованных ребер. В нашем случае:
Image

У Вас недостаточно прав для добавления комментариев.
Вам необходимо зарегистрироваться на сайте