В стране Врунляндия есть шесть городов и шесть дорог: дорога между городами Андерск и Бремен, дорога между городами Андерск и Враль, между городами Бремен и Враль, между городами Обманк и Зевак, между Бремен и Лжецк и между Враль и Лжецк. Можно ли по дорогам пройти с города Бремен в город Обманк. (Задачу решите с помощью графа)

Для того чтобы решить задачу о том, можно ли пройти с города Бремен в город Обманк, мы можем представить города и дороги в виде графа. Граф будет состоять из вершин (города) и ребер (дороги между городами). ### Шаг 1: Построение графа 1. **Города**: - Андерск (A) - Бремен (B) - Враль (C) - Обманк (D) - Зевак (E) - Лжецк (F) 2. **Дороги**: - Андерск - Бремен (A-B) - Андерск - Враль (A-C) - Бремен - Враль (B-C) - Обманк - Зевак (D-E) - Бремен - Лжецк (B-F) - Враль - Лжецк (C-F) Теперь запишем наш граф в виде списка смежности: - A: [B, C] - B: [A, C, F] - C: [A, B, F] - D: [E] - E: [D] - F: [B, C] ### Шаг 2: Изучение возможности пути Теперь нужно проверить, существует ли путь от города Бремен (B) к городу Обманк (D). Для этого мы можем воспользоваться методом поиска в глубину (DFS) или поиска в ширину (BFS). Мы будем пробовать искать путь с помощью DFS. ### Шаг 3: Выполнение поиска 1. **Начинаем с B** (Бремен): - Достижимые города: A (Андерск), C (Враль), F (Лжецк). 2. **Идем к A** (Андерск): - Достижимые города: B (вернемся обратно), C (Враль). Здесь не можем двигаться дальше, поэтому вернемся. 3. **Идем к C** (Враль): - Достижимые города: A (Андерск), B (вернемся), F (Лжецк). - Пробуем пойти к F (Лжецк), где у нас есть еще один путь. 4. **Идем к F** (Лжецк): - Достижимые города: B (вернемся), C (вернемся). - Мы не можем двигаться дальше от Лжецка. 5. **Возвращаемся к B** и идем к F (Лжецк) уже дважды вернулись, поэтому проверяем другую ветвь и идем к C и обратно к B. Не нашли подключение к D (Обманк). ### Шаг 4: Заключение Поскольку у нас нет никаких путей к городу Обманк (D) из Бремен (B), можно сделать вывод, что **по дорогам пройти с города Бремен в город Обманк нельзя**. Таким образом, обобщая все шаги, мы усвоили, что для поиска пути по графу нужно исследовать все возможные пути к целевому городу, и в нашем случае мы этого сделать не смогли.