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

UptoLike

ВУЗ: 

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

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

Рубрика: 

102
Доказательство.
Предположим, что теорема неверна, и пусть
G – максимальный негамильтонов граф с p верши-
нами, удовлетворяющий условиям теоремы. Легко
видеть, что добавление любого ребра в граф, обла-
дающий указанными в теореме свойствами, при-
водит к графу, который так же обладает этими
свойствами. Таким образом, поскольку добавление
к G произвольного ребра
приводит к гамильтонову
графу, любые две несмежные вершины соединимы
простой остовной (содержащей все вершины гра-
фа) цепью.
Покажем сначала, что всякая вершина, сте-
пень которой не меньше (p − 1) / 2, смежна с каж-
дой вершиной со степенью, большей чем
(p.−.1)./.2. Допустим (не теряя общности), что
deg.v
1
≥ (p − 1) / 2 и deg v
p
≥ p / 2, но вершины v
1
и
v
p
не смежны. Тогда существует простая остовная
цепь v
1
v
2
…v
p
, соединяющая v
1
и v
p
(рис. 4.2).
Рис. 4.2.
Обозначим вершины, смежные с v
1
, через v
i1
,…,v
in
,
где n = deg v
1
и 2 = i
1
< i
2
<…< i
n
. Ясно, что верши-
на v
p
не может быть смежной ни с одной вершиной
V
1
V
2
V
p – 1
V
p
…
75
((a
1
,.b
1
), (a
2
,.b
2
)) ´ R тогда и только тогда, когда
выполняется одно из следующих условий:
1) (a
1
, a
2
) ´ R
1
;
2) a
1
= а
2
и (b
1
, b
2
) ´ R
2
.
1.17. Внутренняя и внешняя устойчивость
графа
Пусть задан некоторый граф G = (М, R).
Определение 1.78. Подмножество вершин S ´ М,
в котором две любые точки являются несмежны-
ми, называется внутренне устойчивым.
Обозначим |S| – мощность множества S.
Пусть F – множество всех внутренне устойчивых
множеств.
Определение 1.79. Числом внутренней устойчиво-
сти графа G называется
() max
SF
GS
α
∈
=
Отыскание α.(G) нужно начинать с макси-
мального числа вершин и, постепенно увеличивая
его, проверять, образуют ли выбранные вершины
внутренне устойчивое множество.
G
1
G
2
G
3
                   Доказательство.                       ((a1,.b1), (a2,.b2)) ´ R тогда и только тогда, когда
       Предположим, что теорема неверна, и пусть         выполняется одно из следующих условий:
G – максимальный негамильтонов граф с p верши-                  1) (a1, a2) ´ R1;
нами, удовлетворяющий условиям теоремы. Легко                   2) a1 = а2 и (b1, b2) ´ R2.
видеть, что добавление любого ребра в граф, обла-
дающий указанными в теореме свойствами, при-                1.17. Внутренняя и внешняя устойчивость
водит к графу, который так же обладает этими                                  графа
свойствами. Таким образом, поскольку добавление                Пусть задан некоторый граф G = (М, R).
к G произвольного ребра приводит к гамильтонову          Определение 1.78. Подмножество вершин S ´ М,
графу, любые две несмежные вершины соединимы             в котором две любые точки являются несмежны-
простой остовной (содержащей все вершины гра-            ми, называется внутренне устойчивым.
фа) цепью.                                                     Обозначим |S| – мощность множества S.
       Покажем сначала, что всякая вершина, сте-         Пусть F – множество всех внутренне устойчивых
пень которой не меньше (p − 1) / 2, смежна с каж-        множеств.
дой вершиной со степенью, большей чем                    Определение 1.79. Числом внутренней устойчиво-
(p.−.1)./.2. Допустим (не теряя общности), что           сти графа G называется
deg.v1 ≥ (p − 1) / 2 и deg vp ≥ p / 2, но вершины v1 и                     α (G ) = max S
vp не смежны. Тогда существует простая остовная                                     S∈F

цепь v1v2…vp, соединяющая v1 и vp (рис. 4.2).                  Отыскание α.(G) нужно начинать с макси-
                                                         мального числа вершин и, постепенно увеличивая
       V1       V2          …       Vp – 1    Vp
                                                         его, проверять, образуют ли выбранные вершины
                                                         внутренне устойчивое множество.
                       Рис. 4.2.
Обозначим вершины, смежные с v1, через vi1,…,vin,
где n = deg v1 и 2 = i1 < i2 <…< in. Ясно, что верши-
на vp не может быть смежной ни с одной вершиной
                                                               G1              G2               G3


                             102                                                    75

Страницы