Un algoritmo per ricostruire un grafico dalla sua informazione di percorso più breve?

Question

Un algoritmo per ricostruire un grafico dalla sua informazione di percorso più breve?

#1 da (2 voti)

8

Ho alcuni dati di percorso più brevi per un grafico. Posso ricostruire il grafico stesso da questi dati?

Più precisamente, ho una matrice booleana (0/1) per ogni vertice v nel grafico (V, E) . L'elemento di matrice [s, d] è uguale a 1 iff v si trova nel percorso più breve dal vertice di origine s al vertice di destinazione d . Tutti i bordi del grafico hanno la stessa lunghezza.

Ad esempio, per il grafico

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

le tre matrici sarebbero:

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

Le mie domande:

1) esiste un algoritmo per ricostruire l'insieme di spigoli E da queste matrici?

2) la soluzione è sempre unica? (questa è più una curiosità personale che un requisito reale)

3) l'algoritmo può essere generalizzato a lunghezze dei bordi non uniformi?

algorithms

posta kfx 07.07.2014 - 14:19

fonte

1 risposta

Leggi altre domande sui tag algorithms

Come aggiungere contributori al file LICENCE? Come distribuire il mio software scientifico con il minor numero possibile di dipendenze?

score 2 · Answer 1

puoi estrarre la matrice di adiacenza dalle matrici del percorso usando la seguente proprietà.

C'è un margine tra 2 vertici s e d se e solo se il percorso più breve tra loro contiene solo s e d .

Per una lunghezza non uniforme, otterrai la soluzione unica solo se contiene la disuguaglianza triangolare . In caso contrario, un grafico con d(p1,p2)=1 d(p2,p3)=2 e d(p1,p3)=4 mostrerà il percorso più breve tra p1 e p3 come p2 invece della connessione diretta. Ciò significa che il bordo [p1, p3] non farà mai parte di alcun percorso più breve.