Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Aquilo
0 / 0 / 0
Регистрация: 03.11.2014
Сообщений: 9
1

Алгоритм поиска всех деревьев в графе

03.11.2014, 12:00. Просмотров 400. Ответов 2
Метки нет (Все метки)

Имеется граф.
Необходимо найти множество всех деревьев.
Где дерево это минимальная неизбыточная совокупность ребер удовлетворяющая условию связности, при удалении любого ребра из дерева дерево перестает быть связным.

Каким алгоритмом возможно решить поставленную задачу?
По возможности с наименьшей вычислительной сложностью.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.11.2014, 12:00
Ответы с готовыми решениями:

Алгоритм поиска слова в заданном Графе
Доброго времени суток. Может быть кто-то, когда-то писал такой алгоритм, для поиска слова в...

Алгоритм поиска элементарных циклов в неориентированном графе
Необходимо граф разбить на элементарные циклы, то есть такие циклы, которые не имею внутри...

Алгоритм нахождения ВСЕХ ободов в графе
Дан связанный граф (не менее 16 вершин), нужно найти все подграфы, являющиеся ободами. (Обод –...

Реализовать алгоритм А* для поиска оптимального пути из начальной вершины в конечную на графе
Привет Нужно реализовать этот алгоритм для поиска оптимального пути из начальной вершины в...

Алгоритм поиска всех слов
День добрый. Есть такая задача: программа хавает тексты, которые ты ей даешь, берет от туда все...

2
salam
188 / 169 / 29
Регистрация: 10.07.2012
Сообщений: 791
03.11.2014, 14:04 2
деревьев может быть экспоненциальное число видимо. если вас интересует поиск всех, то алгоритм в любом случае будет сложности порядка перебора. можно писать самый простой перебор.
0
Aquilo
0 / 0 / 0
Регистрация: 03.11.2014
Сообщений: 9
03.11.2014, 14:11  [ТС] 3
их число измеряеться как d(d-2)
то есть
d=4 16
d=5 125
...
d=10 108=100 000 000

Кое какой алгоритм рекурсивного перебора уже придумал, на там ~=20% повторов, не знаю как убрать их (не перебирая каждый вариант с уже полученными). Да и не оптимальный он сильно.

Вот и спросил какие математические алгоритмы есть для решения этой задачи.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.11.2014, 14:11

Алгоритм для поиска всех целочисленных делителей числа
Сделать максимально эффективный алгоритм для поиска всех целочисленных делителей числа Описать...

Алгоритм поиска числа всех вершин высоты N в двоичном дереве
Добрый день. Нужно придумать эффективуюю программу(алгоритм) поиска числа всех вершин высоты N в...

Алгоритм оптимального расположения на графе
Дан неориентированый граф. Необходимо вычислить, какие узлы отмечать, так, что бы расстояние до...


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

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

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