Основные понятия теории графов. Гладких О.Б - 73 стр.

UptoLike

ВУЗ: 

ЕГУ им. Бунина | Елец

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

Рубрика: 

104
должно быть более чем m вершин со степенями,
превосходящими m, и, следовательно, не мень-
шим, чем p / 2. В результате найдется некоторая
вершина, скажем v
p
, степени по крайней мере p./.2,
не смежная с v
1
. Так как v
1
и v
p
не смежны, то су-
ществует остовная простая цепь v
1
…v
p
. Как и вы-
ше, обозначим через v
i1
,…,v
im
вершины графа G,
смежные с v
1
, и заметим, что вершина v
p
не может
быть смежной ни с одной из m вершин v
ij−1
для
1 <.j ≤ m. Но поскольку v
1
и v
p
не смежны, а v
p
имеет степень не меньше p / 2, то, как было пока-
зано в первой части доказательства, m должно
быть меньше чем (p – 1) / 2. Так как по предполо-
жению число вершин, со степенями, не превосхо-
дящими m, меньше чем m, то хотя бы одна из m
вершин v
ij–1
, скажем u, должна иметь степень не
меньше p./.2. Итак, мы установили, что степени
двух несмежных вершин v
p
и u не меньше p / 2.
Полученное противоречие завершает доказатель-
ство теоремы.
Приведенное достаточное условие не явля-
ется необходимым. Кубический граф, изображен-
ный на рис. 4.4, гамильтонов, хотя ясно, что он не
удовлетворяет условиям теоремы. Однако условия
теоремы неулучшаемы, поскольку при их ослабле-
нии новое условие уже не будет достаточным для
гамильтоновости графа.
73
Рис. 1.30
Определение 1.76. Произведением графов G
1
× G
2
называется граф (M
1
×
M
2
, R), в котором ((a
1
, b
1
),
(a
2
, b
2
)) ´ R тогда и только тогда, когда а
1
= а
2
и
(b
1
, b
2
) ´ R
2
, или b
1
= b
2
и (а
1
, а
2
) ´ R
1
.
Пример 1.37.
Изобразите произведение G
1
.
×
.G
2
графов
G
1
= ({1, 2}; {(1, 1), (2, 1)}) и
G
2
= ({a, b, c}; [a, b] ® {(b, c)}
На рис. 1.31 изображено произведение дан-
ных графов.
1
2
×
а b c
G
1
G
2
=
(2, а) (2, b) (2, с)
G
1
× G
2
(1, а) (1, b) (1, с) 
должно быть более чем m вершин со степенями,
превосходящими m, и, следовательно, не мень-
шим, чем p / 2. В результате найдется некоторая
вершина, скажем vp, степени по крайней мере p./.2,
не смежная с v1. Так как v1 и vp не смежны, то су-
ществует остовная простая цепь v1…vp. Как и вы-
ше, обозначим через vi1,…,vim вершины графа G,
смежные с v1, и заметим, что вершина vp не может                             Рис. 1.30
быть смежной ни с одной из m вершин vij−1 для        Определение 1.76. Произведением графов G1 × G2
1 <.j ≤ m. Но поскольку v1 и vp не смежны, а vp      называется граф (M1 × M2, R), в котором ((a1, b1),
имеет степень не меньше p / 2, то, как было пока-    (a2, b2)) ´ R тогда и только тогда, когда а1 = а2 и
зано в первой части доказательства, m должно         (b1, b2) ´ R2, или b1 = b2 и (а1, а2) ´ R1.
быть меньше чем (p – 1) / 2. Так как по предполо-
жению число вершин, со степенями, не превосхо-                             Пример 1.37.
дящими m, меньше чем m, то хотя бы одна из m                  Изобразите произведение G1. × .G2 графов
вершин vij–1, скажем u, должна иметь степень не                    G1 = ({1, 2}; {(1, 1), (2, 1)}) и
меньше p./.2. Итак, мы установили, что степени                     G2 = ({a, b, c}; [a, b] ® {(b, c)}
двух несмежных вершин vp и u не меньше p / 2.
Полученное противоречие завершает доказатель-             На рис. 1.31 изображено произведение дан-
ство теоремы.                                        ных графов.
       Приведенное достаточное условие не явля-                                  (1, а)   (1, b)    (1, с)
ется необходимым. Кубический граф, изображен-
ный на рис. 4.4, гамильтонов, хотя ясно, что он не   1
удовлетворяет условиям теоремы. Однако условия                    а   b      c
                                                              ×                  =
теоремы неулучшаемы, поскольку при их ослабле-
нии новое условие уже не будет достаточным для       2
гамильтоновости графа.                                   G1           G2
                                                                                 (2, а)    (2, b)   (2, с)
                                                                                          G1 × G2


                          104                                                        73

Страницы