7 / 13
Лемма 3.
Пусть дан сильно связный орграф. Тогда любой его
сильно связный подграф
[
Q
0
]
,
[
Q
0
]
6
= [
Q
]
несовершенен.
J
Допустим, что подграф
[
Q
0
]
совершенен. Возьмем вершины
a
∈
[
Q
0
]
и
b /
∈
[
Q
0
]
. Поскольку граф
[
Q
]
сильно связный, существует
путь
v
1
→
. . .
→
v
r
, v
1
=
a, v
r
=
b
. При
a
∈
[
Q
0
]
и
b /
∈
[
Q
0
]
найдется
такое ребро
v
i
→
v
i
+1
, что
v
i
∈
[
Q
0
]
и
v
i
+1
/
∈
[
Q
0
]
. Итак, из вершины
v
i
вышло ребро
v
i
→
v
i
+1
, не содержащееся в множестве
Q
0
. Это
противоречит тому, что подграф
[
Q
0
]
совершенен.
I
Продолжим доказательство теоремы 1. Цель — подобрать
g
-метки
так, чтобы на каждом пути длиной, превосходящей число
n
, встретил-
ся барьер. Опишем необходимую конструкцию.
Построим цепочку орграфов
[
Q
0
]
⊃
[
Q
1
]
⊃ ∙ ∙ ∙ ⊃
[
Q
m
]
и снабдим
некоторые ребра
g
-меткой. Для этого примем, во-первых,
[
Q
] = [
Q
0
]
.
Если уже построен граф
[
Q
k
]
, то для построения следующего графа
[
Q
k
+1
]
возьмем сначала любую сильно связную компоненту
[
Q
0
]
графа
[
Q
k
]
. Согласно лемме 3,
[
Q
0
]
— несовершенный граф, а потому со-
держит вершину
b
k
, из которой выходит только одно ребро
b
k
→
c
k
,
лежащее в подграфе
[
Q
0
]
; назовем такое ребро
одиночным
. На каждом
ребре
d
→
b
k
исходного графа
[
Q
]
, входящем в вершину
b
k
, зададим
g
-метку вида
g
(
d, b
k
) =
f
(
b
k
, c
k
)
; получим барьеры
d
→
b
k
→
c
k
. Уда-
лим из орграфа
[
Q
k
]
вершину
b
k
, ребро
b
k
→
c
k
и все ребра, входящие
в вершину
b
k
. Получим новый орграф; это и есть искомый граф
[
Q
k
+1
]
.
Работа заканчивается тогда, когда очередной граф не имеет циклов и,
как следствие, не имеет нетривиальных связных компонент.
Каждый граф
[
Q
k
+1
]
получается из предыдущего графа
[
Q
k
]
уда-
лением одной вершины
b
k
(и ребер, содержащих вершину
b
k
). По-
лучаем также
g
-метки на некоторых ребрах. На остальных ребрах
ставим
g
-метки произвольно. В результате исходный размеченный ор-
граф
([
Q
]
, f
)
превратился в размеченный орграф
G
= ([
Q
]
, f, g
)
. От-
метим, что граф, полученный после удаления указанных ребер, далее
не используется; он необходим лишь как средство построения набора
g
-меток.
Для дальнейшего исследования введем следующие понятия: 1)
пе-
тля
— путь
q
1
→
. . .
→
q
s
, где
q
s
=
q
1
, а вершины
q
1
, . . . , q
s
−
1
попарно
различны (рис. 2,
а
); 2)
расширенная петля
— путь
q
0
→
. . .
→
q
s
, что
q
0
6
=
q
1
и путь
q
1
→
. . .
→
q
s
есть петля (рис. 2,
б
).
Лемма 4.
Пусть в графе
[
Q
]
дан путь и его отрезок, являющийся
расширенной петлей. Тогда этот отрезок содержит барьер.
J
Возьмем расширенную петлю
q
0
→
. . .
→
q
s
и соответствую-
щую петлю
q
1
→
. . .
→
q
s
, где
q
s
=
q
1
. Найдется такое
r
≥
0
, что эта
петля лежит в графе
[
Q
r
]
и не лежит в графе
[
Q
r
+1
]
(так как построен-
ная цепочка убывает начиная с исходного графа и заканчивая графом
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2016. № 2
9