Элементы теории графов. Сюсюкалов А.И - 25 стр.

UptoLike

ВУЗ: 

РГРТУ | Рязань

Составители: 

Рубрика: 

20
Теорема 5.2. Граф является односторонним тогда и толь-
ко тогда, когда в нем есть маршрут, содержащий все вершины
орграфа.
Д о к а з а т е л ь с т в о. Необходимость. Рассмотрим мар-
шрут в орграфе
k
vvvL ...,,,
21
, содержащий наибольшее
число вершин. Так как для любых трех вершин орграфа хотя бы
из одной достижимы две другие, то
3
k
. Если маршрут со-
держит все вершины орграфа, то теорема верна.
Пусть существует вершина
u
, не входящая в
L
. Если вер-
шина
1
v достижима из вершины
u
, то в орграфе существует
маршрут, содержащий больше вершин, чем маршрут
L
, что
противоречит выбору
L
(рис. 15). То же произойдет, если вер-
шина
u
достижима из вершины
k
v . Предположим, что это не
выполняется.
Рассмотрим две соседние в маршруте
L
вершины
x
и
y
.
Если из одной из них (например, из вершины
x
) достижима
вершина
u
, а вторая (вершина
y
) достижима из
u
, то в оргра-
фе есть маршрут
k
vyuxvL ...,,,...,,...,...,,
11
, содержащий
большее число вершин, чем
L
(рис. 16).
Пусть это не выполняется. Тогда в орграфе снова существу-
ет маршрут
k
vvuvL ...,,,...,...,,
212
или
kk
vuvvL ...,,,...,...,,
113
с большим числом вершин, чем
L
(рис. 17).
Достаточность очевидна. Теорема доказана.
1
v
L
2
v
k
v
Рис.15

Страницы