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

Ответ 1

Позвольте называть конечную точку, найденную первой BFS x. Важнейшим шагом является доказательство того, что x, найденный на этом первом шаге, всегда "работает", т.е. Что он всегда находится на одном конце самого длинного пути. (Заметим, что в общем случае может быть более одного одинаково длинного пути.) Если мы сможем установить это, просто увидеть, что BFS, внедренная в x, найдет некоторое node, насколько это возможно, из x, что поэтому должно быть общий длинный путь.

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

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

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

[EDIT 2] Возвращаясь к этому позже, теперь мне кажется, что два случая, которые необходимо учитывать: (i) путь uv пересекает путь от корня до x ( на некоторой вершине y, не обязательно на старшей точке uv пути h); и (ii) это не так. Нам все еще нужно h для доказательства каждого случая.

Ответ 2

Я собираюсь выработать подсказку 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 принадлежит максимально удаленной паре.

Ответ 3

Вот альтернативный способ взглянуть на это:

Предположим, что G= (V, E) - непустое конечное дерево с множеством вершин V и edge E.

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

• Пусть count = 0. Пусть все ребра в E изначально будут неокрашенными. Пусть C изначально будет V.
• Рассмотрим подмножество V ' V, содержащее все вершины с ровно одним неокрашенным ребром:
  • если V 'пуст, тогда пусть d = count * 2 и остановится.
  • если V "содержит ровно два элемента, а затем цвет их взаимного (неокрашенного) края зеленого цвета, пусть d = count * 2 + 1 и остановится.
  • в противном случае V "содержит не менее трех вершин; действуйте следующим образом:
• Приращение на единицу.
• Удалите все вершины из C, которые не имеют неокрашенных ребер.
• Для каждой вершины в V с двумя или более неокрашенными краями перекрасьте каждый из своих зеленых краев красным цветом (некоторые вершины могут иметь нуль таких ребер).
• Для каждой вершины в V 'окрашивайте ее неокрашенным краем зеленый цвет.
• Вернитесь к шагу (2).

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

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

• этот алгоритм всегда заканчивается в заданных условиях, оставляя каждый край G цветным или красным или зеленым, и оставляя C одним или двумя элементами.
• при завершении алгоритма, d - диаметр G, измеренный по краям.
• Для вершины v в V простейшие пути максимальной длины в G, начинающиеся с v, являются точно такими, которые содержат все вершины центра, заканчиваются на лист и пересекать только зеленые края между центром и дальним концом. Они идут от v, через центр, к одному из листьев, наиболее удаленных от центра.

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

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

Ответ 4

1: procedureTreeDiameter (Т)

2: выбрать произвольную вершину v, где v∈V

3: u = BFS (T, v)

4: t = BFS (T, u)

5: обратное расстояние (u, t)

Результат: Сложность = O (| V |)