Задача
COM-B2-M05-P013 Критерий для знаков на связном графе
На вершинах связного графа стоят знаки \(+\) и \(-\). За ход можно выбрать ребро и поменять знаки в обеих его концах. Докажите, что все знаки можно сделать положительными тогда и только тогда, когда в начальном положении число отрицательных знаков чётно.
Необходимость даёт произведение знаков. Для достаточности используйте остовное дерево и убирайте отрицательные знаки с листьев.
Необходимость: один ход меняет два знака, поэтому чётность числа отрицательных знаков сохраняется. Если в конце отрицательных знаков \(0\), то в начале их должно быть чётное число.
Докажем достаточность. Возьмём остовное дерево графа и выберем в нём корень. Будем обрабатывать листья, кроме корня. Если в листе стоит минус, применим ход к ребру, соединяющему лист с его родителем; знак в листе станет плюсом, а знак родителя изменится. Если в листе плюс, ничего не делаем. После этого лист можно больше не трогать.
Так мы сделаем положительными все вершины, кроме, возможно, корня. Чётность числа отрицательных знаков сохранялась, а перед последним шагом вне корня отрицательных знаков нет. Поэтому корень тоже положителен. Значит, все знаки можно сделать положительными.
Сильная задача: кроме инварианта требуется конструктивная достаточность.