1) Между планетами Солнечной системы установлено сообщение. Ракеты летают по следующим маршрутам: Земля - Плутон, Плутон - Меркурий, Плутон - Венера, Земля - Меркурий, Венера - Уран, Нептун - Сатурн, Сатурн - Юпитер, Юпитер - Марс и Марс - Уран. Можно ли добраться с Земли до Марса? Изобразите граф.

Привет! Давай разберем задачи по теории графов. ### Задача 1 Список маршрутов: - Земля — Плутон - Плутон — Меркурий - Плутон — Венера - Земля — Меркурий - Венера — Уран - Нептун — Сатурн - Сатурн — Юпитер - Юпитер — Марс - Марс — Уран Давай посмотрим на связи: 1. Связная компонента 1: Земля — Плутон — Меркурий — Венера — Уран — Марс — Юпитер — Сатурн — Нептун. (Все эти планеты связаны между собой). 2. Как видим, путь существует: Земля — Плутон — Венера — Уран — Марс. **Ответ:** Да, добраться можно. ### Задача 2 Для решения используем **Лемму о рукопожатиях**: сумма степеней всех вершин графа равна удвоенному количеству ребер ($2|E| = \sum \deg(v)$). - Количество вершин (компьютеров) $n = 15$. - Степень каждой вершины $k = 5$ (каждый компьютер соединен с 5 другими). - Сумма степеней = $15 \times 5 = 75$. - По лемме, сумма степеней должна быть четным числом ($2|E|$), так как каждое ребро соединяет 2 вершины. - Число 75 — нечетное. Значит, такого графа существовать не может. **Ответ:** Нет, это невозможно. ### Задача 3 Используем ту же формулу: - Количество городов $n = 240$. - Степень каждой вершины $k = 3$. - Сумма степеней = $240 \times 3 = 720$. - Количество дорог (ребер) равно $\frac{\text{Сумма степеней}}{2} = \frac{720}{2} = 360$. **Ответ:** Всего 360 дорог. ### Задача 4 В теории графов есть правило: если из каждой вершины выходит четное число ребер (как в задаче — по 2 дороги), то граф является эйлеровым или представляет собой совокупность эйлеровых циклов. Если граф связный, то в нем существует Эйлеров цикл, который проходит по всем ребрам ровно один раз. Так как из каждого города выходит по 2 дороги, это условие выполняется (граф является 2-регулярным). **Ответ:** Да, это возможно, так как граф представляет собой набор циклов, и при связности можно обойти все пути.