Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
Другие темы раздела
Алгоритмы Суффиксный автомат 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. НО, обратите внимание на термин главная подматрица.... подробнее
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
04.06.2013, 10:28 0

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

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

Ответ

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

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

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

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

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

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

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

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