Minimale schädliche Kosten in der Grafik

Dies ist das Multiway-Cut-Problem in Bäumen. Es kann in polynomieller Zeit durch eine einfache dynamische Programmierung gelöst werden. Siehe Chopra und Rao: " Auf dem mehrwegig geschnittenen Polyeder ", Networks 21 (1): 51-89, 1991 .

Ich denke, ein modifizierter Kruskal ist der Weg hierher zu gehen.

Nimm den Graphen G '= (V', E '), V' = V, E '= {}. Sortieren Sie die Kanten in E in nicht aufsteigender Reihenfolge der Kosten. Nun, für jede Kante in E, füge es zu E 'hinzu, wenn es keine zwei Komponenten verbindet, die beide Scheitelpunkte mit Bomben haben. Das Ergebnis ist die Summe der Kosten von E-E.

BEARBEITEN:

Führen Sie dies in Ihrem Beispiel aus.

Zu Beginn ist unser Kantensatz leer {} und wir nehmen die Kanten in nicht aufsteigender Reihenfolge [[1], [2], [0, 1], [2], [4], [1], [3]).

Also besteht unser Graph am Anfang aus 5 getrennten Komponenten.

(1, 2) kostet 8, und nur eine der Komponenten, die es verbindet, hat eine Bombe. Also fügen wir es zu E 'hinzu. E '= {(1, 2)} und wir haben 4 Komponenten.

Die nächsthöhere Kostengrenze ist (0, 1) mit Kosten von 5. Aber beide Komponenten haben Bomben, also fügen Sie diese Kante nicht hinzu.

Der nächste ist (2, 4). Dies schließt auch Komponenten mit Bomben an, also überspringen wir dies auch.

Zuletzt ist die niedrigste Kostenkante (1, 3). Da eine ihrer Komponenten (die nur den Knoten 3 enthält) keine Bombe hat, fügen wir sie zu E 'hinzu.

Dies gibt uns E '= {(1,2), (1, 3)}.

Meine Argumentation ist, dass wir Kanten mit höheren Kosten vor solchen mit niedrigeren Kosten hinzufügen. Dadurch wird sichergestellt, dass in jedem Pfad zwischen Knoten mit Bomben im ursprünglichen Knoten alle Kosten bis auf die niedrigsten hinzugefügt werden.

Hier ist meine Hypothese:

Der Graph G ist ein Baum. Daher gibt es nur einen Pfad zwischen zwei Knoten.

Angenommen, es gibt L rote (Bomb) Knoten und V-L weiße (Knoten ohne Bomb). Die Lösung erfordert die Partitionierung von G in eine Gesamtstruktur von L Unterbäumen. Dies erfordert die Entfernung von mindestens L-1 Kanten.

Jeder der Kanten, die entfernt werden, muss auf ein Pfad zwischen zwei roten Knoten sein.

A. Löschen Sie den Baum G, um alle Kanten zu entfernen, die nicht an einem Pfad zwischen zwei roten Knoten beteiligt sind.

1. Entfernen Sie weiße Blattknoten (und die einfallende Kante) aus der Betrachtung.
2. Wiederholen Sie 1, bis sich im modifizierten Diagramm keine weißen Blattknoten mehr befinden.

B. Nach (A) sind alle Kanten im Graphen Kanten, die einen Pfad zwischen zwei roten Knoten bilden.

Wählen Sie die Kante mit dem geringsten Gewicht in dieser Baumstruktur aus. Dies führt zu zwei Unterbäumen, wobei jeder Baum mindestens einen roten Knoten enthält.

C. Kehren Sie zu Schritt A für jeden der in B erstellten Unterbäume zurück, wenn dieser mehr als einen roten Knoten enthält.

Das ist O (V log V) (| E | ist | V | -1).

Ich denke, der folgende Vorschlag sollte funktionieren:

• 1) Beginne mit einer Bombe, in deinem Beispiel beginne ich mit: 0
• 2) Erstellen Sie Pfade für alle benachbarten Knoten. Nimm also alle Beziehungen und beginne einen Weg mit ihnen. In Ihrem Beispiel wird ein Pfad gestartet: 0 -> 1 .
• 3) Wenn Sie eine andere Bombe auf einem Pfad treffen, entfernen Sie die Kante mit den niedrigsten Kosten. In dem Beispiel treffen wir keine Bombe, also fahren wir mit Schritt 2 fort.
• 3A) Noch keine Bombe in irgendeinem Pfad. Fahren Sie mit Schritt 2 fort und erweitern Sie die Pfade mit den neuen benachbarten Knoten. In Ihrem Fall wird ein neuer Pfad erstellt: 1 -> 3 . Und der bestehende wird erweitert: 0 -> 1 -> 2
• 3B) Eine Bombe ist auf dem Weg gefunden. Nimm den Weg, wo die Bombe gefunden wird, und entferne die Kante mit den niedrigsten Kosten. In Ihrem Beispiel enthält der Pfad 0 -> 1 -> 2 eine Bombe (2). Also entfernen wir die Beziehung mit den Kosten. 5. Entfernen Sie den Pfad von der 'Todo' und fahren Sie mit Schritt 2 auf den zuletzt erreichten Knoten (2 und 3) fort.

Ich am Ende sollten Sie jeden Knoten genau einmal durchlaufen. Wenn ich mich nicht irre, sollte die Komplexität ungefähr O (n log n) sein.

Ссылка

hat eine Beschreibung des Algorithmus.

Google HTML-Version der Postscript-Datei

==========================================

Ссылка

  

Der Fall k = 2 ist nicht die einzige polynomiell lösbare Instanz des Mehrwege-Schnittproblems.   Lovdsz [12] und Cherkasskij [3] zeigen, dass wenn ce = 1 Ve E E und G Eulerian ist, dann der Multiway   Schnittproblem ist polynomiell lösbar. Erdos und Szökely [8] haben gezeigt, dass eine Verallgemeinerung von   Das Mehrwege-Schnittproblem ist polynomiell lösbar, wenn der zugrundeliegende Graph G ein Baum ist. Dalhaus   et. al. [7] haben gezeigt, dass das Problem für feste k-planare Graphen polynomiell lösbar ist.

Ich hatte letzte Nacht eine simple, auf einem Greedy-Algorithmus basierende Lösung geschrieben, die darin bestand, Knoten zu entfernen, die sich nicht auf einem Pfad zwischen zwei roten (Terminal) Knoten befanden, und dann den kleinsten Gewichtungsknoten auszuwählen und dann den Vorgang zu wiederholen. Bäume. Ich habe das gelöscht, da das weitere Lesen andeutete, dass das Problem NP ist. Aber diese Referenz legt nahe, dass es eine polynomiale Lösung gibt ...