Вопрос:

11 Опираясь на теорию графов решите задачу. Из медной проволоки нужно спаять плоское украшение заданных размеров (см. рисунок), затратив наименьшее возможное количество проволоки. Проволоку можно гнуть под любым углом и спаивать в точках соединения. Какое наименьшее количество кусков проволоки потребуется?

Смотреть решения всех заданий с листа

Ответ:

1. Украшение представляет собой граф, где точки соединения - вершины, а отрезки проволоки - ребра.
2. Для создания фигуры из наименьшего количества кусков проволоки необходимо пройти по каждому ребру ровно один раз. Это задача о поиске Эйлерова пути или цикла.
3. В данном графе все вершины имеют четную степень (кроме двух вершин, которые являются началом и концом 'хвоста' кошки, имеющих нечетную степень). Следовательно, для прохождения всех ребер потребуется 2 куска проволоки (по одному для каждой нечетной вершины).
ГДЗ по фото 📸
Подать жалобу Правообладателю

Похожие