Доказательство правильности:Алгоритм определения диаметра дерева в теории графов

StackOverflow https://stackoverflow.com//questions/20010472

Вопрос

Чтобы найти диаметр дерева, я могу взять любой узел из дерева, выполнить BFS, чтобы найти узел, который находится дальше всего от него, а затем выполнить BFS на этом узле.Наибольшее расстояние от второго BFS даст диаметр.

Однако я не уверен, как это доказать?Я пробовал использовать индукцию по количеству узлов, но случаев слишком много.

Мы были бы очень признательны за любые идеи...

Это было полезно?

Решение

Давайте назовем конечную точку, найденную первым BFS X. Решающий шаг доказывает, что X нашел на этом первом шаге всегда «работает» - то есть, что он всегда находится на одном конце какого-либо самого длинного пути. (Примечание. самый длинный путь.

HINT: Предположим (к наобою), что между двумя вершинами u и v большей из которых есть ни один из которых не является x.

Соблюдайте, что на уникальном пути между u и v, должно быть несколько самых высоких (ближайших к корне) вершина H. Существует два возможности: либо H - на пути от корня BFS к X, или это не так. Покажите противоречие, показывая, что в обоих случаях путь U-V может быть выполнен, по меньшей мере, как долго, заменяя некоторые сегмент пути в него с помощью пути к X.

[править] На самом деле, его не нужно лечить 2 случая отдельно в конце концов. Но я часто упрощаю сломать конфигурацию в несколько (или даже много) случаев, и относиться к каждому отдельно. Здесь случай, когда h находится на пути от корня BFS до X, легче обрабатывать и дает подсказку для другого случая.

[редактировать 2] Возвращаясь к этому позже, теперь это кажется, что два случая, которые необходимо рассмотреть, являются (i) УФ-путь пересекает путь от корня до X ( При некоторые вершины y не обязательно на высочайшей точке УФ-пути H); и (ii) это не так. Нам все еще нужно h, чтобы доказать каждый случай.

Другие советы

Я собираюсь потренироваться подсказка j_random_hacker'а.Позволь s, t будьте максимально отдаленной парой.Позволь u быть произвольной вершиной.У нас есть схема, подобная

    u
    |
    |
    |
    x
   / \
  /   \
 /     \
s       t ,

где x является соединением s, t, u (т.е.уникальная вершина, лежащая на каждом из трех путей между этими вершинами).

Предположим, что v является вершиной, максимально удаленной от u.Если схема теперь выглядит как

    u
    |
    |
    |
    x   v
   / \ /
  /   *
 /     \
s       t ,

затем

d(s, t) = d(s, x) + d(x, t) <= d(s, x) + d(x, v) = d(s, v),

где неравенство сохраняется, потому что d(u, t) = d(u, x) + d(x, t) и d(u, v) = d(u, x) + d(x, v).Существует симметричный случай, когда v прикрепляется между s и x вместо того, чтобы находиться между x и t.

Другой случай выглядит следующим образом

    u
    |
    *---v
    |
    x
   / \
  /   \
 /     \
s       t .

Сейчас,

d(u, s) <= d(u, v) <= d(u, x) + d(x, v)
d(u, t) <= d(u, v) <= d(u, x) + d(x, v)

d(s, t)  = d(s, x) + d(x, t)
         = d(u, s) + d(u, t) - 2 d(u, x)
        <= 2 d(x, v)

2 d(s, t) <= d(s, t) + 2 d(x, v)
           = d(s, x) + d(x, v) + d(v, x) + d(x, t)
           = d(v, s) + d(v, t),

так max(d(v, s), d(v, t)) >= d(s, t) с помощью усредняющего аргумента, и v принадлежит к максимально удаленной паре.

Вот альтернативный способ посмотреть на него:

Предположим, g = ( v , e ) - непустое, конечное дерево с установленным вершинами V и EDGE SET E .

Рассмотрим следующий алгоритм:

  1. Пусть count = 0. Пусть все края в e изначально будут раскрыты. Пусть c первоначально равно v .
  2. Рассмотрим подмножество v ' v , содержащих все вершины с одним неосвеченным краем:
      .
    • , если v 'пусто, пусть d = count * 2 и останавливайтесь.
    • , если v 'содержит ровно два элемента, затем цвет их взаимного (неочищенного) края зеленого, пусть D = Count * 2 + 1, и остановитесь.
    • в противном случае v 'содержит как минимум три вершины; Выполните следующие действия:
  3. Увеличение Счет на один.
  4. Удалите все вершины от c , которые не имеют распущенных ребер.
  5. для каждой вершины в v с двумя или более неосвещенными краями, повторно раскрась, каждая из его зеленых краев красных (некоторые вершины могут иметь нулевые такие края).
  6. Для каждой вершины в v ', цвет его распущенный край зеленый.
  7. Вернуться к шагу (2).

    8. Это в основном цвета графа из листьев внутрь, маркировка путей с максимальным расстоянием до листа в зеленых и отмеченных тем, что только более короткие расстояния в красном. Между тем, узлы C , центр с коротким максимальным расстоянием до листа свышены до c содержит только один или два узла с наибольшим максимальным расстоянием до листа.

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

      .
    • Этот алгоритм всегда прекращается в условиях, приведенных в условиях, оставляя на каждом краю g цветной красный или зеленый, и оставив c с одним или двумя элементами.
    • при окончании алгоритма, D - это диаметр g , измерен в краях.
    • Учитывая вершину v в v , простые пути максимальной длины в g < / strong> начиная с v - это именно те, которые содержат все вершины центра, прекращают на листе и пересекают только зеленые края между центром и дальней конечной точкой. Они идут от v , через центр, к одному из листьев дальше всего от центра.

    Теперь рассмотрим ваш алгоритм, который может быть более практичным, в свете вышесказанного. Начиная с любой вершины v , есть ровно один простой путь p от этой вершины, заканчиваясь в центре вершины и содержащий все вершины Центр (потому что g это дерево, и если есть две вершины в c , тогда они разделяют край) Отказ Можно показать, что максимальные простые пути в g имеют v как одна конечная точка, имеют форму объединения P с простым путем от центра до листа, проходящего только зеленые края.

    Основная точка для наших целей заключается в том, что входящий край другой конечной точки обязательно зеленый. Поэтому, когда мы выполняем поиск самых длинных путей, начинающих там, у нас есть доступ к тем, которые проходят только зеленые края из листа через (все вершины) центра в другой лист. Это именно простые простые пути максимально длины в G , поэтому мы можем быть уверены, что второй поиск действительно будет раскрыть диаграмму графа.

1:procedureTreeDiameter(T)

2:pick an arbitrary vertex v where v∈V

3:u = BFS ( T, v )

4:t = BFS ( T, u )

5:return distance ( u, t )

Result: Complexity = O(|V|)

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top