ВУЗ:
Составители:
Рубрика:
30
Покажем, что в построенном орграфе существует контур. Выбе-
рем любую вершину
i
v орграфа. Поскольку из нее выходит хотя
бы одна дуга, перейдем по этой дуге в соседнюю вершину
2
v .
Аналогично из
2
v перейдем в
3
v и так далее. Поскольку число
вершин в орграфе конечно, то в конце концов мы попадем в
вершину, в которой были ранее. Полученный контур определяет
необходимые встречи команд. 11. Рассмотрим ориентированный
граф
G
, задающий движение по улицам города. Из условия
следует, что орграф
G
– сильный. Построим маршрут, который
начинается и оканчивается в одной и той же вершине и содер-
жит все дуги орграфа. Рассмотрим две произвольные вершины
1
u и
1
v . В орграфе существует маршрут, соединяющий вершины
1
u и
1
v , и маршрут, соединяющий вершины
1
v и
1
u . Объединим
эти маршруты в один маршрут
1
L . Он будет начинаться и окан-
чиваться в вершине
1
u . Если этот маршрут будет содержать все
дуги орграфа, то он будет искомым. Предположим, что в оргра-
фе остались дуги, не вошедшие в маршрут
1
L . Рассмотрим дугу
22
,vu , причем
2
u принадлежит
1
L , а
2
v не принадлежит
1
L .
В орграфе существует маршрут, соединяющий вершины
2
v и
2
u . Вместе с дугой
22
,vu он будет образовывать маршрут
2
L ,
который начинается и оканчивается в вершине
2
v . Объединим
маршруты
1
L и
2
L в один маршрут
L
(см. рис. 18).
1
L
2
L
1
v
2
v
1
u
2
u
Рис.18
Если маршрут
L
не содержит все дуги орграфа
G
, то увеличим
его с помощью некоторого маршрута
3
L , и так до тех пор, пока
не получим нужный маршрут. Этот маршрут и будет соответст-
