ГДЗ 11 Опираясь на теорию графов решите задачу. Из медной проволоки нужно спаять плоское украшение заданных размеров...
11
Опираясь на теорию графов решите задачу.
Из медной проволоки нужно спаять плоское украшение заданных размеров (см. рисунок), затратив наименьшее возможное количество проволоки. Проволоку можно гнуть под любым углом и спаивать в точках соединения. Какое наименьшее количество кусков проволоки потребуется?
Решение:
Для решения задачи воспользуемся теорией графов. Представим украшение как граф, где точки соединения — это вершины, а линии и дуги — рёбра.
-
Условие минимального количества проволоки: Чтобы затратить минимум материала, мы не должны проходить по одной и той же линии дважды. Это означает, что нам нужно найти минимальное количество непрерывных путей, которыми можно покрыть все рёбра графа без повторений.
-
Теорема: Согласно теории графов, связный граф можно начертить, не отрывая руки и не проводя по одной линии дважды, если в нём 0 или 2 нечётные вершины (вершины, из которых выходит нечётное количество линий). Если в графе $2k$ нечётных вершин (где $k > 1$), то минимальное количество непрерывных линий, необходимых для его покрытия, равно $k$.
-
Анализ вершин графа на рисунке:
- Точка соединения хвоста и туловища (слева): из неё выходит петля хвоста (2 конца), линия спины (1) и линия позвоночника (1). Итого 4 линии — чётная вершина.
- Кончики ушей (2 точки): из каждого выходит по 1 линии. Итого 2 вершины со степенью 1 — нечётные.
- Основание левого уха: соединяет линию спины, линию уха и две дуги головы. Итого 4 линии — чётная вершина.
- Основание правого уха: соединяет линию уха и две дуги головы. Итого 3 линии — нечётная вершина.
- Левая точка головы (примыкание позвоночника): соединяет линию позвоночника и две дуги головы. Итого 3 линии — нечётная вершина.
- Остальные точки на голове (снизу и справа): имеют степень 2 (соединяют две дуги). Итого 2 чётные вершины.
-
Подсчёт: Всего в графе 4 нечётные вершины (два кончика ушей, основание правого уха и левая точка головы). Следовательно, $2k = 4$, откуда $k = 2$.
Для того чтобы изготовить такое украшение без лишних затрат проволоки (без нахлёстов), потребуется минимум 2 куска проволоки.
Ответ: 2