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

UptoLike

ВУЗ: 

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

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

Рубрика: 

19
Следствие. Если G = G(V, E) – связный граф, имеющий n вершин, где n
≥
3, и если для каждой вершины υ
∈
V выполняется deg(υ) ≥
2
n
, то граф G имеет
гамильтонов цикл.
ТЕОРЕМА 1.13. Пусть G = G(V, E) – связный граф с n ≥ 3 вершинами и
пусть u и υ – несмежные вершины графа G такие, что deg(u) + deg(υ) ≥ n. Отсю-
да граф G
e
, состоящий из графа G с присоединенным ребром e = {u, υ}, имеет
гамильтонов цикл тогда и только тогда, когда граф G имеет гамильтонов цикл.
● Пусть G – граф с n вершинами. Замыканием графа G, обозначаемым
cl(G), называется граф, полученный из графа G рекурсивным добавлением ре-
бер к несмежным вершинам u и
υ графа G, для которых deg(u) + deg(υ) ≥ n до
тех пор, пока это возможно.
Пример. Если G – граф, изображенный на рис. 1.44, то cl(G) – граф, изображенный на
рис. 1.45.
Рис. 1.44 Рис. 1.45
Пример. Если G – граф, изображенный на рис. 1.46, то cl(G) – граф, изображенный на
рис. 1.47.
Рис. 1.46 Рис. 1.47
ТЕОРЕМА 1.14. Граф G имеет гамильтонов цикл тогда и только тогда,
когда граф cl(G) имеет гамильтонов цикл.
1.6 Алгоритм поиска кратчайшего пути
До сих пор при рассмотрении графов нас интересовали вершины и ребра,
по которым можно перемещаться. Теперь нас интересует не только перемеще-
ние из точки А в точку B ,
но и то, как это сделать наилучшим способом. Пер-
вый вопрос состоит в том, что означает «наилучшим способом». Это может
a
b
c
e ƒ
d
b
a
e
c
d
ƒ
a b
c d e
a b
c
e
d

Страницы