Главное меню

Городе 10 остановок, можно ли доехать от остановки 7 до 3 и от 9 до 1?

Автор Wennnt, Март 13, 2024, 22:50

« назад - далее »

Wennnt

В городе десять автобусных остановок: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 и 10 непересекающихся дорог между остановками 3 и 4, 1 и 10, 6 и 7, 7 и 8, 4 и 9, 2 и 1, 2 и 3, 5 и 6, 9 и 10, 5 и 8. Можно ли доехать на автобусе от остановки 7 до остановки 3? От остановки 9 до остановки 1?

Stham

Можно аккуратно просмотреть какие номера связанны между собой от 7 до 3 в одном случае и от 9 до 1 в другом случае. И найдя общие номера построить путь или не найдя общих, констатировать невозможность доехать. Но наглядней и проще будет, если нарисовать в виде графа остановки и дороги их соединяющие. Смотрим рисунок.
Как видим получили два не связанных графа.
И номера 7 и 3 находятся в разных графах и нет соединения между ними.
Значит нельзя доехать от остановки 7 до остановки 3
Во втором случае обе остановке находятся в одном связном графе и от остановки 9 до остановки 1 существует путь, а значит можно добраться на автобусе.
Ответ: от 7 к 3 - нельзя; от 9 к 1 - можно
                                                                              

Xeldmed

Давайте смотреть, что там получается.
а) От остановки 7 до остановки 3:
7 и 8,
8 и 5,
5 и 3,
как видно, что можно доехать.
б) От остановки 9 до остановки 1:
9 и 10,
10 и 1,
и тут можно доехать, ещё даже короче.