Бипартитные графики с минимальными весами
https://cs.stackexchange.com/questions/128045
-
29-09-2020 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня есть полный двусторонний график с установками узлов $ a={a_1, a_2, \ ldots, a_n \} $ и $ b={b_1, b_2, \ ldots, b_n \} $ . Каждый узел имеет вес, $ v_i $ для $ a_i $ и $ b_i $ . Каждый узел $ a_i $ подключен к одному узлу $ B $ , скажем, $ b_j $ , через край $ E_I $ , вес которого $ \ mom (v_i, w_j) $ . Теперь я хочу найти однозначное отображение из $ a $ на $ b $ , чьи Сумма тяжелых весов как можно меньше.
Моя идея - сортировать $ v_i $ s все чаще и $ w_i $ s Сумма всех $ \ min (v_i, w_i) $ после сортировки. Это правильно? Можете ли вы дать доказательство / диспецитную защиту?
У меня запустите компьютерные моделирования для $ n= 5,6, \ ldot, 10 $ со случайной весом вершины и не нашли контрпример.
Решение
Приятно, что вы проверили свою идею на случайных образцах.
понять, почему ваша идея работает, давайте найдем простейший, но нетривиальный случай, а затем посмотрите на него. Для простоты и WLOG вес узла будет использоваться для обозначения этого узла. Например, если $ a $ содержит узел с весом $ 42 $ , этот узел будет называться Узел 42.
Корпус $ n= 1 $ тривиально.
Пусть $ n= 2 $ . Если мы бы посмотрим на $ a={1, 2 \} $ и $ b={3, 4 \} $ , однако, однако мы выбираем сопоставление, сумма будет $ 1 + 2= 3 $ . Этот образец, по-видимому, не просвещается.
Как насчет $ a={1, 3 \} $ и $ b={2,4 \ } $ ?
- .
- Если мы подключаем 1 с 2 и 3 с 4, сумма - $ \ min (1,2) + \ min (3,4)= 1 + 3= 4 $ .
- Если мы подключаем 1 с 4 и 3 с 2, сумма составляет $ \ min (1,4) + \ min (3,2)= 1 + 2= 3 $ .
Так это нетривиальный пример. Теперь мы должны задать основной вопрос,
Чтобы ответить на вопрос, мы должны наблюдать, как придумывают эти две суммы. Обратите внимание, что 1 появляется в обеих суммах. Это совпадение? Подумайте на мгновение, и вы узнаете, что это не так. 1 - минимальное количество всех чисел. Так что, что он подключен к, он будет выбран в качестве веса соединения.
Это означает, что все, к чему не подключено число 1, что 3 в этом случае, то число будет отсутствовать от последующих вычислений, то есть он будет «потрачен». Чем больше «отходы», тем меньше остальные числа будут и, следовательно, чем меньше веса, остальное соединение будет производить, поскольку функция $ \ min (\ cdot, \ cdot) $ < / span> уменьшается по отношению к обеим переменным. Так что 1 должно быть подключено к числу как можно больше. Это почему 1 подключено к 4 вместо 3, чтобы произвести минимальную общую сумму.
В случае $ n= 2 $ , есть только два варианта сопоставления. Либо меньшее число в $ a $ сопоставлено на меньшее число в $ B $ , judbed отображение », или к большему количеству в $ B $ , назвала« обратное отображение ». Чтобы создать сопоставление меньшего объема общего веса, мы всегда должны выбирать «обратное отображение», так что большое количество будет потрачено впустую (или то, что одинаково, будет использоваться меньшее число.)
Чтобы доказать, что ваша идея верна, мы сначала покажем, что для любого сопоставления от $ a $ на $ B $ < / span>, есть отображение, которое отображает отображение $ \ min (a) $ на $ \ max (b) $ < / span> без большего общего веса. Предположим, что карта $ F $ Карты $ \ min (a) $ на некоторые
Итак, мы знаем,
- .
- Минимальный общий вес исходит из сопоставлений, которые отображаются $ \ min (a) $ на $ \ max (b ) $ .
- для всех отображений, которые отображают $ \ min (a) $ $ \ max (b) $ Минимальный общий вес происходит, по тому же аргументу, сопоставлением, которое отображает минимум оставшихся чисел в $ a $ (то есть второе минимальное число в < SPAN CLASS= «Математический контейнер»> $ a $ ) до максимума оставшихся номеров в $ B $ (т. Е. Второе минимальное количество в $ b $ ).
- для всех отображений, которые отображают
Еще более формальное доказательство может быть дано. Однако вышеупомянутые рассуждения могут быть легче понять. Это, я полагаю, убедив обычный человек.
Вот еще один простой способ доказать свою идею.
Первый полагать, что все номера отличаются. Докажем, Reductio Ad Absurdum. Предположим, что минимальный общий вес может быть достигнут с помощью сопоставления $ G $ , кроме сопоставления, описанного в вашей идее. Тогда $ G $ должен содержать подставку, который является «форвардным сопоставлением», т. Е. Должно быть два числа $ \ alpha_1 \ lt \ alpha_2 $ в $ a $ и два числа $ \ beta_1 \ lt \ beta_2 $ в $ b $ такой, что $ g (\ alpha_1)=beta_1 $ и < Spaness Class= «Математический контейнер»> $ G (\ alpha_2)=beta_2 $ .
Теперь мы можем сделать еще одно сопоставление $ G '$ , что такое же, как $ G $ везде Кроме того, за исключением того, что подкапорение $ g '$ on $ \ alpha_1 $ и $ \ alpha_2 $ - это «обратное отображение», то есть $ G '(\ alpha_1)=beta_2 $ и < Spant Class="Math-Container"> $ g '(\ alpha_2)=beta_1 $ . Теперь мы можем, как и прежде, подтвердить, что общий вес $ g '$ меньше, чем у $ G $ < / span>, что противоречит нашему предположению.
Если все номера не отличаются, мы будем использовать технику приближения к пределью. Слегка возвышать все числа, чтобы они были отличными. Теперь все веса будут немного от их оригинальных весов. Это означает, что общий вес, полученный от вашей идеи, не должен быть далеко от оптимального решения. Пусть возмущение идет к нулю, мы видим, что на самом деле это оптимальное решение.
Вы можете быть заинтересованы в аналогичной проблеме, Как доказать жадный алгоритм, который минимизирует максимальную сумму сопряжения .
Другие советы
Я думаю, что лучшее решение здесь использует алгоритм Min-Charge Max-Flow на этом графике.Если вы не знаете об этом, иди и прочитайте об этом.Этот алгоритм является наиболее классическим решением для этой проблемы.
