Блог пользователя ardmn

Построение остовных деревьев
Автор ardmn, 14 лет назад, По-русски
Нужно по заданному графу построить все возможные остовные деревья . Подскажите как это сделать (алгоритм) или подскажите где это посмотреть.
Спасибо !
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А граф взвешенный или нет ?
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Перебор. На каждом уровне находим первое ребро, которое можно либо добавить либо убрать, фиксируем его и углубляемся в переборе. Насколько мне помнится, что-то подобное было описано в Окулове ( зелёненьком вроде ).
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Описание одного возможного решения есть в книге Кристофидеса.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А это случаем не NP задача?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Что такое "NP задача" в таком контексте? Вы явно что-то путаете в терминологии. Тут надо перечислить все остовные деревья, разумно предположить, что требуется алгоритм, работающий за O(размер ответа) * poly(размер графа). Эта задача естественным образом решается (например, как написали выше, упорядочим рёбра и будем последовательно перебирать, берем/не берём текущее ребро в ответ, проверяя на каждом шаге, достраивается ли текущая конструкция до какого-нибудь остовного дерева ещё не перебранными рёбрами).
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Всего будет n^(n-2) остовных деревьев.Если граф разрежённый ,то будет выгоднее по времени рекурсивно удалять ребро ,которое не является мостом,пока не останется n-1 ребро.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Матричная теорема Кирхгофа. Нахождение количества остовных деревьев за O (N3)
→ Ответить