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

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

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

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

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

Какое наименьшее количество ребер нужно добавить к графу, чтобы получился граф, имеющий Эйлеров цикл
Какое наименьшее количество ребер нужно добавить к графу K_{3,4} чтобы получился граф, имеющий...

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

Как корректно собрать составить схему по заданному графу
Здравствуйте, не могу понять как составить схему по графу. Номера соответствуют елементам: 1 - 0;...

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

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

5
salam
189 / 170 / 29
Регистрация: 10.07.2012
Сообщений: 796
03.06.2013, 16:08 2
ребро может добавлять к графу новую вершину?
0
Anastasia121192
0 / 0 / 0
Регистрация: 19.03.2013
Сообщений: 10
03.06.2013, 16:33  [ТС] 3
В задаче об этом ничего не сказано, но, мне кажется, без этого не обойтись.
0
salam
189 / 170 / 29
Регистрация: 10.07.2012
Сообщений: 796
03.06.2013, 18:38 4
если за н, то можно реально его перестраивать каждый раз...
0
Igor3D
1229 / 596 / 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
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.06.2013, 13:28

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

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

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


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

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

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