Выявление бесполезных ребер для кратчайшего пути

11

Рассмотрим граф (задача имеет смысл как для ориентированных, так и для неориентированных графов). Назовите матрицей расстояний : - это кратчайшее расстояние от вершины до вершины в для некоторой фиксированной функции агрегирования (например, или ).GMGGMG[i,j]ijG+max

Я сказать , что подграф G из G (с таким же множеством вершин) является зр-эквивалентно к G , если MG=MG . Другими словами, удаление ребер для перехода от G к G не меняет длину кратчайших путей; удаленные края не требуются для кратчайшего пути.

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

Мой первый вопрос: имеют ли эти понятия стандартное название?

Мой второй вопрос: какова сложность классификации ребер G таким способом, в зависимости от того, является ли G ненаправленным или направленным, и от функции агрегирования?

(Например, для G ненаправленного и для max минимальные sp-эквивалентные подграфы являются остовными деревьями с минимальным весом, поэтому, по крайней мере, если все веса ребер различны, классификация легко вычисляется путем вычисления уникального минимального остовного дерева, но в целом Я не знаю, как все работает.)

a3nm
источник
2
«Например, если G является ненаправленным и невзвешенным, любое остовное дерево G является минимальным sp-эквивалентным подграфом». Похоже, что это не так: в все расстояния равны , но ни одно остовное дерево обладает этим свойством. На самом деле никакой подграф не делает. В противном случае это звучит как гаечный ключ en.wikipedia.org/wiki/Graph_spanner#DistanceKn1Kn
Сашо Николов
5
Фактически, для любого неориентированного невзвешенного графа не существует sp-эквивалентного подграфа: если подграф не включает ребро , то . GG(u,v)1=MG[u,v]<MG[u,v]
Сашо Николов
2
Я думаю, мы можем, по крайней мере, сказать, что идентификация так же проста, как кратчайший путь для всех пар: если существует ребро но кратчайший путь от до короче этого ребра, то ребро «бесполезно» (мы должны всегда использовать этот более короткий путь вместо этого края в любом сценарии); наоборот, если ребро «бесполезно», то путь должен быть короче, чем длина ребра от до . Так что просто итерируйте по краям и проверьте, существует ли более короткий путь, чем этот край. (Выше для обычного кратчайшего пути, не думал о правиле агрегации .)(u,v)uvuvmax
usul
3
Возможно, вы захотите посмотреть «
Хранители
2
Сашо Николов: Извините, для неориентированных и невзвешенных графов я имел в виду ребра с весом 0, а не 1. Перефразируя это в вопросе.
a3nm

Ответы:

3

Если вы ищете способ назвать (или поочередно охарактеризовать) эти ребра, которые вы называете «бесполезными» и «необходимыми», вы можете назвать их ребрами с центральностью между 0 и = 1 соответственно. Каждое ребро может быть классифицировано как имеющее = 0, = 1 или (0,1) меру промежуточности во времени всех пар-кратчайших путей.

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

Функция централизованности встроена почти в каждый анализ сети, который я видел, и есть определение, которое также применимо к ориентированным графам:

(редактировать: ссылка, которую я дал изначально, обсуждала только центральность узлов, но вот единственная статья в Википедии, в которой я могу найти информацию о центральности границ: http://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm Тем не менее, промежуточное звено является стандартной мерой, которую обычно можно найти в пакетах сетевого анализа.)

JimN
источник
Я думаю, что разница между центральностью узлов между центральностью и центральностью между краями несущественна, потому что вы всегда можете добавить промежуточные узлы к ребрам или скопировать узлы и добавить одно ребро из одной копии в другую, чтобы уменьшить одно определение до другого. Это полезный указатель, спасибо, что сообщили мне об этом!
a3nm