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

12

Considere um gráfico G(V,E) . Cada aresta e tem dois pesos Ae e Be . Encontrar uma árvore geradora que minimiza o produto (eTAe)(eTBe) . 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?

Strin
fonte
Talvez tente construir um novo gráfico, onde o peso de uma aresta e é max(Ae,Be) .
utdiscant
3
Este é um problema / exercício de lição de casa? Se sim, é de um livro? A razão pela qual pergunto é que o contexto pode ajudar a "fazer engenharia reversa" do problema. Não é imediatamente óbvio que um algoritmo guloso é apropriado aqui, mas se ele vem do capítulo sobre algoritmos gulosos ...
Joe
1
@utdiscant, isso não vai funcionar. Bordas negativas podem ser úteis.
Nicholas Mancuso
mesmo para bordas positivas não é útil, por exemplo, o par (10,10) não é melhor que o par (11,1) na maioria dos casos.

Respostas:

1

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 n1n

Deixe peso Um número de borda iaii

Seja peso B do número da aresta ibii

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)

a1=2,a2=11,a3=4

b1=11,b2=2,b3=6

Então

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

(4,6)=44+8+24+66+12=154(2,11)=22+4+12+121+44=203(11,2)=121+22+66+4+8=221

é removido.(11,2)

Termine com (2,11),(4,6)=617=102

Outras árvores abrangidas são

(11,2),(4,6)=1512=180

(2,11),(11,2)=1313=169

Herp Derpington
fonte
1
Parece-me que esta é uma abordagem bastante gananciosa. Não estou convencido de sua "prova" de minimalismo.
Nejc
1
@SaeedAmiri Como isso é um exemplo de contador? Postei o trabalho na seção editada, o algoritmo dá o resultado correto.
amigos estão dizendo sobre herp derpington
1
O que você fez foi descobrir quanto cada contribui em e E a i . Σ e E b i , e você escolhe os que têm o maior impacto. Isso é bom, mas não é o necessário. É uma pergunta complicada. Se você quiser melhorar sua resposta, precisará de uma prova. Caso contrário, não há uso. (ai,bi)eEai.eEbi
AJed
é muito injusto obter um voto negativo pelo seu esforço.
AJed
@AJed A prova é igual à da exclusão prim / kush / reverse. Tudo o que temos de provar agora é que a propriedade de corte ainda é válida.
Herp Derpington
1

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 .xyxeTAeeTBexy

  1. ABA,BAxBy

  2. COABABxyCABC

2SABC=|AB×AC|=(BxAx,ByAy)×(CxAx,CyAy)=(BxAx)Cy+(AyBy)CxAy(BxAx)+Ax(ByAy)

  1. Ay(BxAx)+Ax(ByAy(BxAx)Cy+(AyBy)CxG=(V,E)w(e)=Be(BxAx)+Cx(AyBy). Now we run a maximum spanning tree on G to get point C.

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

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


fonte