Die Idee eines MST mit eingeschränktem Durchmesser besteht darin, dass Sie alle Scheitelpunkte miteinander verbunden halten und einen bestimmten Abstand voneinander einhalten. Aber alle Papiere, die ich gesehen habe, halten die Anforderung aufrecht, dass Sie einen Baum produzieren, wenn das Zulassen von Zyklen dazu beitragen kann, den Durchmesser zu verringern. Kennt jemand irgendwelche Papiere, die dies untersuchen? (Es ist schwer zu suchen.)
Betrachten Sie beispielsweise ein vollständiges Diagramm mit Scheitelpunkten, die in einem Kreis in einer Ebene angeordnet sind (Kantengewicht = euklidischer Abstand). Das MST (z. B. über Prims) folgt dem Kreis, so dass der Durchmesser des Graphen ungefähr dem Umfang des Kreises entspricht . Indem wir die Endkante verbinden lassen, können wir den Durchmesser halbieren, ohne das Gesamtgewicht stark zu erhöhen.
Antworten:
Der Subgraph "Spanning mit minimalem Durchmesser" ist das, wonach Sie suchen sollten. Selbst bei planaren Graphen ist es NP-schwer zu berechnen. Dieses Papier gibt einen schönen Überblick.
quelle