Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
Другие темы раздела
Алгоритмы Суффиксный автомат http://www.cyberforum.ru/algorithms/thread888285.html
Разбираюсь в теории, стало непонятно следующее: "Тогда назовём множеством окончаний endpos(t) множество всех позиций в строке s, в которых оканчиваются вхождения строки t."...
Алгоритмы Блок-схема нахождения факториала 3!, 5!, 7! с одним циклом Помогите, пожалуйста, составить блок-схему нахождения факториала 3!, 5!, 7! с одним циклом. http://www.cyberforum.ru/algorithms/thread888113.html
Алгоритм Маркова Алгоритмы
Вот система, для неё нужно написать алгоритм маркова. Не могу разобраться.
Алгоритмы Диплом: сравнительный анализ архитектур Джона Фон Неймана и Фибоначчи (языки C или delphi)
Уважаемые программисты, мне очень нужна помощь по диплому. В нём есть почти все алгоритмы простой арифметики (свёрстки, умножения, перемещения и т.д.), но главного не хватает: помехоустойчивых кодов:...
Алгоритмы Алгоритм нахождения наибольшей общей подстроки http://www.cyberforum.ru/algorithms/thread887584.html
Например, у меня 3 строки: alerroraa marerrordd nierrorasd По какому алгоритму определить error и вынести его?
Алгоритмы Нужно найти наибольшую главную подматрицу, которая состоит только из 1 Дана матрица NxN, симметричная, состоит из 0 и 1, на главной диагонали 1. Нужно найти наибольшую главную подматрицу, которая состоит только из 1. НО, обратите внимание на термин главная подматрица.... подробнее
NurlashKO
89 / 89 / 80
Регистрация: 07.10.2012
Сообщений: 145
05.06.2013, 13:28 0

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

05.06.2013, 13:28. Просмотров 518. Ответов 5
Метки (Все метки)

Ответ

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

Вернуться к обсуждению:
Есть мин-ое остовое дерево к заданному графу. Нужно добавить к этому графу новое ребро, и предложить алгоритм, который перестроит мин-е остовое дерево
1
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.06.2013, 13:28
Готовые ответы и решения:

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

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

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

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

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

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