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

Решение:

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

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

Маршруты (ребра):

• Земля <-> Меркурий
• Плутон <-> Венера
• Меркурий <-> Плутон
• Меркурий <-> Венера
• Уран <-> Нептун
• Сатурн <-> Юпитер
• Марс <-> Марс (это не маршрут, а ошибка в условии, игнорируем)
• Марс <-> Уран

Цель: Найти кратчайший путь (минимальное число рейсов) от Земли до Юпитера.

Построим возможные пути от Земли:

1. Земля (0 рейсов)
2. Земля -> Меркурий (1 рейс)
3. Из Меркурия можно попасть:
   • Земля -> Меркурий -> Плутон (2 рейса)
   • Земля -> Меркурий -> Венера (2 рейса)
4. Из Плутона можно попасть:
   • Земля -> Меркурий -> Плутон -> Венера (3 рейса)
5. Из Венеры можно попасть:
   • Земля -> Меркурий -> Венера -> Плутон (3 рейса)
   • Земля -> Меркурий -> Плутон -> Венера (3 рейса)

Проанализируем доступные маршруты к Юпитеру:

• Единственный прямой маршрут, ведущий к Юпитеру, это Сатурн <-> Юпитер.
• Значит, нам нужно сначала добраться до Сатурна.

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

Смотрим на все планеты, с которыми связаны маршруты:

• Земля
• Меркурий
• Плутон
• Венера
• Уран
• Нептун
• Марс
• Юпитер

Обратите внимание: в списке маршрутов отсутствует какая-либо связь с планетой Сатурн, кроме как до Юпитера. Это означает, что попасть на Сатурн из других планет (кроме Юпитера) невозможно по указанным маршрутам.

Вывод:

Исходя из предоставленных маршрутов, добраться до Сатурна (и, следовательно, до Юпитера) с Земли невозможно. Нет ни одного рейса, который бы связывал Сатурн с другими планетами, кроме как с Юпитером, и нет пути с Земли до Сатурна.

Ответ: Невозможно добраться до Юпитера по указанным маршрутам.