Árvore de abrangência mínima com parâmetros de peso duplo

Considere um gráfico $G(V,E)$ . Cada aresta $e$ tem dois pesos $A_e$ e $B_e$ . Encontrar uma árvore geradora que minimiza o produto $\left(\sum_{e \in T}{A_e}\right)\left(\sum_{e \in T}{B_e}\right)$ . O algoritmo deve ser executado em tempo polinomial em relação a $|V|, |E|$.

Acho difícil adaptar qualquer um dos algoritmos tradicionais em árvores de abrangência (Kruskal, Prim, Edge-Deletion). Como resolver isso? Alguma dica?

Vou assumir que você não recebe arestas negativas ponderadas, porque isso pode não funcionar se houver pesos negativos.

Algoritmo

Para cada uma das suas arestas, identifique-as de a $1$$n$

Deixe peso Um número de borda $a_i$$i$

Seja peso B do número da aresta $b_i$$i$

Elabore esta tabela

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

Com cada um dos elementos da tabela sendo o produto de linha e coluna.

Para cada aresta, some a linha e a coluna relevantes da tabela (e lembre-se de remover o elemento na interseção, pois ele foi somado duas vezes).

Encontre a aresta que possui a maior soma e exclua-a se não desconectar o gráfico. Marque a borda como essencial caso contrário. Se uma aresta foi excluída, preencha suas linhas e colunas com 0.

Correção

O resultado é obviamente uma árvore.

O resultado está obviamente se estendendo desde que nenhum vértice está desconectado.

O resultado é mínimo? Se houver outra borda cuja exclusão criará uma árvore de abrangência menor no final do algoritmo, essa borda será excluída e anulada primeiro. (se alguém pudesse me ajudar a tornar isso um pouco mais rigoroso / e / ou contra-exemplo, isso seria ótimo)

Tempo de execução

Obviamente polinomial em .$|V|$

editar

nãoéum exemplo contrário.$(2,11), (11,2), (4,6)$

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

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

Então

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

é removido.$(11,2)$

Termine com $(2,11), (4,6) = 6 * 17 = 102$

Outras árvores abrangidas são

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

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

Esta é a solução em http://www.cnblogs.com/autsky-jadek/p/3959446.html .

Podemos visualizar todas as árvores de abrangência como um ponto no plano , onde x é a soma do peso ∑ e ∈ T A e , y é a soma do peso ∑ e ∈ T B e . O objetivo é minimizar x y .$x-y$$x$$\sum_{e\in T}A_{e}$$\sum_{e\in T}B_{e}$$xy$

1. $A$$B$$A,B$$A$$x$$B$$y$

2. $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})$. Now we run a maximum spanning tree on $G^{\prime}$ to get point $C$.

4. Run the above algorithm on $OBC, OAC$ recursively, until there is no more spanning trees between $BC,AC$ and $O$.

5. Now we get a set of possible spanning trees. Calculate $xy$ value for each tree to get the minimum tree.