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

@Anastasia121192 · Регистрация: 19.03.2013

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

Я даже не знаю, как к этому подступиться. Может, где-то есть практические примеры или еще что? Помогите пожалуйста.

@salam · 03.06.2013, 16:08

ребро может добавлять к графу новую вершину?

@Anastasia121192 · 03.06.2013, 16:33 **[ТС]**

В задаче об этом ничего не сказано, но, мне кажется, без этого не обойтись.

@salam · 03.06.2013, 18:38

если за н, то можно реально его перестраивать каждый раз...

@Igor3D · 04.06.2013, 10:28

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

Видимо надо понимать так: если в таком графе "назначили" новое ребро (между 2-мя имеющимися вершинами), и он перестал быть остовным. Надо удалить какое-то число старых ребер чтобы граф опять стал остовным

@NurlashKO · 05.06.2013, 13:28

Во первых, пусть мы хотим вставить наше ребро (v, u). Тогда должно удалится какое то ребро лежащее на пути от v до u (по определению остова, есть только один путь). Очевидно что удаляемое ребро должно быть максимального веса. Если вес этого(максимального) ребра меньше веса нашего(добавляемого) ребра то нам не выгодно добавлять ребро. Иначе просто удаляем это(максимальное) ребро и вставляем наше.
Найти это ребро можно обычным ДФС-ом.
Так как количество ребер в остове не превышает N, а точнее оно равно N - 1 то ассимтотика решения будет О(N).

@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

@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

Опции темы