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

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