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

Ответ: Нельзя пройти из Бремена в Обманк.

Решение:

• Представим города в виде вершин графа, а дороги в виде ребер.
• Строим граф по условию:
• Андерск соединен с Бременом.
• Андерск соединен с Вралем.
• Бремен соединен с Вралем.
• Обманк соединен с Зеваком.
• Бремен соединен с Лжецком.
• Враль соединен с Лжецком.
• Анализируем граф:
• Есть два несвязных подграфа:
• Подграф 1: Андерск - Бремен - Враль - Лжецк.
• Подграф 2: Обманк - Зевак.
• Город Бремен находится в подграфе 1.
• Город Обманк находится в подграфе 2.
• Так как подграфы не связаны, невозможно пройти из Бремена в Обманк.

Ответ: Нельзя пройти из Бремена в Обманк.