Um algoritmo para reconstruir um gráfico a partir de suas informações de caminho mais curto?

8

Eu tenho alguns dados de caminho mais curto para um gráfico. Posso reconstruir o próprio gráfico a partir desses dados?

Mais precisamente, eu tenho uma matriz booleana (0/1) para cada vértice v no gráfico (V, E) . Matriz elemento [s, d] é igual a 1 sse v está no caminho mais curto do vértice fonte s de destino vértice d . Todas as arestas do gráfico têm o mesmo comprimento.

Por exemplo, para o gráfico

(V1) -- (V2) -- (V3)

as três matrizes seriam:

V1:

1 1 1
1 0 0
1 0 0

V2:

0 1 1
1 1 1
1 1 0

V3:

0 0 1
0 0 1
1 1 1

Minhas perguntas:

1) existe um algoritmo para reconstruir o conjunto de arestas E dessas matrizes?

2) a solução é sempre única? (isso é mais uma curiosidade pessoal do que um requisito real)

3) o algoritmo pode ser generalizado para comprimentos de borda não uniformes?

algorithms kfx
fonte
1
Se houver uma aresta entre dois vértices v1e v2, exatamente esses dois vértices estarão no caminho mais curto entre v1e v2. Assim, para qualquer outro vértice v, [v1, v] == 0 == [v, v1]na matriz de v2e [v2, v] == 0 == [v, v2]na matriz de v1.
Giorgio
1
Talvez eu esteja errado, mas não são 1) e 2) equivalentes?
proskor
Não tenho certeza se 1) e 2) são equivalentes: pode haver mais de um gráfico para uma informação de caminho mais curto e também um algoritmo que encontra todas as soluções possíveis.
Giorgio
Ok, mas isso é um problema diferente. O objetivo era reconstruir um gráfico a partir do conjunto dessas matrizes, não calcular se existe uma solução que satisfizesse as restrições codificadas nessas matrizes.
proskor
1
@Giorgio adicionando uma única aresta da v1 à v3 maior que a v1-v2-v3 resulta no mesmo conjunto de matrizes, a menos que esteja faltando alguma coisa - então seria um contra-exemplo para o caso de aresta não uniforme
jk.

Respostas:

2

você pode extrair a matriz de adjacência das matrizes de caminho usando a propriedade a seguir.

Há uma aresta entre 2 vértices se d se e somente se o caminho mais curto entre eles contiver apenas se d.

Para comprimentos não uniformes, você obterá a solução única se a desigualdade do triângulo persistir . Caso contrário, um gráfico com d(p1,p2)=1 d(p2,p3)=2e d(p1,p3)=4mostrará o caminho mais curto entre p1e p3como através, em p2vez da conexão direta. O que significa que a aresta [p1, p3] nunca fará parte de nenhum caminho mais curto.

catraca arrepiante
fonte