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

@Aquilo · Регистрация: 03.11.2014

Студворк — интернет-сервис помощи студентам

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

Каким алгоритмом возможно решить поставленную задачу?
По возможности с наименьшей вычислительной сложностью.

@salam · 03.11.2014, 14:04

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

@Aquilo · 03.11.2014, 14:11 **[ТС]**

их число измеряеться как d^(d-2)
то есть
d=4 16
d=5 125
...
d=10 10⁸=100 000 000

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

Вот и спросил какие математические алгоритмы есть для решения этой задачи.

@Aquilo 0 / 0 / 0 Регистрация: 03.11.2014 Сообщений: 13
		1
	Алгоритм поиска всех деревьев в графе 03.11.2014, 12:00. Показов 1276. Ответов 2 Метки нет (Все метки) Имеется граф. Необходимо найти множество всех деревьев. Где дерево это минимальная неизбыточная совокупность ребер удовлетворяющая условию связности, при удалении любого ребра из дерева дерево перестает быть связным. Каким алгоритмом возможно решить поставленную задачу? По возможности с наименьшей вычислительной сложностью. 0

@salam 193 / 173 / 30 Регистрация: 10.07.2012 Сообщений: 800
	03.11.2014, 14:04	2
	деревьев может быть экспоненциальное число видимо. если вас интересует поиск всех, то алгоритм в любом случае будет сложности порядка перебора. можно писать самый простой перебор. 0

@Aquilo 0 / 0 / 0 Регистрация: 03.11.2014 Сообщений: 13
	03.11.2014, 14:11 [ТС]	3
	их число измеряеться как d^(d-2) то есть d=4 16 d=5 125 ... d=10 10⁸=100 000 000 Кое какой алгоритм рекурсивного перебора уже придумал, на там ~=20% повторов, не знаю как убрать их (не перебирая каждый вариант с уже полученными). Да и не оптимальный он сильно. Вот и спросил какие математические алгоритмы есть для решения этой задачи. 0

Опции темы