Minimalne drzewo opinające z podwójnymi parametrami wagi

Rozważmy wykres . Każda krawędź ma dwa obciążniki i . Znajdź drzewo które minimalizuje produkt . Algorytm powinien działać w czasie wielomianowym w odniesieniu do.$G(V,E)$A e B e ( ∑ e ∈ T A e ) ( ∑ e ∈ T B e ) | 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|$

Trudno mi dostosować dowolny tradycyjny algorytm na drzewach opinających (Kruskal, Prim, Usuwanie krawędzi). Jak to rozwiązać? Jakieś wskazówki?

Zakładam, że nie masz ujemnie ważonych krawędzi, ponieważ może to nie działać, jeśli występują ujemne wagi.

Algorytm

Dla każdej krawędzi oznacz je od do$1$$n$

Niech waży A numeru krawędzi$a_i$$i$

Niech waga B numeru krawędzi$b_i$$i$

Przygotuj ten stół

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

Każdy element tabeli jest iloczynem wiersza i kolumny.

Dla każdej krawędzi zsumuj odpowiedni wiersz tabeli i kolumnę (pamiętaj o usunięciu elementu w przecięciu, ponieważ został on zsumowany dwukrotnie).

Znajdź krawędź, która ma największą sumę, usuń ją, jeśli nie rozłączy wykresu. W przeciwnym razie zaznacz krawędź jako niezbędną. Jeśli krawędź została usunięta, wypełnij jej wiersze i kolumny wartością 0.

Poprawność

Rezultatem jest oczywiście drzewo.

Wynik jest oczywiście szeroki, ponieważ żadne wierzchołki nie są odłączone.

Wynik jest minimalny? Jeśli istnieje inna krawędź, której usunięcie spowoduje utworzenie mniejszego drzewa opinającego na końcu algorytmu, wówczas krawędź ta zostałaby najpierw usunięta i unieważniona. (gdyby ktoś pomógł mi uczynić to nieco bardziej rygorystycznym / i / lub kontrprzykładowym, byłoby świetnie)

Środowisko wykonawcze

Oczywiście wielomian w.$|V|$

edytować

$(2,11), (11,2), (4,6)$ jest nie przykładem licznika.

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

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

Następnie

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

$(11,2)$ zostaje usunięty.

Skończ z$(2,11), (4,6) = 6 * 17 = 102$

Inne drzewa rozpinające są

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

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

To jest rozwiązanie z http://www.cnblogs.com/autsky-jadek/p/3959446.html .

Możemy zobaczyć każde drzewo opinające jako punkt na płaszczyźnie , gdzie jest sumą masy , y jest sumą wagi . Celem jest zminimalizowanie .$x-y$$x$$\sum_{e\in T}A_{e}$$\sum_{e\in T}B_{e}$$xy$

1. Znajdź minimalne drzewo rozpinające według wagi i waga . Tak więc mamy dwa punkty w płaszczyźnie xy . We wszystkich punktach drzewa rozpinającego w płaszczyźnie ma minimum , ma minimum .$A$$B$$A,B$$A$$x$$B$$y$

2. Teraz staramy się znaleźć punkt w trójkącie który ma maksymalną odległość do linii , abyśmy mogli zminimalizować wartość dla dla wszystkich punktów w trójkącie .$C$$OAB$$AB$$xy$$C$$ABC$

Ponieważ .$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. Zauważ, że jest stałą, więc teraz dążymy do maksymalizacji . Więc tworzymy nowy wykres , podczas gdy waga . Teraz uruchamiamy maksymalne drzewo rozpinające na do uzyskania punktu . ( B x - A x )⋅ C y +( A y - B y )⋅ C x G ′ =(V,E)w(e)= B e ( B x - A x )+ C x ( A y - B y$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. Uruchom powyższy algorytm na rekurencyjnie, aż nie ma więcej drzew obejmujące między i .$OBC, OAC$$BC,AC$$O$

5. Teraz otrzymujemy zestaw możliwych drzew spinających. Oblicz wartość dla każdego drzewa, aby uzyskać minimalne drzewo.$xy$