Minimale Gesamtdistanz mit k Links zwischen n Knoten

Question

Ich kam mit dem folgenden Problem, dass ich nicht kenne die Lösungen zu finden, noch kann ich den 'Lookup' Begriff weiter untersuchen.

Angenommen, wir haben N geordnete Knoten (n_1, n_2 ... n_N) mit jeweils einem festen Abstand von 1 zwischen ihnen. So dist (n_1, n_N) = N-1. Jetzt dürfen wir zwei beliebige Knoten verbinden und damit ihre Entfernung zu 1 reduzieren. Nehmen wir an, wir können solche Verbindungen haben.

Das Problem ist: Wie wählen wir, welche Knoten verbinden, um den Gesamtabstand zwischen zwei Knoten zu minimieren?

Ist dieses Problem eine bekannte Variante eines gut untersuchten Problems? Hat eine effiziente Lösung gibt es für diese (oder eine Variante, wo wir nur die maximale Entfernung zwischen zwei beliebigen Knoten minimieren wollen)

Dank

Answer 1

Sie interessiert sein an „On the sum of all distances in a graph or digraph“. Dieses Papier bezieht sich auf Ihre "Gesamtdistanz" als die "Übertragung" eines Graphen. Ihre "maximale Entfernung" wird allgemein als "Durchmesser" eines Graphen bezeichnet. Es diskutiert die zwei, beweist einige Eigenschaften einer Graphenübertragung und zeigt, dass die Übertragung und der Durchmesser unabhängig voneinander sind.

Naiv, Sie haben n-choose-k Optionen zu versuchen. Das ist ziemlich schlecht, wenn n und k groß sind. Nicht schlecht, wenn einer von ihnen klein ist.

Es gibt Arbeit, es besser zu machen. This Mathoverflow question fragt nach der Verringerung der mittleren Entfernung zwischen den Scheitelpunkten, die proportional zur Übertragung des Graphen ist. Es gibt zwei Antworten, von denen ich keine verbürgen kann. Es bezieht sich auch auf a paper, die direkt auf diese Frage eingeht.

Die Minimierung des Durchmessers eines Graphen wird in this paper behandelt.

Sie könnten in Betracht ziehen, diese Frage auf den Math Stackexchange zu beziehen.