Алгоритм определения диаметра дерева с использованием BFS / DFS. Почему это работает?

28

Эта ссылка предоставляет алгоритм для определения диаметра ненаправленного дерева с использованием BFS / DFS . Подводя итог:

Запустите BFS на любом узле в графе, помня узел, который вы обнаружили последним. Запустите BFS, вспомнив последний обнаруженный узел v. d (u, v) - диаметр дерева.

Почему это работает?

Страница 2 этого обеспечивает рассуждение, но это сбивает с толку. Я цитирую начальную часть доказательства:

Запустите BFS на любом узле в графе, помня узел, который вы обнаружили последним. Запустите BFS, запомнив последний обнаруженный узел v. d (u, v) - диаметр дерева.

Корректность. Пусть a и b - любые два узла, так что d (a, b) - диаметр дерева. Существует уникальный путь от а до б. Пусть t будет первым узлом на этом пути, обнаруженным BFS. Если пути p1 от s до u и p2 от a до b не имеют общих ребер, то путь от t до u включает s. Так

d(t,u)d(s,u)

d(t,u)d(s,a)

.... (больше неравенства следует ..)

Неравенство не имеет смысла для меня.

curryage
источник
Я не нахожу цитату в связанном вопросе.
Рафаэль
1
Попробуйте заменить «не делить ребра» на «не делить вершины» в решении.
Ювал Фильмус
Вы используете только BFS, а не DFS.
Миниатюра

Ответы:

11

Все части доказательства претензии основаны на двух важнейших свойствах деревьев с ненаправленными краями:

  • 1-связность (т. Е. Между любыми 2 узлами дерева существует ровно один путь)
  • любой узел может служить корнем дерева.

Выберите произвольный узел дерева . Пусть U ,s - узлы с d ( u , v ) = d i a m ( G ) . Предположим далее, что алгоритм находит узел x, начинающийся с s первым, а некоторый узел y, начинающийся с x следующим. wlog d ( s , u ) d ( s , v ) . Обратите внимание, чтоU,vВ(г)d(U,v)знак равноdяaм(г)ИксsYИксd(s,U)d(s,v) должно выполняться, если только первая стадия алгоритма не заканчивается в точке x . Мы увидим, что d ( x , y ) = d ( u , v ) .d(s,Икс)d(s,Y)Иксd(Икс,Y)знак равноd(U,v)

Наиболее общая конфигурация всех задействованных узлов может быть замечена в следующей псевдографике (возможно, или s = z x y или оба):sзнак равноZUvsзнак равноZИксY

(u)                                            (x)
  \                                            /
   \                                          /
    \                                        /
     ( z_uv )---------( s )----------( z_xy )
    /                                        \
   /                                          \
  /                                            \
(v)                                            (y)

мы знаем это:

  1. . в противном случае d ( u , v ) < d i a m ( G ) противоречит предположению.d(ZUv,Y)d(ZUv,v)d(U,v)<dяaм(г)
  2. . в противном случае d ( u , v ) < d i a m ( G ) противоречит предположению.d(ZUv,Икс)d(ZUv,U)d(U,v)<dяaм(г)
  3. , иначе этап 1 алгоритма не остановился бы на x .d(s,ZИксY)+d(ZИксY,Икс)d(s,ZUv)+d(ZUv,U)Икс
  4. , иначе этап 2 алгоритма не остановился бы на y .d(ZИксY,Y)d(v,ZUv)+d(ZUv,ZИксY)Y

1) и 2) подразумевают .d(U,v)знак равноd(ZUv,v)+d(ZUv,U)d(ZUv,Икс)+d(ZUv,Y)знак равноd(Икс,Y)+2d(ZUv,ZИксY)d(Икс,Y)

3) и 4) подразумевают d(ZИксY,Y)+d(s,ZИксY)+d(ZИксY,Икс)d(s,ZUv)+d(ZUv,U)+d(v,ZUv)+d(ZUv,ZИксY) эквивалентно .d(Икс,Y)знак равноd(ZИксY,Y)+d(ZИксY,Икс)2*d(s,ZUv)+d(v,ZUv)+d(U,ZUv)d(U,v)

следовательно, .d(U,v)знак равноd(Икс,Y)

аналоговые доказательства верны для альтернативных конфигураций

                 (u)                          (x)
                   \                          /
                    \                        /
                     \                      /
     ( s )---------( z_uv )----------( z_xy )
                     /                      \
                    /                        \
                   /                          \
                 (v)                          (y)

а также

                          (x)        (u)  
                          /            \  
                         /              \ 
                        /                \
     ( s )---------( z_xy )----------( z_uv )
                        \                /          
                         \              /           
                          \            /            
                          (y)        (v)            

это все возможные конфигурации. в частности, ИкспaTчас(s,U),ИкспaTчас(s,v) из-за результата этапа 1 алгоритма и из-за стадии 2.YпaTчас(Икс,U),YпaTчас(Икс,v)

коллапсар
источник
(1) Что касается первого рисунка, разве путь от s до x не должен всегда содержать вершины u и v в некотором порядке, так как они присутствуют в дереве, сгенерированном BFS? (2) Не могли бы вы уточнить, как получаются неравенства? (3) Поскольку BFS, начиная с s и начиная с x, где-то на пути содержат u, v, я считаю, что рисунок должен быть таким, как показано в ссылке imgur.com/jQ94erY . Как приведенные здесь обоснования применимы здесь?
Карридж
@curryage обратите внимание, что дерево задано, а не создается bfs! конкретные ответы: объявление 1) нет. представьте уточнение дерева в графике (1), добавив произвольно много узлов на ребре и ровно 1 узел на ребре ((s,ZИксY) . первая ступень BFS закончится в точке х. объявление 2) какие неравенства не ясны? мы всегда предполагаем, что ( u , v ) - путь, длина диаметра графа d i a g ( G )(zxy,x)(u,v)diag(G), это хорошо определено как G 1-связен. Объявление 3) нет: 3.1 существует более 1 пути между любыми 2 узлами, кроме , поэтому граф не является деревом. ...(s,y)
коллапсар
@curryage ... 3,2 ; это невозможно как д (d(Икс,Y)>d(U,v) по предположению, а диаметр графа - это максимальное минимальное расстояние между любыми двумя узлами. в случае дерева существует ровно 1 путь между любыми 2 узлами, поэтому определение сводится к «максимальному расстоянию между любыми двумя узлами». d(U,v)знак равноdяaм(г)
коллапсар
9

Интуиция позади очень проста для понимания. Предположим, мне нужно найти самый длинный путь, который существует между любыми двумя узлами в данном дереве.

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

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

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

Но какова гарантия того, что x будет конечной точкой максимального пути?

Давайте посмотрим на примере: -

       1   
    / /\ \
   6 2  4 8
         \ \
          5 9
           \
            7

Предположим, я начал свою BFS с 6. Узел на максимальном расстоянии от 6 - это узел 7. Используя BFS, мы можем получить этот узел. Теперь мы запускаем BFS с узла 7, чтобы получить узел 9 на максимальном расстоянии. Путь от узла 7 к узлу 9 явно самый длинный путь.

Что, если BFS, которая началась с узла 6, дала 2 как узел на максимальном расстоянии. Затем, когда мы получим BFS из 2, мы получим 7 как узел на максимальном расстоянии, и самый длинный путь будет тогда 2-> 1-> 4-> 5-> 7 с длиной 4. Но фактическая длина самого длинного пути равна 5. Это не может случается, потому что BFS от узла 6 никогда не даст узел 2 как узел на максимальном расстоянии.

Надеюсь, это поможет.

MayankPratap
источник
1
это простое и понятное объяснение! Благодарность :)
anekix
4

Вот доказательство, которое следует за множеством решений MIT, более тесно связанным с исходным вопросом. Для ясности я буду использовать те же обозначения, которые они используют, чтобы сравнение было легче сделать.

Предположим, у нас есть две вершины и b, такие, что расстояние между a и b на пути p ( a , b ) является диаметром, например, расстояние d ( a , b ) является максимально возможным расстоянием между любыми двумя точками в дереве. Предположим, у нас также есть узел s a , b (если s = a , тогда будет очевидно, что схема работает, поскольку первая BFS получит b , а вторая вернется к a). Предположим также, что у нас есть узелaбaбп(a,б)d(a,б)sa,бsзнак равноaб такое, что d ( s , u ) = max x d ( s , x ) .Ud(s,U)знак равноМаксимумИксd(s,Икс)

Лемма 0: и и b являются листовыми узлами.aб

Доказательство: если бы они не были листовыми узлами, мы могли бы увеличить , расширив конечные точки до конечных узлов, что противоречит d ( a , b ) диаметру.d(a,б)d(a,б)

Лемма 1: .Максимум[d(s,a),d(s,б)]знак равноd(s,U)

Доказательство. Предположим, что и d ( s , b ) строго меньше, чем d ( s).d(s,a)d(s,б) . Мы рассмотрим два случая:d(s,U)

Случай 1: путь вовсе не содержит вершину s . В этом случае d ( a , b ) не может быть диаметром. Чтобы понять почему, пусть t будет единственной вершиной на p ( a , b ) с наименьшим расстоянием до s . Тогда мы видим, что d ( a , u ) = d ( a , t ) + d ( t , sп(a,б)sd(a,б)Tп(a,б)s , поскольку d ( s , u ) > d ( s , b ) = d ( s , t ) + d ( t ,d(a,U)знак равноd(a,T)+d(T,s)+d(s,U)>d(a,б)знак равноd(a,T)+d(T,б) . Точно так же мы бы также имели d ( b , u ) > d ( a , b ) . Это противоречит тому, что d ( a , b ) - диаметр.d(s,U)>d(s,б)знак равноd(s,T)+d(T,б)>d(T,б)d(б,U)>d(a,б)d(a,б)

Случай 2: путь содержит вершину s . В этом случае d ( a , b ) снова не может быть диаметром, так как для некоторой вершины u такой, что d ( s , u ) = max x d ( s , x ) , оба d ( a , u ) и d ( b) , у ) будет больше, чем гп(a,б)sd(a,б) Ud(s,U)знак равноМаксимумИксd(s,Икс)d(a,U)d(б,U) .d(a,б)

Лемма 1 дает причину, по которой мы начинаем второй поиск в ширину в последней обнаруженной вершине первой BFS. Если u - единственная вершина с максимально возможным расстоянием от s , то по лемме 1 она должна быть одной из конечных точек некоторого пути с расстоянием, равным диаметру, и, следовательно, второй BFS с u в качестве корня однозначно находит диаметр. С другой стороны, если существует хотя бы одна другая вершина v такая, что d ( s , v ) = d ( s , u ) , то мы знаем, что диаметр равен dUUsUvd(s,v)знак равноd(s,U) , и не имеет значения, начинаем ли мы второй BFS с u или v .d(a,б)знак равно2d(s,U)Uv

xdavidliu
источник
Потрясающе. Спасибо за публикацию этого ответа. Я удивлен, что этот ответ не получил никаких голосов.
Зефир
0

Сначала запустите DFS из случайного узла, затем диаметр дерева - это путь между самыми глубокими листьями узла в его поддереве DFS: введите описание изображения здесь

seddik11
источник
4
Почему это работает?
Юваль Фильмус
0

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

ИксaИксИксбaa

Extrarius
источник
1
Икс
Я не уверен, как построить такое доказательство. Мне кажется, что обратное утверждение интуитивно верно: если два узла находятся на максимальном расстоянии друг от друга, то для любого данного узла один из двух находится на максимально возможном расстоянии от него.
Extrarius
vИксзнак равноvaзнак равноUбa
Да, но этот вопрос определяет ненаправленные деревья, в контексте которых я интуитивно понятен. Запрет циклов и направленных ребер значительно упрощает решение многих проблем с графами.
Extrarius
0

Одна ключевая вещь, которую нужно знать, это то, что дерево всегда плоское, а это значит, что оно может быть выложено на плоскости, поэтому часто работает обычное двумерное мышление. В этом случае алгоритм говорит, что начиная с любого места, уходите как можно дальше. Расстояние от этой точки до максимально возможного расстояния от нее - самое длинное расстояние в дереве и, следовательно, диаметр.

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

Старый Про
источник
0

@op, способ определения случаев в PDF может быть немного неправильным.

Я думаю, что два случая должны быть:

  1. п1п2п1п2Tп2s

  2. п1п2Tп2п1

Остальная часть доказательства в PDF должна следовать.

С этим определением фигура, показанная OP, попадает в Случай 2.

user650654
источник