Gráficos bipartitos con pesos mínimos.
https://cs.stackexchange.com/questions/128045
-
29-09-2020 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Tengo un gráfico bipartito completo con conjuntos de nodos $ a={A_1, A_2, \ LDOTS, A_N \} $ y $ b={b_1, b_2, \ ldots, b_n \} $ . Cada nodo tiene un peso, $ v_i $ para $ a_i $ y $ W_I $ para $ b_i $ . Cada nodo $ A_I $ está conectado a exactamente un nodo de $ b $ , digamos $ b_j $ , a través de un borde $ e_i $ , cuyo peso es $ \ min (v_i, w_j) $ . Ahora quiero encontrar un mapeo uno a uno de $ a $ a $ b $ , cuyo La suma de pesos de borde es lo más pequeña posible.
Mi idea es ordenar $ v_i $ s cada vez más y $ w_i $ s disminuyendo y luego encuentra La suma de todos los $ \ min (v_i, w_i) $ después de la clasificación. ¿Es correcto? ¿Puedes dar una prueba / impermeable?
He ejecutado simulaciones de computadora para $ n= 5,6, \ ldots, 10 $ con pesos de vértices aleatorios y no encontramos un contraejemplo.
Solución
Es bueno que haya revisado su idea en algunas muestras aleatorias.
Para ver por qué funciona su idea, encontremos el caso más simple pero no trivial y luego echemos un vistazo. Para simplificar y Wlog, el peso de un nodo se utilizará para denotar ese nodo. Por ejemplo, si $ A $ contiene un nodo con peso $ 42 $ , ese nodo será referido al nodo como Nodo 42.
El caso de $ n= 1 $ es trivial.
Let $ n= 2 $ . Si sucede a mirar a $ a={1, 2 \} $ y $ b={3, 4 \} $ , sin embargo, elegimos la asignación, la suma será $ 1 + 2= 3 $ . Esta muestra aparentemente no es iluminadora.
¿Qué tal $ a={1, 3 \} $ y $ b={2,4 \ } $ ?
- Si nos conectamos 1 con 2 y 3 con 4, la suma es $ \ min (1,2) + \ min (3,4)= 1 + 3= 4 $ .
- Si nos conectamos 1 con 4 y 3 con 2, la suma es $ \ min (1,4) + \ min (3,2)= 1 + 2= 3 $ .
Entonces este es un ejemplo no trivial. Ahora debemos hacer la pregunta básica, por qué hace la segunda opción produce una suma más pequeña?
Para responder a la pregunta, debemos observar cómo surgen dos sumas. Tenga en cuenta que 1 aparece en ambas sumas. ¿Es esa coincidencia? Piensa por un momento y lo sabrás, no lo es. 1 es el número mínimo de todos los números. Entonces, lo que sea conectado, se seleccionará como el peso de la conexión.
Eso significa, en el que se conecte el número 1, que es 3 en este caso, ese número faltará en cálculos posteriores, es decir, se "desperdiciará". Cuanto más grande sea el "desecho", cuanto menos los números restantes serán y, por lo tanto, menos peso producirá la conexión restante, ya que la función $ \ min (\ cdot, \ cdot) $ < / SPAN> está disminuyendo con respecto a ambas variables. Así que 1 debe estar conectado a un número lo más grande posible. Eso es por qué 1 está conectado a 4 en lugar de 3 para producir la suma total mínima.
En el caso de $ n= 2 $ , solo hay dos opciones del mapeo. Ya sea el número más pequeño en $ a $ se asigna al número más pequeño en $ b $ , dobló " Mapeo ", o al número más grande en $ b $ , doblado" Mapeo inverso ". Para hacer que el mapeo produzca un peso total más pequeño, siempre debemos elegir la "asignación inversa", de modo que se desperdicie un gran número (o, qué es lo mismo, se seguirá utilizando un número más pequeño).
Para probar que su idea es correcta, primero mostramos que para cualquier asignación de $ a $ a $ b $ < / span>, hay un mapeo que mapea $ \ min (a) $ a $ \ max (b) $ < / SPAN> sin mayor peso total. Supongamos que map $ f $ maps $ \ min (a) $ a algunos $ b_j $ y algunos números $ a_i $ a $ \ max (b) $ . Luego podemos hacer otro mapa $ f '$ , que es el mismo que $ f $ excepto para estos 4 Número, $ f '$ maps $ \ min (a) $ a $ \ max (b) $ y $ a_i $ a $ b_j $ . Desde entonces, como lo hemos mostrado anteriormente, para cuatro números $ \ min (a), a_i $ y $ b_j $ , $ \ max (b) $ , tenemos $$ \ min (\ min (a), \ max (b)) + \ min (a_i, b_j) \ le \ min (\ min (a), b_j) + \ MIN (A_I, \ max (b)), $$ El peso total de $ f '$ no es mayor que el de $ f $ .
Entonces lo sabemos,
- El peso total mínimo proviene de una asignación que mapea $ \ min (a) $ a $ \ max (b ) $ .
- Para todas las asignaciones que mappes $ \ min (a) $ a $ \ max (b) $ , el peso total mínimo proviene de, por el mismo argumento, un mapeo que asigna el mínimo de los números restantes en $ a $ (es decir, el segundo número mínimo en < span class="Math-contenedor"> $ A $ ) al máximo de los números restantes en $ b $ (es decir, el segundo número mínimo en $ b $ ).
- para todas las asignaciones que mapea
Se podría dar una prueba aún más formal. Sin embargo, el razonamiento anterior podría ser más fácil de entender. Debería, creo, convencer a un humano ordinario.
Aquí hay otra manera directa de demostrar su idea.
Supongamos primero que todos los números son distintos. Permítanos demostrar por Reductio ad absurdum. Supongamos que se puede alcanzar el peso total mínimo mediante un mapeo $ g $ que no sea el mapeo descrito en su idea. Luego, $ G $ debe contener una subestimación que es un "mapeo hacia adelante", es decir, debe haber dos números $ \ alfa_1 \ lt \ alfa_2 $ en $ a $ y dos números $ \ beta_1 \ lt \ beta_2 $ en $ b $ tal que $ g (\ alfa_1)=beta_1 $ y < Span Class="Math-contenedor"> $ g (\ alfa_2)=beta_2 $ .
Ahora podemos hacer otro mapeo $ g '$ que es el mismo que $ g $ en todas partes más, excepto que la sub-mapeo de $ g '$ en $ \ alfa_1 $ y $ \ alfa_2 $ es una "asignación inversa", es decir, $ g '(\ alfa_1)=beta_2 $ y < Span Class="Math-contenedor"> $ g '(\ alfa_2)=beta_1 $ . Ahora podemos, como antes, verifique que el peso total de $ g '$ es más pequeño que el de $ g $ < / Span>, que contradice nuestro supuesto.
Si todos los números no son distintos, usaremos la técnica de acercamiento por límite. Perturbó a todos los números ligeramente para que se vuelvan distintos. Ahora todos los pesos estarán ligeramente fuera de sus pesos originales. Eso significa que el peso total obtenido de su idea no debe estar lejos de la solución óptima. Deja que la perturbación vaya a cero, vemos que, de hecho, es la solución óptima.
Puede estar interesado en un problema similar, Cómo demostrar el algoritmo codicioso que minimiza la suma máxima de un emparejamiento .
Otros consejos
Creo que la mejor solución aquí está utilizando el algoritmo de flujo máximo de costo mínimo en este gráfico.Si no lo sabes, ve y lee.Este algoritmo es la solución más clásica para este tipo de problema.
