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 |
Ответы с готовыми решениями:
5
Какое наименьшее количество ребер нужно добавить к графу, чтобы получился граф, имеющий Эйлеров цикл
Не могу добавить графу в таблицу Workbench Применим ли к данному графу отношений алгоритм топологической сортировки? |
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 |
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 |
Добавить в таблицу графу с общими суммами по каждому виду товара Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |