Контрольные задания > 3. Можно ли соединить 8 городов дорогами так, чтобы из трёх городов выходило по три дороги, а из оставшихся пяти городов по четыре дороги? Нарисуйте пример подходящего графа или объясните, почему это невозможно.
Вопрос:

3. Можно ли соединить 8 городов дорогами так, чтобы из трёх городов выходило по три дороги, а из оставшихся пяти городов по четыре дороги? Нарисуйте пример подходящего графа или объясните, почему это невозможно.

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

Ответ:

Невозможно. По теореме о рукопожатиях, сумма степеней всех вершин должна быть чётной. В данном случае сумма степеней равна (3 * 3) + (5 * 4) = 9 + 20 = 29, что является нечётным числом.
ГДЗ по фото 📸
Подать жалобу Правообладателю

Похожие