Отбор ЮМШ

Рассмотрим граф с ребрами только веса (будем говорить о цене перелёта в тысячу рублей так, аналогично с весом Тогда в этом графе нет нечётных циклов. Следовательно, он является двудольным. Нам бы хотелось, что сумма стоимостей всех перелетов была минимальна, поэтому надо просто максимизировать количество единиц. Пусть в графе с ребрами веса всего вершин. Тогда в одной доле вершин, а в другой Тогда количество ребер между долями равно Следовательно, больше всего ребер между долями, когда в них одинаковое количество вершин или почти одинаковое, если — нечетно. Пусть Тогда возьмем две доли по вершин. Соединим любые две вершины из разных долей ребрами веса А все вершины в долях соединим ребрами веса Тогда между долями получим суммарный все а в долях Очевидно, что в этом примере все условия выполняются, так как проход по ребру с весом не влияет на четность веса маршрута и долю поменять мы не можем, пройдя по ребру с весом Следовательно, в сумме получаем Теперь пусть Тогда возьмем две доли с и вершинами. Тогда ребер между долями а ребер в долях Поэтому суммарный вес