Minimaler Spanning Tree mit doppelten Gewichtungsparametern

Betrachte einen Graphen . Jede Kante hat zwei Gewichte und . Suchen Sie einen Spanning Tree, der das Produkt . Der Algorithmus sollte in Bezug auf in Polynomzeit ablaufen .e A e B e ( ∑ e ∈ T A e ) ( ∑ e ∈ T B e ) | V | , | E $G(V,E)$$e$$A_e$$B_e$$\left(\sum_{e \in T}{A_e}\right)\left(\sum_{e \in T}{B_e}\right)$$|V|, |E|$

Ich finde es schwierig, einen der traditionellen Algorithmen auf Spanning Trees (Kruskal, Prim, Edge-Deletion) anzupassen. Wie man es löst? Irgendwelche Hinweise?

Ich gehe davon aus, dass Sie keine negativ gewichteten Kanten erhalten, da dies bei negativen Gewichten möglicherweise nicht funktioniert.

Algorithmus

Beschriften Sie sie für jede Ihrer Kanten mit bis$1$$n$

Es sei Gewicht A der Kantennummer$a_i$$i$

Es sei Gewicht B der Kantennummer$b_i$$i$

Stellen Sie diese Tabelle auf

   |a_1 a_2 a_3 a_4 .. a_n
---+-------------------------
b_1|.........................
b_2|.........................
 . |.........................
 . |.........................
b_n|...................a_n * b_n

Dabei ist jedes Tabellenelement das Produkt aus Zeile und Spalte.

Summieren Sie für jede Kante die entsprechende Tabellenzeile und -spalte (und denken Sie daran, das Element in der Schnittmenge zu entfernen, da es zweimal summiert wurde).

Suchen Sie die Kante mit der größten Summe, und löschen Sie diese Kante, wenn das Diagramm dadurch nicht getrennt wird. Markieren Sie die Kante als wesentlich, ansonsten. Wenn eine Kante gelöscht wurde, füllen Sie ihre Zeilen und Spalten mit 0.

Richtigkeit

Das Ergebnis ist offensichtlich ein Baum.

Das Ergebnis ist offensichtlich überspannend, da keine Eckpunkte getrennt werden.

Das Ergebnis ist minimal? Wenn es eine andere Kante gibt, deren Löschung am Ende des Algorithmus einen kleineren Spannbaum erzeugt, dann wäre diese Kante zuerst gelöscht und auf Null gesetzt worden. (Wenn mir jemand helfen könnte, dieses Beispiel etwas strenger und / oder gegnerischer zu gestalten, dann wäre das großartig.)

Laufzeit

Offensichtlich Polynom in.$|V|$

bearbeiten

$(2,11), (11,2), (4,6)$ ist kein Gegenbeispiel.

$a_1 = 2, a_2 = 11, a_3 = 4$

$b_1 = 11, b_2 = 2, b_3 = 6$

Dann

   | 2     11     4
---+--------------------
11 | 22    121    44
 2 | 4     22     8
 6 | 12    66     24

$(11,2)$ wird entfernt.

Beenden Sie mit$(2,11), (4,6) = 6 * 17 = 102$

Andere Spannbäume sind

$(11,2), (4,6) = 15 * 12 = 180$

$(2,11), (11,2) = 13 * 13 = 169$

Dies ist die Lösung von http://www.cnblogs.com/autsky-jadek/p/3959446.html .

Wir können jeden Spannbaum als einen Punkt in der Ansicht - Ebene, wobei x die Summe des Gewicht Σ e ∈ T A e , y ist die Summe des Gewicht Σ e ∈ T B e . Das Ziel ist es, x y zu minimieren .$x-y$$x$$\sum_{e\in T}A_{e}$$\sum_{e\in T}B_{e}$$xy$

1. Finden der minimalen Spanning - Tree nach Gewicht und das Gewicht B . So haben wir zwei Punkte in der xy - Ebene A , B . In allen Spannbaumpunkten in der Ebene hat A das Minimum x , B das Minimum y .$A$$B$$A,B$$A$$x$$B$$y$

2. Nun wollen wir einen Punkt im Dreieck O A B finden , der den maximalen Abstand zur Linie A B hat , so dass wir den x y -Wert für C für alle Punkte im Dreieck A B C minimieren können .$C$$OAB$$AB$$xy$$C$$ABC$

$2S_{ABC}=|\overrightarrow{AB}\times\overrightarrow{AC}|=(B_{x}-A_{x},B_{y}-A_{y})\times(C_{x}-A_{x},C_{y}-A_{y})=(B_{x}-A_{x})\cdot C_{y}+(A_{y}-B_{y})\cdot C_{x}-A_{y}(B_{x}-A_{x})+A_{x}(B{}_{y}-A_{y})$

3. $A_{y}(B_{x}-A_{x})+A_{x}(B{}_{y}-A_{y}$$(B_{x}-A_{x})\cdot C_{y}+(A_{y}-B_{y})\cdot C_{x}$$G^{\prime}=(V,E)$$w(e)=B_{e}(B_{x}-A_{x})+C_{x}(A_{y}-B_{y})$$G^{\prime}$$C$

4. $OBC, OAC$$BC,AC$$O$

5. $xy$