Составители:
Рубрика:
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
Страницы
- « первая
- ‹ предыдущая
- …
- 73
- 74
- 75
- 76
- 77
- …
- следующая ›
- последняя »