Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
Anastasia121192
0 / 0 / 0
Регистрация: 19.03.2013
Сообщений: 10
1

Есть мин-ое остовое дерево к заданному графу. Нужно добавить к этому графу новое ребро, и предложить алгоритм, который перестроит мин-е остовое дерево

03.06.2013, 13:11. Просмотров 510. Ответов 5
Метки нет (Все метки)

Полный текст задачи: "Предположим, что у нас имеется минимальное остовое дерево Т заданного графа G (c n вершинами и m ребрами) и новое ребро e=(u,v) веса w, которое добавляется к G. Предложите алгоритм сложности О(n), который перестроит дерево Т в минимальное остовое дерево Т' графа G+e".

Я даже не знаю, как к этому подступиться. Может, где-то есть практические примеры или еще что? Помогите пожалуйста.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.06.2013, 13:11
Ответы с готовыми решениями:

Вычислить вероятность состояния системы по заданному графу
Всем привет. Я закончил ВУЗ более 10 лет назад и уже совершенно забыл как это...

Как корректно собрать составить схему по заданному графу
Здравствуйте, не могу понять как составить схему по графу. Номера...

Не могу добавить графу в таблицу Workbench
Поле неактивно, помогите пожалуйста...

Применим ли к данному графу отношений алгоритм топологической сортировки?
Применим ли к данному графу отношений алгоритм топологической сортировки? (см....

По заданному дереву построить новое дерево только из тех элементов данного дерева, которые оканчиваются на 7
Пожалуйста, помогите. Уже весь мозг себе сломала. Т-Т Есть задание - "Напишите...

5
salam
182 / 163 / 29
Регистрация: 10.07.2012
Сообщений: 775
03.06.2013, 16:08 2
ребро может добавлять к графу новую вершину?
0
Anastasia121192
0 / 0 / 0
Регистрация: 19.03.2013
Сообщений: 10
03.06.2013, 16:33  [ТС] 3
В задаче об этом ничего не сказано, но, мне кажется, без этого не обойтись.
0
salam
182 / 163 / 29
Регистрация: 10.07.2012
Сообщений: 775
03.06.2013, 18:38 4
если за н, то можно реально его перестраивать каждый раз...
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
04.06.2013, 10:28 5
...остовное дерево состоит из некоторого подмножества рёбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим рёбрам, и в нём нет циклов, то есть из любой вершины нельзя попасть в саму себя, не пройдя какое-то ребро дважды.
Видимо надо понимать так: если в таком графе "назначили" новое ребро (между 2-мя имеющимися вершинами), и он перестал быть остовным. Надо удалить какое-то число старых ребер чтобы граф опять стал остовным
0
NurlashKO
89 / 89 / 80
Регистрация: 07.10.2012
Сообщений: 145
05.06.2013, 13:28 6
Во первых, пусть мы хотим вставить наше ребро (v, u). Тогда должно удалится какое то ребро лежащее на пути от v до u (по определению остова, есть только один путь). Очевидно что удаляемое ребро должно быть максимального веса. Если вес этого(максимального) ребра меньше веса нашего(добавляемого) ребра то нам не выгодно добавлять ребро. Иначе просто удаляем это(максимальное) ребро и вставляем наше.
Найти это ребро можно обычным ДФС-ом.
Так как количество ребер в остове не превышает N, а точнее оно равно N - 1 то ассимтотика решения будет О(N).
1
05.06.2013, 13:28
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.06.2013, 13:28

Пройти по заданному графу с крайней левой вершины в правую, использовав все рёбра по одному разу
Существует граф, по которому нужно пройти с крайней левой вершины в правую,...

Добавить в таблицу графу с общими суммами по каждому виду товара
Доброго времени суток. Прошу вашей помощи. Задача такова: В текстовом файле в...

Периодически зависает ПК, на короткое время (0.30-1 мин) и отпускает на 2-3 мин.
Имею вот такой конфиг: Операционная система Microsoft Windows 7 Ultimate...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru