8 / 13
Рис. 2. Петля (
а
) и расширенная петля (
б
)
без циклов). Поскольку граф
[
Q
r
+1
]
получен из графа
[
Q
r
]
удалением
ровно одной вершины
b
r
, эта вершина лежит на петле. Возможны два
случая: 1) вершина
b
r
совпадает c вершиной
q
1
; 2) она совпадает с не-
которой вершиной
q
j
,
1
< j < s
. В обоих случаях
b
r
→
c
r
— одиночное
ребро в графе
[
Q
r
]
. Поэтому, и по построению функции
g,
в первом
случае имеем барьер
q
0
→
q
1
→
q
2
, где
q
1
=
b
r
, q
2
=
c
r
, во втором —
барьер
q
j
−
1
→
q
j
→
q
j
+1
, где
q
j
+1
=
c
r
.
I
Для следующей леммы используем введенное обозначение
n
=
|
Q
|
.
Лемма 5.
Любой отрезок пути длиной, не меньшей
n
+ 1
,
не
являющийся начальным
,
содержит расширенную петлю.
J
Любой путь
q
1
→
. . .
→
q
m
длиной, не меньшей
n
, содержит со-
впадающие вершины и, следовательно, петлю. Пусть эта петля имеет
вид
q
i
→
. . .
→
q
s
, q
i
=
q
s
. Поскольку рассматриваемый отрезок не на-
чало пути, на этом пути имеется вершина
q
i
−
1
. Получим расширенную
петлю
q
i
−
1
→
q
i
→
. . .
→
q
s
.
I
Из лемм 4 и 5 получаем, что любой не начальный отрезок пути
длиной, не меньшей
n
+1
, содержит барьер. Отсюда следует теорема 1.
Частичное угадывание множеств
R
(
q
0
, Q, Q
0
)
и языков
L
(
q
0
, Q, Q
0
)
.
Вернемся к множествам
R
(
Q, Q
0
)
, выделяемым усло-
вием
lim
α
=
Q
0
. Известно, что эти множества
R
(
Q, Q
0
)
непусты тогда
и только тогда, когда подграф
[
Q
0
]
сильно связный. Из теоремы 1
вытекает следствие.
Следствие 1.
Множество
R
(
Q, Q
0
)
частично угадываемо тогда
и только тогда
,
когда
[
Q
0
]
— несовершенный подграф.
Отсюда немедленно получаем соответствующее утверждение и для
языков
L
(
q
0
, Q, Q
0
)
.
Несколько модифицируем процедуру угадывания
множества посредством
g
-меток в орграфе
G
= (
Q, E, f, g
)
. Рассмо-
трим сильно связное множество
Q
0
⊂
Q
и соответствующее
R
(
Q
0
)
.
Пусть
[
Q
0
]
— несовершенный подграф. Тем самым множество
R
(
Q, Q
0
)
угадываемо в узком смысле с некоторым интервалом угадывания.
Условимся задавать
g
-метки, определяющие угадывание, только на
ребрах, входящих в подграф
[
Q
0
]
. Если путь произволен, то процеду-
ра угадывания для него будет носить “прерывистый” характер: если
10
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2016. № 2