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

Решение:

Для решения задачи построим граф, где планеты — это вершины, а маршруты — это ребра.

• Вершины: Земля (З), Меркурий (М), Марс (Марс), Венера (В), Уран (У), Нептун (Н), Сатурн (С), Юпитер (Ю), Плутон (П).
• Ребра (маршруты): (З, М), (Марс, М), (Марс, В), (У, Н), (Ю, П), (М, В), (Н, С), (С, Ю), (П, У).

Теперь посмотрим, есть ли путь от Земли до Плутона:

1. Из Земли можно попасть только на Меркурий: З → М.
2. Из Меркурия можно попасть на Марс или Венеру: З → М → Марс или З → М → В.
3. Из Марса можно попасть на Венеру: З → М → Марс → В.
4. Из Венеры нет прямых маршрутов.
5. Из других планет (Уран, Нептун, Сатурн, Юпитер, Плутон) создается отдельная группа маршрутов: У ↔ Н ↔ С ↔ Ю ↔ П ↔ У.

Как видно, нет ни одного маршрута, соединяющего группу {Земля, Меркурий, Марс, Венера} с группой {Уран, Нептун, Сатурн, Юпитер, Плутон}.

Изображение графа:

Ответ: Нет, добраться с Земли до Плутона невозможно.