11 На рисунке показан абажур, изготовленный из стальной проволоки. Какое наименьшее количество кусков проволоки нужно, чтобы изготовить абажур, показанный на рисунке?
\square
| μltirow[b]{2}{*}{Ответ:} | |||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \square | \square | \square | \square | \square | |||||||||||||||||||||||||||
| \square | \square | \square | \square | \square | \square | \square |
Мы покажем, что при оптимальном соединении всех «отрезков» рисунка получаем схему, которую можно разбить на 4 непрерывных «линию». Другими словами, изготовить абажур можно, используя всего 4 куска проволоки.
Ниже приведён пошаговый анализ, как можно прийти к такому выводу.
────────────────────────────── Шаг 1. Переформулировка задачи в терминах графа
Абажур, выполненный из проволоки, можно рассматривать как рисунок (граф) с узлами (точками перегиба и соединениями) и отрезками (проволоковыми элементами). Нам нужно «разложить» этот граф на минимальное число непрерывных кусков проволоки. Кажды...