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

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

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

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

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

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

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

ds.algorithms reference-request graph-algorithms shortest-path a3nm
источник

«Например, если G является ненаправленным и невзвешенным, любое остовное дерево G является минимальным sp-эквивалентным подграфом». Похоже, что это не так: в все расстояния равны , но ни одно остовное дерево обладает этим свойством. На самом деле никакой подграф не делает. В противном случае это звучит как гаечный ключ en.wikipedia.org/wiki/Graph_spanner#Distance

K_{n}

$K_n$

1

$1$

K_{n}

$K_n$

Сашо Николов

Фактически, для любого неориентированного невзвешенного графа не существует sp-эквивалентного подграфа: если подграф не включает ребро , то .

G

$G$

G^{'}

$G'$

(u, v)

$(u, v)$

1 = M_{G} [u, v] < M_{G^{'}} [u, v]

$1 = M_G[u, v] < M_{G'}[u, v]$

Сашо Николов

Я думаю, мы можем, по крайней мере, сказать, что идентификация так же проста, как кратчайший путь для всех пар: если существует ребро но кратчайший путь от до короче этого ребра, то ребро «бесполезно» (мы должны всегда использовать этот более короткий путь вместо этого края в любом сценарии); наоборот, если ребро «бесполезно», то путь должен быть короче, чем длина ребра от до . Так что просто итерируйте по краям и проверьте, существует ли более короткий путь, чем этот край. (Выше для обычного кратчайшего пути, не думал о правиле агрегации .)

(u, v)

$(u,v)$

u

$u$

v

$v$

u

$u$

v

$v$

max

$\max$

usul

Возможно, вы захотите посмотреть «

Хранители

Сашо Николов: Извините, для неориентированных и невзвешенных графов я имел в виду ребра с весом 0, а не 1. Перефразируя это в вопросе.

a3nm

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

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

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

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

JimN
источник

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

a3nm

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

Ответы: