Identificando arestas inúteis para o caminho mais curto

$G$ $M_G$ $G$ $M_G[i, j]$ $i$ $j$ $G$ $+$ $\max$

Eu digo que um subgrafo de (com o mesmo conjunto de vértices) é sp-equivalente a se . Em outras palavras, remover arestas para ir de para não altera o comprimento dos caminhos mais curtos; as arestas removidas não são necessárias para nenhum caminho mais curto. $G'$ $G$ $G$ $M_G = M_{G'}$ $G$ $G'$

Em geral, não existe um único subgrafo de equivalente a sp que seja mínimo para inclusão. Por exemplo, se não é direcionado e todas as arestas têm peso , qualquer árvore de abrangência de é um subgrafo mínimo equivalente a sp (na verdade, qualquer aresta em um ciclo pode ser removida, mas desconectar um par de vértices obviamente altera a distância). No entanto, ainda posso chamar as arestas de inúteis se elas não estiverem em um subgráfico mínimo equivalente a sp, necessário se estiverem em todos os subgráficos mínimos equivalentes a sp (por exemplo, na interseção) e opcional se estiverem em alguns deles (por exemplo, , em sua união). $G$ $G$ $0$ $G$ $G$

Minha primeira pergunta é: essas noções têm um nome padrão?

Minha segunda pergunta é: Qual é a complexidade de classificar as arestas de dessa maneira, dependendo de ser não direcionado ou direcionado e da função de agregação? $G$ $G$

(Por exemplo, para não direcionado e para , os subgráficos mínimos equivalentes a sp abrangem árvores de peso mínimo, portanto, pelo menos se todos os pesos das arestas forem diferentes, a classificação será facilmente calculada calculando-se a árvore de abrangência mínima exclusiva, mas em geral Não sei como as coisas funcionam.) $G$ $\max$

ds.algorithms reference-request graph-algorithms shortest-path a3nm
fonte

"Por exemplo, se G é direcionado e não ponderado, qualquer árvore de abrangência de G é um subgrafo mínimo equivalente a sp." Isso não parece ser verdade: em todas as distâncias são , mas nenhuma árvore de tem essa propriedade. De fato, nenhum subgráfico faz. Em outras palavras, isso soa como uma chave inglesa pt.wikipedia.org/wiki/Graph_spanner#Distance #

K_{n}

$K_n$

1

$1$

K_{n}

$K_n$

Sasho Nikolov

De fato, para qualquer gráfico não ponderado não direcionado , não existe subgráfico equivalente a sp: se um subgrafo não incluir aresta , então .

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]$

Sasho Nikolov

Acho que podemos pelo menos dizer que a identificação é tão fácil quanto o caminho mais curto de todos os pares: se houver uma aresta mas o caminho mais curto de a for mais curto que a aresta, então a aresta é "inútil" (devemos sempre utilizar esse caminho mais curto em vez dessa borda, em qualquer cenário); por outro lado, se uma aresta é "inútil", deve haver um caminho mais curto que o comprimento da aresta de a . Portanto, basta percorrer as arestas e verificar se há um caminho mais curto que a aresta. (O texto acima é para o habitual caminho mais curto, ainda não pensou sobre o regra de agregação.)

(u, v)

$(u,v)$

u

$u$

v

$v$

u

$u$

v

$v$

max

$\max$

usul

Você pode querer olhar para cima "preservadores à distância"

arnab

Sasho Nikolov: Desculpe, para gráficos não direcionados e não ponderados, eu quis dizer arestas de peso 0, não 1. Reformulando isso na questão.

a3nm

Se você estiver procurando uma maneira de nomear (ou caracterizar alternadamente) essas arestas que você chama de "inúteis" e "necessárias", você pode se referir a elas como as arestas com centralidade entre as partes = 0 e = 1, respectivamente. Cada aresta pode ser classificada como tendo = 0, = 1 ou em (0,1) medida de intervalo no tempo dos caminhos mais curtos de todos os pares.

Essa é uma medida bem estudada das arestas da rede, e existem algoritmos rápidos para atualizar todas as pontuações de centralidade das arestas com as exclusões das arestas (mas não tenho certeza sobre outras perturbações).

Uma função de centralidade é incorporada a quase todas as análises de rede que eu já vi, e há uma definição que se aplica também a gráficos direcionados:

(editar: o link que forneci inicialmente discutiu apenas a centralidade entre os nós dos nós, mas aqui está o único artigo da Wikipedia que discute a centralidade entre os limites: http://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm Ainda assim, o limite entre as bordas é uma medida padrão que geralmente pode ser encontrada em pacotes de análise de rede.)

JimN
fonte

Eu acho que a diferença entre a centralidade entre nós e a centralidade entre as bordas é essencial porque você sempre pode adicionar nós intermediários às bordas ou copiar nós e adicionar uma borda de uma cópia à outra, para reduzir uma definição à outra. Este é um ponteiro útil, obrigado por me informar disso!

a3nm

Identificando arestas inúteis para o caminho mais curto

Respostas: