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

UptoLike

ВУЗ: 

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

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

Рубрика: 

76
Рис. 1.33.
Для графов, изображенных на рис. 1.33, име-
ем следующие числа внутренней устойчивости.
α(G
1
)=1, т.к. любая пара вершин G
1
является
смежной. Граф G
2
имеет два внутренне устойчи-
вых множества
S
1
= {x
1
, x
3
}, S
2
= {x
4
, x
2
}.
Так как, |S
1
| = |S
2
| = 2, то, следовательно, α.(G
2
) = 2.
Граф G
3
содержит внутренне устойчивые множества
S
1
= {x
1
,x
5
}, S
2
= {x
1
,x
3
}, S
3
= {x
1
,x
4
},
S
4
= {x
2
,x
5
}, S
5
= {x
2
,x
4
}.
Но если к любому из этих множеств доба-
вить какую-либо вершину, не содержащуюся в
нем, то подмножество перестанет быть внутренне
устойчивым, следовательно, α (G
3
) = 2.
Определение 1.80. Подмножество вершин T ³ М
есть внешне устойчивое множество, если для каж-
дой точки x
i
´ (М \ T) выполнено условие
Г (x
i
) T = 0,
где Г (x
i
) – множество дуг, порожденных точкой x
i
.
Обозначим |T| – мощность множества T.
Пусть Ф – множество всех внешне устойчивых
множеств.
Определение 1.81. Числом внешней устойчивости
графа G называется
101
Отметим, что придумано еще много других
развлекательных и полезных задач, связанных с
поиском гамильтоновых циклов. Сформулируем
две из них.
1. Задача про банкет. Компанию из нескольких
человек требуется рассадить за круглым столом
таким образом, чтобы по обе стороны от каждо-
го сидели его знакомые. Очевидно, для решения
этой задачи нужно найти
гамильтонов цикл в
графе знакомств компании.
2. Задача о шахматном коне. Можно ли, начиная с
произвольного поля шахматной доски, обойти
конем последовательно все 64 поля по одному
разу и вернуться в исходное поле? (решение бу-
дет рассмотрено ниже).
Следующая теорема, доказанная Поша
(Posa L.), дает достаточное условие того, что не-
ориентированный граф является
гамильтоновым.
Она обобщает результаты, полученные ранее Оре
(Ore O.) и Дираком (Dirac G.A.), которые приво-
дятся здесь в виде следствий.
4.2. Основные теоремы и их следствия
Теорема 4.1. Пусть G имеет p ≥ 3 вершин. Если
для всякого n, 1 ≤ n ≤ (p − 1) ⁄ 2, число вершин со
степенями, не превосходящими n, меньше чем n, и
для нечетного p число вершин степени (p−1) ⁄ 2 не
превосходит (p − 1) ⁄ 2, то G – гамильтонов граф. 
                                                                 Отметим, что придумано еще много других
                          Рис. 1.33.
                                                           развлекательных и полезных задач, связанных с
      Для графов, изображенных на рис. 1.33, име-          поиском гамильтоновых циклов. Сформулируем
ем следующие числа внутренней устойчивости.                две из них.
α(G1)=1, т.к. любая пара вершин G1 является                1. Задача про банкет. Компанию из нескольких
смежной. Граф G2 имеет два внутренне устойчи-                 человек требуется рассадить за круглым столом
вых множества                                                 таким образом, чтобы по обе стороны от каждо-
               S1 = {x1, x3}, S2 = {x4, x2}.                  го сидели его знакомые. Очевидно, для решения
Так как, |S1| = |S2| = 2, то, следовательно, α.(G2) = 2.      этой задачи нужно найти гамильтонов цикл в
Граф G3 содержит внутренне устойчивые множества               графе знакомств компании.
             S1 = {x1,x5}, S2 = {x1,x3}, S3 = {x1,x4},     2. Задача о шахматном коне. Можно ли, начиная с
             S4 = {x2,x5}, S5 = {x2,x4}.                      произвольного поля шахматной доски, обойти
      Но если к любому из этих множеств доба-                 конем последовательно все 64 поля по одному
вить какую-либо вершину, не содержащуюся в                    разу и вернуться в исходное поле? (решение бу-
нем, то подмножество перестанет быть внутренне                дет рассмотрено ниже).
устойчивым, следовательно, α (G3) = 2.                           Следующая теорема, доказанная Поша
                                                           (Posa L.), дает достаточное условие того, что не-
Определение 1.80. Подмножество вершин T ³ М                ориентированный граф является гамильтоновым.
есть внешне устойчивое множество, если для каж-            Она обобщает результаты, полученные ранее Оре
дой точки xi ´ (М \ T) выполнено условие                   (Ore O.) и Дираком (Dirac G.A.), которые приво-
                   Г (xi) ­ T = 0,                         дятся здесь в виде следствий.
где Г (xi) – множество дуг, порожденных точкой xi.
      Обозначим |T| – мощность множества T.                     4.2. Основные теоремы и их следствия
Пусть Ф – множество всех внешне устойчивых                 Теорема 4.1. Пусть G имеет p ≥ 3 вершин. Если
множеств.                                                  для всякого n, 1 ≤ n ≤ (p − 1) ⁄ 2, число вершин со
Определение 1.81. Числом внешней устойчивости              степенями, не превосходящими n, меньше чем n, и
графа G называется                                         для нечетного p число вершин степени (p−1) ⁄ 2 не
                                                           превосходит (p − 1) ⁄ 2, то G – гамильтонов граф.


                             76                                                      101

Страницы