Учебник «Вероятность и статистика. 7–9 классы», часть 1, с. 88, §20
№139. В Солнечной системе введено космическое сообщение. Корабли осуществляют рейсы в обе стороны по следующим маршрутам:
Земля — Меркурий, Марс — Венера, Уран — Нептун, Марс — Меркурий, Юпитер — Плутон, Меркурий — Венера, Нептун — Сатурн, Сатурн — Юпитер, Плутон — Уран.
Можно ли добраться с Земли до Плутона?
Дано:
9 планет; маршруты в обе стороны: Земля—Меркурий, Марс—Венера, Уран—Нептун, Марс—Меркурий, Юпитер—Плутон, Меркурий—Венера, Нептун—Сатурн, Сатурн—Юпитер, Плутон—Уран
Найти:
можно ли добраться с Земли до Плутона
Построим граф маршрутов: планеты — вершины, а ребро соединяет две планеты, между которыми летают корабли (в обе стороны, поэтому рёбра без стрелок). Всего девять рёбер.
С Земли можно долететь только до Меркурия. С Меркурия — до Марса и Венеры (а Марс и Венера, в свою очередь, связаны между собой). Ничего другого: из Земли, Меркурия, Марса и Венеры больше никуда не ведут рёбра. Значит, с Земли можно добраться только до этих четырёх планет.
Плутон лежит в другой части графа: маршруты Юпитер — Плутон, Плутон — Уран, Уран — Нептун, Нептун — Сатурн и Сатурн — Юпитер образуют цикл из пяти планет, и ни один маршрут не ведёт из него к Земле, Меркурию, Марсу или Венере. Граф маршрутов состоит из двух частей — он несвязный. Путей от Земли до Плутона нет (проверено перебором).
Ответ: нет, добраться с Земли до Плутона нельзя.
Ответ: Нет, граф маршрутов не связан: с Земли можно попасть только на Меркурий, Марс и Венеру, а Плутон принадлежит другой части графа.
