ГДЗ 11 Из декоративной проволоки нужно спаять плоское украшение в виде листка заданных размеров (см. рисунок), затрат...
11 Из декоративной проволоки нужно спаять плоское украшение в виде листка заданных размеров (см. рисунок), затратив наименьшее возможное количество проволоки. Проволоку можно гнуть под любым углом и спаивать в точках соединения. Какое наименьшее количество кусков проволоки нужно, чтобы изготовить модель, показанную на рисунке?
Для решения этой задачи воспользуемся теорией графов. Модель листка можно представить как связный граф, где линии — это рёбра, а точки их пересечения и свободные концы — вершины.
Минимальное количество непрерывных кусков проволоки (путей), необходимых для того, чтобы изготовить такой граф, не проходя по одному и тому же ребру дважды (чтобы минимизировать расход материала), вычисляется по формуле:
$$
k = \frac{N_{\text{нечёт}}}{2}
$$
где $N_{\text{нечёт}}$ — количество вершин с нечётной степенью (то есть точек, в которых сходится нечётное количество линий).
Проанализируем вершины графа на рисунке:
- Кончик черенка (стебля): это свободный конец, здесь сходится только 1 линия. Степень вершины — 1 (нечётная).
- Центральная точка листка: здесь сходятся 5 внутренних жилок, идущих к лопастям, и 1 линия черенка. Итого 6 линий. Степень вершины — 6 (чётная).
- Кончики пяти лопастей листка: в каждой такой точке сходятся 2 линии внешнего контура и 1 внутренняя жилка. Итого 3 линии. У нас 5 таких вершин, степень каждой — 3 (нечётная).
- Точки «впадин» между лопастями: здесь сходятся только 2 линии контура. Степень таких вершин — 2 (чётная).
Подсчитаем общее количество нечётных вершин:
$$
N_{\text{нечёт}} = 1 \text{ (черенок)} + 5 \text{ (кончики лопастей)} = 6
$$
Следовательно, минимальное количество кусков проволоки равно:
$$
k = \frac{6}{2} = 3
$$
Ответ: 3.