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

UptoLike

ВУЗ: 

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

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

Рубрика: 

78
(n.=.9), ребра характеризуют возможность про-
сматривания объектов часовыми. Так, например,
часовой у объекта X
1
может одновременно наблю-
дать за объектами X
2
, X
3
, X
4
, X
6
, X
9
, часовой у объ-
екта X
2
– за объектами X
1
, X
3
, X
7
, X
8
и т.д. Для дан-
ного графа число внешней устойчивости равно 2.
Внешне устойчивое множество образуют вершины
X
4
, X
8
. Достаточно двух часовых, расположенных в
точках X
4
и X
8
, для охраны всех объектов.
Рис 1.34.
2. Основные теоремы теории графов
Теорема 2.1. Удвоенная сумма степеней вершин
любого графа равна числу его ребер.
Доказательство.
Пусть А
1
, А
2
, А
3
, ..., A
n
– вершины данного
графа, a p(A
1
), р(А
2
), ..., p(A
n
) – степени этих вер-
99
двух параллельных ребер между любыми двумя
вершинами, т.е. оптимальный цикл не проходит ни
по какому ребру графа G более чем два раза.
4. Гамильтоновы циклы
4.1 Основные определения
Определение 4.1. Гамильтоновой цепью графа на-
зывается его простая цепь, которая проходит через
каждую вершину графа точно один раз.
Определение 4.2. Цикл графа, проходящий через
каждую его вершину, называется гамильтоновым
циклом.
Определение 4.3. Граф называется гамильтоно-
вым, если он обладает гамильтоновым циклом.
Определение 4.4. Граф, который содержит про-
стой путь, проходящий через каждую его вершину,
называется полугамильтоновым.
Это определение можно распространить на
ориентированные графы, если путь считать ориен-
тированным. Гамильтонов цикл не обязательно
содержит все ребра графа. Ясно, что гамильтоно-
вым может быть только связный граф и, что вся-
кий гамильтонов граф является полугамильтоно-
вым. Заметим, что гамильтонов цикл существует
далеко не в каждом графе.
Замечание: Любой граф G можно превратить в
гамильтонов граф, добавив достаточное количест-
во вершин. Для этого, например, достаточно к вер-
(n.=.9), ребра характеризуют возможность про-           двух параллельных ребер между любыми двумя
сматривания объектов часовыми. Так, например,           вершинами, т.е. оптимальный цикл не проходит ни
часовой у объекта X1 может одновременно наблю-          по какому ребру графа G более чем два раза.
дать за объектами X2, X3, X4, X6, X9, часовой у объ-
екта X2 – за объектами X1, X3, X7, X8 и т.д. Для дан-                4. Гамильтоновы циклы
ного графа число внешней устойчивости равно 2.                      4.1 Основные определения
Внешне устойчивое множество образуют вершины            Определение 4.1. Гамильтоновой цепью графа на-
X4, X8. Достаточно двух часовых, расположенных в        зывается его простая цепь, которая проходит через
точках X4 и X8, для охраны всех объектов.               каждую вершину графа точно один раз.
                                                        Определение 4.2. Цикл графа, проходящий через
                                                        каждую его вершину, называется гамильтоновым
                                                        циклом.
                                                        Определение 4.3. Граф называется гамильтоно-
                                                        вым, если он обладает гамильтоновым циклом.
                                                        Определение 4.4. Граф, который содержит про-
                                                        стой путь, проходящий через каждую его вершину,
                                                        называется полугамильтоновым.
                                                              Это определение можно распространить на
                                                        ориентированные графы, если путь считать ориен-
                      Рис 1.34.                         тированным. Гамильтонов цикл не обязательно
                                                        содержит все ребра графа. Ясно, что гамильтоно-
                                                        вым может быть только связный граф и, что вся-
      2. Основные теоремы теории графов                 кий гамильтонов граф является полугамильтоно-
Теорема 2.1. Удвоенная сумма степеней вершин            вым. Заметим, что гамильтонов цикл существует
любого графа равна числу его ребер.                     далеко не в каждом графе.
                 Доказательство.                        Замечание: Любой граф G можно превратить в
      Пусть А1, А2, А3, ..., An – вершины данного       гамильтонов граф, добавив достаточное количест-
графа, a p(A1), р(А2), ..., p(An) – степени этих вер-   во вершин. Для этого, например, достаточно к вер-


                            78                                                    99

Страницы