Графы и сети. Харитонова Е.В. - 28 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

27
в) г)
9. Докажите теорему. Граф (мультиграф или псевдограф) имеет собст-
венный эйлеров путь тогда и только тогда, когда он связный и ровно две вер-
шины имеют нечетную степень.
10. Докажите, что если граф содержит цикл от вершины υ к ней самой, то
содержит простой цикл от вершины υ к ней самой.
11.
Докажите, что ориентированный граф является сильно связным, если
в графе существует вершина υ такая, что каждая другая вершина графа дости-
жима из υ и вершина υ достижима из любой другой вершины графа.
12. Докажите теорему. Ориентированный граф имеет эйлеров путь тогда
и только тогда, когда он сильно связный и степень
входа каждой вершины рав-
на ее степени выхода.
II. Найдите гамильтонов цикл, если он существует, для каждого из при-
веденных ниже графов.
13.
а) б)
в) г)
b
c d
e ƒ
a
g h
a
b c
e
ƒ
d
a
b
c
d
e ƒ g
a
b
c
d
e
ƒ
a b
c d
e ƒ
h
i
g
a
b
c d
e ƒ

Страницы