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

Поиск диаметра и радиуса в дереве
Автор proVIDec, 11 лет назад, По-русски

Собственно сабж. С ужасом обнаружил, что не могу найти необходимую информацию в сети. На запросы типа "Радиус дерева" выдает сайты лесничих сообществ и т.п.. А если к запросу добавить слово граф, то про дерево в результатах ничего нет. В общем беда какая-то. Кто-нибудь подскажите пожалуйста материал по теме.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Например, здесь есть какое-то обсуждение.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ну про эту темку я знал, но все равно спасибо, возможно ей и придется довольствоваться. Вообще странно, что по такой общей задаче мало что есть в интернете.

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      По-моему, та тема полностью покрывает мои знания на тему диаметра, радиуса и центра дерева. Собственно, кроме "как их искать" я никакой полезной информации про них придумать не могу.

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Помнится, что у дерева не более двух вершин могут являться центрами. Думаю, какие-нибудь еще любопытные факты можно обнаружить.

        → Ответить
»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Не совсем понял вопрос. Вроде в заголовке темы про диаметр/радиус в теле — только про радиус.

На всякий случай напишу, что знаю: диаметр (максимальное расстояние в дереве во множестве всех кратчайших путей между вершинами) находится за два dfs. Из любого листа запускаем первый обход. Самая удаленная вершина в этом обходе принадлежит диаметру. Остается запустить обход из нее и получить вторую вершину диаметра. На algolist.ru кажется было обсуждение. Про радиус было бы самому интересно прочитать.

UPD: не до конца прочитал тему по вышеуказанной ссылке, там есть пояснение про диаметр, про радиус что-то сильно заминусован вроде бы правильный пост

→ Ответить