Тип 11 Из стальной проволоки требуется изготовить абажур заданных размеров, используя наименьшее количество проволоки.

Для решения задач на определение наименьшего количества кусков проволоки (отрезков), из которых можно составить заданный каркас, нужно найти количество ребер в графе, которые можно провести «не отрывая руки» (одним куском проволоки), а затем учесть узлы (вершины), где сходятся несколько ребер. По правилу: 1 кусок проволоки — это одно ребро или непрерывная ломаная (несколько ребер подряд). Сваривать можно в вершинах. ### Задача 1 На рисунке изображен каркас, состоящий из: - Треугольника сверху (3 ребра). - Дугообразных элементов снизу (3 дуги, соединяющие боковые стороны). - Боковых сторон (2 стороны, каждая из которых состоит из 3 отрезков). В этой задаче каждый сегмент между двумя узлами можно считать отдельным куском, если мы хотим сварить их в узлах, либо стараться провести линию дальше. Однако по классике таких задач, если проволоку можно гнуть и варить, то каждый непрерывный путь — это 1 кусок. В «лодочке» все узлы имеют четную или нечетную степень. Если вершина имеет нечетную степень, в ней должен начинаться или заканчиваться отрезок. Здесь проще всего посчитать количество "ветвей". Ответ: 7 кусков проволоки. ### Задача 2 На рисунке изображен икосаэдр (или подобный многогранник). Для того чтобы найти минимальное количество кусков проволоки, нужно определить количество ребер графа, которые нельзя объединить в одну непрерывную линию без разрыва. В подобных геометрических задачах для пространственных каркасов минимальное число кусков проволоки равно количеству ребер минус количество "лишних" соединений, которые можно было бы провести одной линией. Но так как это пространственный каркас и нам нужно сваривать их в узлах: 1. Икосаэдр имеет 30 ребер. 2. В каждой вершине сходятся 5 ребер. Поскольку степень каждой вершины нечетная (5), из каждой вершины должен выходить "конец" куска проволоки. В графе с $V$ вершинами, где каждая вершина имеет нечетную степень $k$, минимальное число путей (кусков) равно $V / 2$ (так как каждый путь соединяет две нечетные вершины). У икосаэдра 12 вершин. Ответ: 6 кусков проволоки.