Из декоративной проволоки нужно спаять плоское украшение в виде листка заданных размеров (см. рисунок), затратив наименьшее возможное количество проволоки. Проволоку можно гнуть под любым углом и спаивать в точках соединения. Какое наименьшее количество кусков проволоки нужно, чтобы изготовить модель, показанную на рисунке?
Рассмотрим каждый кусок проволоки как путь в графе. Если он начинается и заканчивается в разных вершинах, то он содержит нечетное число ребер, исходящих из этих вершин и четное число ребер, исходящих из любой другой вершины (все они разбиваются на пары входящее-исходящее ребро кроме первого и последнего). Если в одной и той же — то для нее число вершин также будет четно. Значит, любая вершина нечетной степени должна служить началом или концом минимум одного из таких путей. Значит, их количество не меньше 5 : 2 = 2,5 (есть 7 вершин нечетной степени. Каждый путь имеет не более двух концов). То есть их количество равно 3.
Ответ: 3.
-------------
Дублирует задание № 12126.