Ориентированные графы в задачах

Задачи на ориентируемость графов

Пусть задан конечный неориентированный граф. Требуется ориентировать его ребра так, чтобы полученный орграф стал сильно связным. К числу таких задач относится, например, задача о введении на улицах города одностороннего движения. Ясно, что такая ориентация возможна лишь для графов, удовлетворяющих условию теоремы 29. Конкретный алгоритм ориентации следует заимствовать из хода доказательства теоремы 29.

1. На рис. 191−193 представлены схемы улиц некоторых городов. Можно ли на улицах этих городов ввести одностороннее движение?. Если это возможно, то приведите примеры возможных ориентаций.

Рис. 191 Рис. 192 Рис. 193

• 2. Ориентируйте ребра Платоновых графов (рис. 52−56), превратив их в сильно связные орграфы.
• 3. Ориентируйте ребра всех конечных полуправильных графов, превратив их в сильно связные орграфы.

Задачи на изменения состояний системы

Пусть задана некоторая система, которая в любой момент времени может находиться только в одном из конечного числа состояний. Предположим, что возможность изменения состояний системы (т.е. переход из одного состояния в другое) обусловлена некоторым правилом. Требуется определить, возможно ли посредством конечного числа одношаговых изменений состояний перевести систему из некоторого начального состояния в некоторое другое — конечное состояние.

Задачи такого типа можно решать следующим образом. Рассмотрим ориентированный граф, множество вершин которого есть множество всех состояний системы, а множество дуг есть возможные одношаговые переходы из одного состояния в другое. Тогда задача сводится к вопросу о существовании в этом орграфе пути из вершины начального состояния в вершину конечного состояния.

В качестве примера рассмотрим известную задачу о волке, козе и капусте. Некий человек должен переправить через реку волка, козу и капусту. В лодке может находиться только один человек, а с ним или волк, или коза, или капуста. Но если оставить волка с козой без человека, то волк съест козу, если оставить козу с капустой, то коза съест капусту, а в присутствии человека «никто никого не ест». Как человеку перевести свой груз через реку?

Перечислим возможные состояния системы: (ВКк/…) — начальное состояние — волк (В), коза (К) и капуста (к) находятся на левом берегу вместе с человеком;

• (Вк/К) — волк с капустой на левом берегу, коза — на правом, человек в лодке;
• (ВК/к) — волк с козой и человеком на левом берегу, капуста — на правом;
• (Кк/В) — коза с капустой и человеком на левом берегу, волк — на правом;
• (В/Кк) — волк на левом берегу, коза с капустой и человеком — на правом;
• (к/ВК) — волк с козой и человеком на правом берегу, капуста — на левом;
• (К/Вк) — коза на левом берегу, волк с капустой — на правом, человек в лодке;
• (…/ВКк) — конечное состояние — волк, коза и капуста находятся на правом берегу вместе с человеком.

Рассмотрим граф возможных одношаговых изменений состояний системы (рис. 194).

Рис. 194 Рис. 195

Требуется найти путь от вершины (ВКк/…) к вершине (…/ВКк). Таких путей два. Им соответствуют два общеизвестных решения задачи. Отметим, что, так как орграф на рис. 194 является симметрическим, то его можно заменить неориентированным графом, представленным на рис. 195.

Приведем еще две подобные задачи.

• 1. Задача «о трех ревнивых мужьях». Три супружеские пары в воскресенье подошли к реке, где они нашли маленькую лодку, которая не может поднять более двух человек одновременно. Переправа осложняется тем обстоятельством, что все мужья очень ревнивы и ни один из них не может допустить, чтобы его жена оставалась без него в компании, где есть какой-нибудь другой мужчина. Как может быть осуществлена переправа?
• 2. Задача «о людоедах и миссионерах». Три миссионера и три людоеда подошли к берегу А реки и должны переправиться на противоположный берег, В при помощи одной лодки, которая поднимает не более двух человек. Все миссионеры и один из людоедов умеют грести. Можно ли найти такую последовательность переездов, при которой число людоедов никогда не превышает число миссионеров на любом берегу реки, за исключением, конечно, случая, когда на одном берегу нет ни одного миссионера? (Миссионеры очень хорошо чувствуют необходимость в этом основном правиле.)