Gráficos bipartidos com pesos mínimos
https://cs.stackexchange.com/questions/128045
-
29-09-2020 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho um gráfico bipartido completo com conjuntos de nó $ a={a_1, a_2, \ lDOTS, A_N \} $ e $ b={b_1, b_2, \ ldots, b_n \} $ . Cada nó tem um peso, $ v_i $ para $ a_i $ e $ w_i $ para $ b_i $ . Cada nó $ a_i $ está conectado a exatamente um nó de $ B $ , digamos $ b_j $ , através de uma borda $ E_I $ , cujo peso é $ \ min (v_i, w_j) $ . Agora eu quero encontrar um mapeamento um-para-um da $ a $ para $ B $ , cuja soma dos pesos da borda é o menor possível.
minha ideia é classificar $ v_i $ s cada vez mais e $ w_i $ s decrescentemente e, em seguida, encontrar A soma de todas as $ \ min (v_i, w_i) $ após a classificação. Está correto? Você pode dar uma prova / deseja?
Eu tenho apenas simulações de computador para $ n= 5,6, \ lDOTs, 10 $ com pesos de vértices aleatórios e não encontrou nenhum contraexemplo.
Solução
É bom que você tenha verificado sua ideia em algumas amostras aleatórias.
.
Para ver por que sua ideia funciona, vamos encontrar o caso mais simples, mas não-trivial e depois dar uma olhada nisso. Para simplicidade e Wlog, o peso de um nó será usado para denotar esse nó. Por exemplo, se $ a $ a $ contém um nó com peso $ 42 $ , esse nó será referido como Nó 42.
O caso de $ n= 1 $ é trivial.
Deixe $ n= 2 $ . Se acontecermos de olhar para $ a={1, 2 \} $ e $ b={3, 4 \} $ , então, no entanto, escolhemos o mapeamento, a soma será $ 1 + 2= 3 $ . Esta amostra aparentemente não é esclarecedor.
Como sobre $ a={1, 3 \} $ e $ b={2,4 \ } $ ?
- Se conectarmos 1 com 2 e 3 com 4, a soma é $ \ min (1,2) + \ min (3,4)= 1 + 3= 4 $ .
- Se conectarmos 1 com 4 e 3 com 2, a soma é $ \ min (1,4) + \ min (3,2)= 1 + 2= 3 $ .
Então, este é um exemplo não-trivial. Agora devemos fazer a pergunta básica, por que faz a segunda escolha produzir uma soma menor?
Para responder a pergunta, devemos observar como essas duas somas surgem. Note que 1 aparece em ambas as somas. Isso é coincidência? Pense por um momento e você saberá que não é. 1 é o número mínimo de todos os números. Então, tudo o que estiver conectado, ele será selecionado como o peso da conexão.
Isso significa que o número 1 está conectado, o que é 3 neste caso, esse número estará ausente de cálculos posteriores, isto é, será "desperdiçado". Quanto maior o "desperdício" é, quanto menos os números restantes serão e, portanto, quanto menos peso a conexão restante produzirá, já que a função $ \ min (\ Cdot, \ Cdot) $ < / Span> está diminuindo em relação a ambas as variáveis. Então 1 deve ser conectado a um número o mais grande possível. Que é por que 1 está conectado a 4 em vez de 3 de modo a produzir a soma total mínima.
No caso de $ n= 2 $ , existem apenas duas opções do mapeamento. O número menor na $ a $ é mapeado para o número menor em $ B $ , apelidado de "forward Mapeamento ", ou para o número maior em $ B $ , apelidado de" mapeamento reverso ". Para fazer o mapeamento produzir peso total menor, devemos sempre escolher o "mapeamento reverso", de modo que um grande número será desperdiçado (ou, o mesmo, um número menor será mantido a ser usado.)
.
Para provar que sua ideia está correta, mostramos que primeiro para qualquer mapeamento da $ a $ para $ b $ < / span>, há um mapeamento que mapeia $ \ min (A) $ para $ \ max (b) $ < / span> sem peso total maior. Suponha que o mapa $ F $ mapas $ \ min (a) $ para alguma mensagem $ b_J $ e algum número $ a_i $ para $ \ max (b) $ . Então podemos fazer outro mapa $ f '$ , que é o mesmo que $ F $ exceto para estes 4 Número, $ f '$ mapas $ \ min (A) $ para $ \ max (b) $ e $ a_i $ para $ b_j $ . Desde que, como mostramos acima, para quatro números $ \ min (a), a_i $ e $ b_j $ , $ \ max (b) $ , temos $$ \ min (\ min (A), \ max (b) + \ min (A_I, b_j) \ le \ min (\ min (A), b_j) + \ min (a_i, \ max (b)), $$ O peso total da $ f '$ não é maior que o da $ F $ .
para que sabemos,
- o peso total mínimo vem de um mapeamento que mapeia $ \ min (a) $ para $ \ max (b $ .
- para todos os mapeamentos que mapear $ \ min (A) $ para $ \ max (b) $ , o peso total mínimo vem, pelo mesmo argumento, um mapeamento que mapeia o mínimo dos números restantes em $ a $ (ou seja, o segundo número mínimo em < span class="recipiente de matemática"> $ a $ ) para o máximo dos números restantes na $ B $ (ou seja, o segundo número mínimo em $ B $ ).
- para todos os mapeamentos que mapeam
Uma prova ainda mais formal poderia ser dada. No entanto, o raciocínio acima pode ser mais fácil de entender. Deve, acredito, convencer um humano comum.
.
Aqui está outra maneira direta de provar sua ideia.
primeiro assumir que todos os números são distintos. Vamos provar por redutio ad absurdum. Suponha que o peso total mínimo possa ser alcançado por um mapeamento $ g $ diferente do mapeamento descrito em sua ideia. Então $ g $ deve conter um sub-mapeamento que é um "mapeamento para frente", ou seja, deve haver dois números $ \ Alfa_1 \ lt \ alpha_2 $ em $ a $ e dois números $ \ beta_1 \ lt \ beta_2 $ em $ b $ tal que $ g (\ alpha_1)=beta_1 $ e < span class="contentor de matemática"> $ g (\ alpha_2)=beta_2 $ .
Agora podemos fazer outro mapeamento $ g '$ que é o mesmo que $ g $ em todos os lugares mais, exceto que o sub-mapeamento de $ g '$ em $ \ alfa_1 $ e $ \ Alpha_2 $ é um "mapeamento reverso", ou seja, $ g '(\ alpha_1)=beta_2 $ e < span class="contentor de matemática"> $ g '(\ alpha_2)=beta_1 $ . Agora podemos, como antes, verifique se o peso total da $ g '$ é menor que o da $ g $ < / span>, que contradiz a nossa suposição.
Se todos os números não forem distintos, usaremos a técnica de aproximação por limite. Perturbar todos os números ligeiramente para que eles se tornem distintos. Agora todos os pesos serão ligeiramente fora de seus pesos originais. Isso significa que o peso total obtido da sua ideia não deve estar longe da solução ideal. Deixe a perturbação ir para zero, vemos que é, de fato, a solução ideal.
.
Você pode estar interessado em um problema semelhante, Como provar o algoritmo ganancioso que minimiza a soma máxima de um emparelhamento .
Outras dicas
Eu acho que a melhor solução aqui é usar o algoritmo de fluxo máximo de custo mínimo neste gráfico.Se você não sabe disso, vá e leia sobre isso.Este algoritmo é a solução mais clássica para esse tipo de problema.
