Нужно по заданному графу построить все возможные остовные деревья . Подскажите как это сделать (алгоритм) или подскажите где это посмотреть.
Спасибо !
nk.karpov
|
13 лет назад,
#
|
0
А граф взвешенный или нет ?
→
Ответить
|
ardmn
|
13 лет назад,
#
^
|
+1
думаю нет, а есть разница?
→
Ответить
|
maksay
|
13 лет назад,
#
|
0
Перебор. На каждом уровне находим первое ребро, которое можно либо добавить либо убрать, фиксируем его и углубляемся в переборе. Насколько мне помнится, что-то подобное было описано в Окулове ( зелёненьком вроде ).
→
Ответить
|
it4.kp
|
13 лет назад,
#
|
0
Описание одного возможного решения есть в книге Кристофидеса.
→
Ответить
|
Fefer_Ivan
|
13 лет назад,
#
|
0
А это случаем не NP задача?
→
Ответить
|
ilyakor
|
13 лет назад,
#
^
|
0
Что такое "NP задача" в таком контексте? Вы явно что-то путаете в терминологии. Тут надо перечислить все остовные деревья, разумно предположить, что требуется алгоритм, работающий за O(размер ответа) * poly(размер графа). Эта задача естественным образом решается (например, как написали выше, упорядочим рёбра и будем последовательно перебирать, берем/не берём текущее ребро в ответ, проверяя на каждом шаге, достраивается ли текущая конструкция до какого-нибудь остовного дерева ещё не перебранными рёбрами).
→
Ответить
|
Rubanenko
|
13 лет назад,
#
|
0
Всего будет n^(n-2) остовных деревьев.Если граф разрежённый ,то будет выгоднее по времени рекурсивно удалять ребро ,которое не является мостом,пока не останется n-1 ребро.
→
Ответить
|
dyussenaliyev
|
13 лет назад,
#
|
0
Матричная теорема Кирхгофа. Нахождение количества остовных деревьев за O (N3)
→
Ответить
|