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

UptoLike

ВУЗ: 

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

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

Рубрика: 

74
С помощью операции произведения опреде-
лим по индукции важный класс графов, называе-
мых n-мерными кубами (п-кубами). Рассмотрим
граф К
2
, вершины которого обозначим 0 и 1. n-
Мерный куб, или n-куб Q
n
, определяется по сле-
дующим правилам: Q
0
– граф без петель, состоя-
щий из одной вершины, Q
1
= К
2
, Q
n
= К
2
×
Q
n – 1
,
n.>.1. Вершинами n-мерного куба Q
n
являются все-
возможные n-ки, состоящие из нулей и единиц
(всего таких наборов 2
n
), а ребра задаются по сле-
дующему правилу: вершины смежны тогда и толь-
ко тогда, когда соответствующие кортежи разли-
чаются ровно одной координатой. На рис. 1.32 по-
казаны двумерный Q
2
и трехмерный Q
3
кубы.
Рис. 1.32.
Определение 1.77. Композицией G
1
[G
2
] графов G
1
и G
2
называется граф (M
1
× М
2
, R), в котором
Рис. 1.31.
(0, 1) (1, 1)
(0, 0) (1, 0)
(1, 0, 0) (1, 1, 0)
(1, 0, 1) (1, 1, 1)
(0, 0, 0) (0, 1, 0)
(0, 0, 1) (0, 1, 1)
103
из G вида v
ij−1
, поскольку тогда в G был бы га-
мильтонов цикл v
1
v
2
… v
ij−1
v
p
v
p−1
…v
ij
v
1
(рис. 4.3).
Рис. 4.3.
Далее, так как
n ≥ (p − 1) / 2, то p / 2 ≤ deg v
p
≤ p − 1 − n < p / 2,
что невозможно. Поэтому v
1
и v
p
должны быть
смежны.
Отсюда следует, что если deg v ≥ p / 2 для
всех вершин v, то G – гамильтонов граф. (Ниже
это сформулировано в виде следствия 2.) В силу
изложенного выше каждая пара вершин графа G
смежна, т.е. G – полный граф. Мы пришли к про-
тиворечию, поскольку полный граф является га-
мильтоновым
для всех p ≤ 3.
Таким образом, в G – есть вершина v с
deg.v < p / 2. Обозначим через m наибольшую сре-
ди степеней всех таких вершин. Выберем такую
вершину v
1
, что deg v
1
= m. По принятому предпо-
ложению число вершин со степенями, не превос-
ходящими m, не больше чем m < p / 2, поэтому 
                                                                        из G вида vij−1, поскольку тогда в G был бы га-
                         Рис. 1.31.                                     мильтонов цикл v1 v2 … vij−1 vp vp−1…vij v1 (рис. 4.3).
       С помощью операции произведения опреде-
лим по индукции важный класс графов, называе-
мых n-мерными кубами (п-кубами). Рассмотрим
граф К2, вершины которого обозначим 0 и 1. n-
Мерный куб, или n-куб Qn, определяется по сле-
дующим правилам: Q0 – граф без петель, состоя-
щий из одной вершины, Q1 = К2, Qn = К2 × Qn – 1,
n.>.1. Вершинами n-мерного куба Qn являются все-
                                                                                                Рис. 4.3.
возможные n-ки, состоящие из нулей и единиц
(всего таких наборов 2n), а ребра задаются по сле-                             Далее, так как
дующему правилу: вершины смежны тогда и толь-                             n ≥ (p − 1) / 2, то p / 2 ≤ deg vp ≤ p − 1 − n < p / 2,
ко тогда, когда соответствующие кортежи разли-                          что невозможно. Поэтому v1 и vp должны быть
чаются ровно одной координатой. На рис. 1.32 по-                        смежны.
казаны двумерный Q2 и трехмерный Q3 кубы.                                      Отсюда следует, что если deg v ≥ p / 2 для
                                                                        всех вершин v, то G – гамильтонов граф. (Ниже
                        (1, 0, 1)                       (1, 1, 1)       это сформулировано в виде следствия 2.) В силу
  (0, 1)       (1, 1)
                                    (0, 0, 1) (0, 1, 1)                 изложенного выше каждая пара вершин графа G
                                                                        смежна, т.е. G – полный граф. Мы пришли к про-
                                                                        тиворечию, поскольку полный граф является га-
                                    (0, 0, 0)   (0, 1, 0)               мильтоновым для всех p ≤ 3.
  (0, 0)       (1, 0)
                         (1, 0, 0)                          (1, 1, 0)          Таким образом, в G – есть вершина v с
                                                                        deg.v < p / 2. Обозначим через m наибольшую сре-
                        Рис. 1.32.                                      ди степеней всех таких вершин. Выберем такую
Определение 1.77. Композицией G1 [G2] графов G1                         вершину v1, что deg v1 = m. По принятому предпо-
и G2 называется граф (M1 × М2, R), в котором                            ложению число вершин со степенями, не превос-
                                                                        ходящими m, не больше чем m < p / 2, поэтому

                                    74                                                                103

Страницы