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

UptoLike

ВУЗ: 

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

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

Рубрика: 

72
Для графов G
1
= ({а
1
, а
2
, а
3
};
{[а
1
,a
2
]®{(a
2
,a
3
)}) и G
2
= ({a
1
, a
2
, a
4
}; {(а
1
, a
2
), (a
4
,
a
1
)}) (рис. 1.29) найти G
1
® G
2
, G
1
G
2
, G
1
« G
2
.
По определению имеем:
G
1
® G
2
= ({а
1
, а
2
, а
3
, a
4
}; {[a
1
, a
2
]®{(a
2
, a
3
), (a
4
,
a
1
)}),
G
1
G
2
= ({a
1
, a
2
}; {(a
1
, a
2
)}),
G
1
« G
2
= ({а
1
, а
2
, а
3
, a
4
}; {( a
2
, a
1
), (a
2
, a
3
), (a
4
, a
1
)}).
Определение 1.75. Соединением графов G
1
+ G
2
называется граф (M
1
® M
2
; R
1
® R
2
® {[a, b]|a ´
M
1
, b ´ М
2
, а ≠ b}).
Пример 1.36.
Даны графы G
1
и G
2
, показанные на рис.
1.30.а, найти соединением G
1
+ G
2
.
Соединением G
1
+ G
2
является граф, пред-
ставленный на рис. 1.30 б.
а
2
а
4
а
5
а
5
а
а
4
а
2
а
3
а
2
а
4
а
2
а
1
а
3
а
2
G
1
G
2
а
2
а
1
а
4
а
3
а
2
а
1
а
1
а
2
а
3
а
4
G
1
® G
2
G
1
G
2
G
1
« G
2
а
1
Рис. 1.29.
105
Рис. 4.4.
Ограничивая условия теоремы Поша, полу-
чаем более простые, но менее сильные достаточ-
ные условия, найденные Оре и Дираком соответ-
ственно:
Следствие 1. Если p ≥ 3 и deg u + deg v ≥ p для
любой пары u и v несмежных вершин графа G, то
G – гамильтонов граф.
Следствие 2. Если p > 3 и degv ≥ p / 2 для любой
вершины v графа G, то G – гамильтонов граф.
Теорема 4.2. В полном графе G(V, E) всегда суще-
ствует гамильтонов путь.
Доказательство.
Пусть m = a
1
a
2
…a
p
– путь длины p − 1, при-
чем все вершины в m различны. x – вершина . m.
Покажем, что можно составить путь вида
m
k
= a
1
…a
k
xa
k+1
…a
p
Пусть не существует такого целого числа k,
заключенного между 1 и p, что
(a
k
, x) . E, (x, a
k+1
) . E.
Имеем, следовательно, для 1 ≤ k ≤ p: 
       Для графов G1 = ({а1, а2, а3};
{[а1,a2]®{(a2,a3)}) и G2 = ({a1, a2, a4}; {(а1, a2), (a4,
a1)}) (рис. 1.29) найти G1® G2, G1­ G2, G1« G2.
       По определению имеем:
G1® G2 = ({а1, а2, а3, a4}; {[a1, a2]®{(a2, a3), (a4,
a1)}),
                                                                                                   Рис. 4.4.
G1 ­ G2= ({a1, a2}; {(a1, a2)}),
G1« G2 = ({а1, а2, а3, a4}; {( a2, a1), (a2, a3), (a4, a1)}).                        Ограничивая условия теоремы Поша, полу-
                  а2                                                           чаем более простые, но менее сильные достаточ-
                                                      а2
                                 а1                                            ные условия, найденные Оре и Дираком соответ-
                                                      а4                       ственно:
            а1              а3                                                 Следствие 1. Если p ≥ 3 и deg u + deg v ≥ p для
                  G1                         G2                                любой пары u и v несмежных вершин графа G, то
             а2                       а2                   а2
                                                                               G – гамильтонов граф.
                                                                               Следствие 2. Если p > 3 и degv ≥ p / 2 для любой
     а1                а3                        а1                  а3
                                                                               вершины v графа G, то G – гамильтонов граф.
                                                                               Теорема 4.2. В полном графе G(V, E) всегда суще-
             а4                       а1                   а4
        G1 ® G        G1 ­ G2        G1 « G2G1 + G2                            ствует гамильтонов путь.
Определение    1.75.
                2    Соединением    графов                                                     Доказательство.
называется граф (M1 ® Рис.M1.29.
                            2; R1 ® R2 ® {[a, b]|a ´                                 Пусть m = a1a2…ap – путь длины p − 1, при-
M1, b ´ М2, а ≠ b}).                                                           чем все вершины в m различны. x – вершина . m.
                   Пример 1.36.                                                Покажем, что можно составить путь вида
      Даны графы G1 и G2, показанные на рис.                                                  mk = a1…akxak+1…ap
1.30.а, найти соединением G1 + G2.                                                   Пусть не существует такого целого числа k,
                                                                               заключенного между 1 и p, что
      Соединением G1 + G2 является граф, пред-                                               (ak, x) . E, (x, ak+1) . E.
ставленный на рис. 1.30 б.                                                           Имеем, следовательно, для 1 ≤ k ≤ p:
       а2         а4                   а5             а4                  а5

                                            72                  а2                                       105

Страницы