Сколько кратчайших расстояний изменяется при добавлении ребра на график?

22

Пусть G=(V,E) некоторый полный взвешенный неориентированный граф. Построим второй граф G=(V,E) , добавив ребра одно за другим из в . Добавим края дляEEΘ(|V|)G всего.

Каждый раз, когда мы добавляем одно ребро (u,v) к E , мы рассматриваем кратчайшие расстояния между всеми парами в (V,E) и (V,E{(u,v)}) . Мы посчитаем, сколько из этих кратчайших расстояний изменилось в результате сложения (u,v) . Пусть Ci будет числом кратчайших расстояний, которые меняются при добавлении ith ребро, и пусть будет количеством ребер, которые мы добавим в итоге.n

Насколько большой ?C=iCin

Поскольку , C = O ( n 2 ) . Может ли эта граница быть улучшена? Обратите внимание, что я определяю C как среднее по всем ребрам, которые были добавлены, поэтому один раунд, в котором изменяется большое количество расстояний, не столь интересен, хотя он доказывает, что C = Ω ( n ) .Ci=O(|V|2)=O(n2)C=O(n2)CСзнак равноΩ(N)

У меня есть алгоритм для жадного вычисления геометрического t-гаечного ключа, который работает за , поэтому, если C равно o ( n 2 ) , мой алгоритм работает быстрее, чем исходный жадный алгоритм, и если C действительно мал потенциально быстрее, чем самый известный алгоритм (хотя я сомневаюсь в этом).O(Cnlogn)Co(n2)C

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

Можно предположить, что вершины соответствуют точкам в 2d плоскости, а расстояния между вершинами являются евклидовыми расстояниями между этими точками. То есть каждая вершина соответствует некоторой точке ( x , y ) на плоскости, а для ребра ( u , v ) = ( ( x 1 , y 1 ) , ( x 2 , y 2 ) ) ее вес равен к v(x,y)(u,v)=((x1,y1),(x2,y2))(x2x1)2+(y2y1)2.

Алекс тен Бринк
источник
2
Возьмите два клика, соединенных дорожкой с двумя ребрами. Добавление одного ребра непосредственно между кликами сокращает самых коротких путей. Ω(n2)
Луи
1
@Louis: да, есть примеры, в которых одно ребро вызывает изменение большого расстояния, но существуют ли графики, в которых это происходит для каждого добавляемого ребра, или, по крайней мере, для многих из них? Именно поэтому я определил как среднее по всем краям :)C
Алекс тен Бринк
1
Большинство ребер на этом графике, которые можно добавить, относятся к описанному мной типу ...
Луи,
@ Луис Правда. Клики содержат ребер, что больше, чем я когда-либо добавлю к своему графику. O(n2)
Алекс тен Бринк
Раньше у меня была такая же проблема, но мой граф был немного разреженным с и я должен доказать, что средние изменения - это O (1), но я не смог этого сделать :-). Но для вашего случая, я думаю, если вы найдете связь между этим и решением APSP, вы можете получить некоторые результаты. |E|=O(|V|)

Ответы:

19

Рассмотрим следующую линейную цепочку с узлами, n ребрами и порочно выбранными весами:n+1n

пример
[ источник ]

Ясно, что ребра могли быть добавлены в порядке их весов, и их . Добавление пунктирного ребра (что допустимо) создает более короткие пути для всех пар ( u i , b j ) с i , j = 1 , , k . Как k nnO(|V|)(ui,bj)i,j=1,,k и предполагая, чтоnΘ(|V|), первая и последняя строки содержатΘ(|V|) помногим узлам, и сложение вызываетΘ(|V|2)многих изменений кратчайшего пути.kn4nΘ(|V|)Θ(|V|)Θ(|V|2)

Теперь мы можем двигаться «наружу», то есть добавить следующее ребро с весом между u k - 1 и b k - 1 и т. Д .; если мы продолжим это до ( u 1 , b 1 ) , мы вызовем всего Θ ( | V | 3 ) изменений кратчайшего пути.n+2uk1bk1(u1,b1)Θ(|V|3)

Если это не убедит вас, обратите внимание, что вы можете начать этот «процесс» с и работать оттуда; Таким образом , вы добавить п ребер , которые вызывают в общей сложности Х п я = 1 я 2thetas ; ( п 3 ) = & thetas ( | V | 3 ) много кратчайших изменений пути --- это просто невозможно сделать , чтобы поместиться на одном экран.(c1,c2)ni=1ni2Θ(n3)=Θ(|V|3)

Рафаэль
источник
1
Это действительно работает, и, кроме того, ваш пример может быть немного изменен, чтобы стать евклидовым. Спасибо :)
Алекс тен Бринк