Ein Algorithmus zum Rekonstruieren eines Graphen aus seinen kürzesten Pfadinformationen?

8

Ich habe einige kürzeste Wegdaten für ein Diagramm. Kann ich das Diagramm selbst aus diesen Daten rekonstruieren?

Genauer gesagt habe ich eine boolesche (0/1) Matrix für jeden Scheitelpunkt v in Graph (V, E) . Das Matrixelement [s, d] ist gleich 1, wenn sich v auf dem kürzesten Weg vom Quellscheitelpunkt s zum Zielscheitelpunkt d befindet . Alle Kanten im Diagramm haben die gleiche Länge.

Zum Beispiel für das Diagramm

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

Die drei Matrizen wären:

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

Meine Fragen:

1) Gibt es einen Algorithmus, um die Menge der Kanten E aus diesen Matrizen zu rekonstruieren?

2) Ist die Lösung immer einzigartig? (Dies ist eher eine persönliche Neugier als eine echte Anforderung)

3) Kann der Algorithmus auf ungleichmäßige Kantenlängen verallgemeinert werden?

algorithms kfx
quelle
1
Wenn zwischen zwei Eckpunkten v1und eine Kante liegt v2, befinden sich genau diese beiden Eckpunkte auf dem kürzesten Weg zwischen v1und v2. Also für einen anderen Scheitelpunkt v, [v1, v] == 0 == [v, v1]in der Matrix v2und [v2, v] == 0 == [v, v2]in der Matrix aus v1.
Giorgio
1
Vielleicht irre ich mich, aber nicht 1) und 2) gleichwertig?
Proskor
Ich bin nicht sicher, ob 1) und 2) gleichwertig sind: Es gibt möglicherweise mehr als einen Graphen für eine bestimmte Information über den kürzesten Pfad und auch einen Algorithmus, der alle möglichen Lösungen findet.
Giorgio
Ok, aber das ist ein anderes Problem. Es ging darum , einen Graphen aus der Menge dieser Matrizen zu rekonstruieren und nicht zu berechnen, ob es eine Lösung gibt, die die in diesen Matrizen codierten Einschränkungen erfüllt.
Proskor
1
@Giorgio Das Hinzufügen einer einzelnen Kante von v1 zu v3, die länger als v1-v2-v3 ist, führt zu demselben Satz von Matrizen, es sei denn, ich vermisse etwas - wäre also ein Gegenbeispiel für den ungleichmäßigen
Kantenfall

Antworten:

2

Sie können die Adjazenzmatrix mithilfe der folgenden Eigenschaft aus den Pfadmatrizen extrahieren.

Es gibt eine Kante zwischen 2 Scheitelpunkten sund d genau dann, wenn der kürzeste Pfad zwischen ihnen nur sund enthält d.

Bei ungleichmäßiger Länge erhalten Sie nur dann die eindeutige Lösung, wenn die Dreiecksungleichung gilt. Andernfalls zeigt ein Diagramm mit d(p1,p2)=1 d(p2,p3)=2und d(p1,p3)=4den kürzesten Weg zwischen p1und p3wie durch p2anstelle der direkten Verbindung. Dies bedeutet, dass die Kante [p1, p3] niemals Teil eines kürzesten Pfades sein wird.

Ratschenfreak
quelle