Вопрос:

В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?
Фотография

Ответ ассистента

17. Сумма степеней всех вершин графа равна количеству рёбер, умноженному на 2 (по лемме о рукопожатиях). В нашем случае: 15 телефонов × 5 соединений = 75. Число 75 нечётное, поэтому построить такой граф невозможно. Ответ: Нет. 18. Пути, проходящие через город В, обязательно начинаются с отрезка А → В. Посчитаем варианты движения из В в И: 1) В → Е → Ж → И 2) В → Е → И 3) В → Ж → И Всего существует 3 пути. Ответ: 3. 19. В такой системе граф может оказаться несвязным (вершины чётной степени могут образовывать отдельные замкнутые циклы, не соединённые со столицей и городом Дальний). Поэтому гарантировать наличие пути из столицы в Дальний нельзя. Ответ: Нет.

Другие решения

Что ещё задавали пользователи