В некоторой деревне есть 5 5 магазинов и 4 4 дороги между ними: дорога между магазинами «Овощной» и «Фруктовый», между «Фруктовым» и «Булочной», между «Мясным» и «Овощным», а…
В некоторой деревне есть 5 5 магазинов и 4 4 дороги между ними: дорога между магазинами «Овощной» и «Фруктовый», между «Фруктовым» и «Булочной», между «Мясным» и «Овощным», а также между «Рыбным» и «Мясным». Можно ли, находясь в магазине «Фруктовый», дойти по этим дорогам до каждого из остальных магазинов? Решение Вершины графа — это , а рёбра графа —.
Для того чтобы решить данную задачу, нужно определить, можно ли из магазина "Фруктовый" дойти до каждого из остальных магазинов по имеющимся дорогам.
Задан граф, где вершинами являются магазины, а рёбра - дороги между ними.
Составим таблицу смежности для этого графа:
| Овощной | Фруктовый | Булочной | Мясной | Рыбный |
----------------------------------------------------------
Овощной| 0 | 1 | 0 | 1 | 0 |
----------------------------------------------------------
Фруктовый| 1 | 0 | 1 | 0 | 0 |
----------------------------------------------------------
Булочной| 0 | 1 | 0 | 0 | 0 |
----------------------------------------------------------
Мясной | 1 | 0 | 0 | 0 | 1 |
----------------------------------------------------------
Рыбный | 0 | 0 | 0 | 1 | 0 |
Теперь мы видим, что из магазина "Фруктовый" можем дойти до "Овощного", "Булочного" и "Мясного", но до "Рыбного" из "Фруктового" не добраться по имеющимся дорогам.
Следовательно, нельзя находясь в магазине "Фруктовый", дойти по этим дорогам до каждого из остальных магазинов.
