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

UptoLike

ВУЗ: 

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

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

Рубрика: 

17
ТЕОРЕМА 1.10. Каждый планарный граф G содержит вершину степени
5 или менее.
Пример. Покажем, что граф, изображенный на рис. 1.36, является, планарным. Пере-
двигая вершину d, получаем более простой граф, изображенный на рис. 1.37. Передвигая
вершину c, получаем граф (рис. 1.38), который, очевидно, является планарным.
Рис. 1.36 Рис. 1.37 Рис. 1.38
1.5 Пути и циклы Гамильтона
В 1857 году математик Уильям Фоуэн Гамильтон придумал игру. Она
включала додекаэдр, т.е. правильным многогранник, 12 граней которого пред-
ставляли собой конгруэнтные правильные пятиугольники. В каждом из 20 уг-
лов, или вершин тела, просверливалась дырка, в которую вставлялся колышек,
изображавший город. Используя веревку, требовалось найти путь через
города,
посетив каждый город один раз, и вернуться в исходный город. Додекаэдр на
плоскости изображается так, как показано на рис. 1.39.
Рис. 1.39
Проблема в таком случае сводится к нахождению цикла в графе, прохо-
дящего через каждую вершину, исключая начальную, только один раз. Отсюда
любой цикл графа, обладающий таким свойством, называется гамильтоновым
циклом. Этот цикл в некотором смысле противоположен эйлерову циклу, кото-
рый проходит через все ребра только один раз.
● Пусть G –
граф. Гамильтонов путь – это простой путь, который про-
ходит через каждую вершину G.
e
a
c d
b a
d
e
c
b
a b
c
d e
b
l
m k
u t
a n
j c
q s
о i
r
g
ƒ
e
h
d

Страницы