Previous Page  8 / 13 Next Page
Information
Show Menu
Previous Page 8 / 13 Next Page
Page Background

Рис. 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