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

Решение: Представим куб как граф, где вершины куба - это вершины графа, а ребра куба - это ребра графа. Добавление диагоналей на противоположных гранях увеличивает степень некоторых вершин. Наша задача - минимизировать число кусков проволоки, что эквивалентно минимизации числа связных компонент после разрезания проволоки в вершинах. У куба 8 вершин. С двумя диагоналями у нас есть 4 вершины степени 3 (исходные вершины куба) и 4 вершины степени 4 (вершины, где сходятся диагонали). Сумма степеней всех вершин равна (4 imes 3 + 4 imes 4 = 12 + 16 = 28). Для связного графа (один кусок проволоки) число ребер (E) и вершин (V) связано неравенством (E ge V - 1). В нашем случае мы хотим, чтобы количество кусков проволоки (связных компонент) было минимальным. Если у нас (k) кусков, то (E ge V - k). Изначально у куба 12 ребер + 2 диагонали = 14 ребер. Таким образом, (E = 14) и (V = 8). (14 ge 8 - k), следовательно, (k ge 8 - 14 = -6). Это не имеет смысла, так как (k) должно быть положительным. Теперь рассмотрим степени вершин. Если бы все вершины имели степень 2, то можно было бы обойтись одним куском проволоки (замкнутая цепь). Однако у нас есть вершины степени 3 и 4. Чтобы минимизировать количество кусков, нужно максимизировать количество вершин, соединенных одним куском проволоки. Поскольку у нас есть вершины степени 4, нам потребуется как минимум **2** куска проволоки. Чтобы в каждой вершине сходилось четное число ребер. Ответ: **2**