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

Лемма 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