ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.12.2023
Просмотров: 224
Скачиваний: 8
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
2. ОСНОВЫ ТЕОРИИ ГРАФОВ
63
(a) неориентированных без петель и кратных рёбер?
(b) неориентированных, у которых допускаются кратные рёбра и петли?
Эйлеров цикл (путь) в мультиграфе — цикл (путь), проходящий по каждому ребру мультиграфа ровно один раз.
2.5.3.
(a) В связном мультиграфе есть эйлеров цикл тогда и толь- ко тогда, когда степень каждой его вершины чётна.
(b) В связном мультиграфе есть эйлеров цикл тогда и только то- гда, когда множество его ребер распадается на несамопересекаю- щиеся циклы.
(c) При каком условии в мультиграфе существует эйлеров путь?
(d) При каком условии в ориентированном мультиграфе существу- ет ориентированный эйлеров цикл?
(e) При каких n граф K
n имеет эйлеров цикл?
(f) То же для графа K
m,n
Входящей степенью вершины ориентированного мультиграфа называется число входящих в нее рёбер (с учетом кратности). Ана- логично определяется исходящая степень. При петля кратности k
‘вносит вклад’ k и во входящую, и в исходящую степень.
2.5.4.
(a) Если количество вершин нечётной степени в связном графе равно 2k, то множество его рёбер можно представить в виде объединения k путей, никакой из которых не проходит ни по какому ребру дважды и никакие два из которых не имеют общих рёбер.
(b) На рёбрах графа, у которого степень каждой вершины чётна,
можно поставить стрелки так, что у каждой вершины входящая степень будет совпадать с исходящей.
(c) Все рёбра связного графа раскрашены в два цвета. Из каждой вершины выходит поровну рёбер обоих цветов. Тогда из любой вер- шины до любой другой можно добраться, каждый раз меняя цвет ребра.
(d) В нарисованном на плоскости без самопересечений связном графе есть эйлеров цикл тогда и только тогда, когда грани мож- но раскрасить в 2 цвета правильно, т.е. так, что при переходе через каждое ребро цвет меняется.
64
Элементы дискретной математики в задачах
2.5.5.
Математик забыл трёхзначный код своего замк´a. Замок от- крывается, если три цифры кода набраны подряд (даже если перед этим были набраны другие цифры). Математик набирает одну циф- ру в секунду; набранная цифра добавляется в конец. Докажите, что математик сможет открыть замок за
(a) 29 секунд, если в коде могут быть использованы только цифры
1, 3 и 7;
(b) 1002 секунды, если в коде могут быть использованы только десять цифр.
(c) Сформулируйте и докажите правило «0 < 1 < 2 . . . < 8 < 9»
открытия замка за 1002 секунды.
Последовательность де Брёйна (П. д. Б.) с параметрами n и k
— последовательность, элементы которой принадлежат заданному множеству из k элементов (обычно — {0, 1, . . . , k − 1}), причём все её подпоследовательности длины n различны, и среди этих подпо- следовательностей встречаются все k n
возможных последователь- ностей. (Таким образом, длина П. д. Б. равна k n
+ n
− 1.)
(Также П. д. Б. называют бесконечную периодическую последо- вательность с периодом k n
, каждая подпоследовательность которой длины k n
+ n
− 1 является П. д. Б. с параметрами n и k.)
2.5.6.
Постройте последовательность де Брёйна с параметрами k =
2
(‘двоичную’) и
(a) n = 3, начинающуюся с 111;
(b) n = 4, начинающуюся с 1011;
(c) n = 4, заканчивающуюся на 1010.
2.5.7.
Правило «0 лучше 1». Рассмотрим последовательность из 0
и 1, построенную по следующим правилам. Она начинается с k еди- ниц. Дальше мы пишем 1, только если при написании 0 не все под- последовательности длины k новой последовательности различны.
Если даже при написании 1 не все подпоследовательности длины k
новой последовательности различны, то заканчиваем написание последовательности. Докажите, что таким образом получится по- следовательность де Брёйна.
2.5.8.
Дан связный ориентированный мультиграф с n вершинами.
Входящая степень d k
каждой вершины k равна исходящей.
2. ОСНОВЫ ТЕОРИИ ГРАФОВ
65
(a) Существует дерево, содержащее все вершины этого мультигра- фа, все рёбра которого направлены в сторону вершины 1.
(b) Фиксируем дерево T из (a). Будем обходить этот граф (по стрелкам), проходя по каждому ребру не более одного раза. Снача- ла выйдем из вершины 1 в произвольном направлении. Далее, пусть мы пришли в некоторую вершину v. Выходим из нее по любому реб- ру, не принадлежащему T , если это возможно. А если невозможно,
то выходим из нее по ребру, принадлежащему T (такое ребро един- ственно). Докажите, что движение закончится в вершине 1, и что в результате получится ориентированный эйлеров цикл.
(c) Число ориентированных эйлеровых циклов в этом мультигра- фе кратно числу (d
1
− 1)! · . . . · (d n
− 1)!.
2.6 Гамильтоновы пути и циклы
Гамильтонов путь (цикл) в графе — путь (цикл), проходящий через каждую вершину ровно по одному разу.
2.6.1.
Грани гамильтонова плоского графа можно правильно рас- красить в 4 цвета.
Напомним (§2.1), что длина пути — число его ребер (а не вер- шин).
2.6.2.
(a) Если граф связен и 2e
> n
2
− 3n + 6, то в нём есть гамильтонов цикл.
(b) Теорема Дирака. Граф, сумма степеней любых двух несмеж- ных вершин которого не меньше n, имеет гамильтонов цикл.
(c) Лемма Дирака. Если a
0
. . . a s
— максимальный из путей в гра- фе, проходящих по каждой своей вершине только один раз, s
> 3
и deg a
0
+ deg a s
> s, то в этом графе есть несамопересекающийся цикл длины s.
(d) Если в связном графе есть несамопересекающийся цикл длины s < n
, то в этом графе есть путь длины s, проходящий по каждой своей вершине только один раз.
(e) Граф, сумма степеней любых двух несмежных вершин кото- рого не меньше n − 1, имеет гамильтонов путь.
66
Элементы дискретной математики в задачах
2.6.3.
Пусть для некоторых графа и целого k
> 2 среди любых k + 1
вершин графа есть ребро и после удаления любого набора из k − 1 вершины граф остается связным. Тогда в этом графе есть гамильтонов цикл.
2.6.4.
Пусть среди любых k + 1 вершин графа есть ребро и после удаления любого набора из k − 1 вершины граф остается связным.
(a) В этом графе есть хотя бы один несамопересекающийся цикл.
(b) Обозначим через v
1
, . . . , v s
максимальный несамопересекаю- щийся цикл в этом графе. Обозначим через W любую компонен- ту связности графа, полученного удалением вершин этого цикла из исходного графа. Обозначим через X множество вершин цикла,
соседних с W .
Тогда |X| > k.
(c) Вершины v i
, v i+1
не лежат одновременно в X.
(d) Если v i
, v j
∈ X, то в графе нет ребра v i+1
v j+1 1
2 6
11 16 15 4
12 10 8
7 9
5 3
14 13
Рис. 7: Есть ли в этом графе гамильтонов путь?
2.6.5.
(a) Есть ли гамильтонов путь в графе на рисунке 7?
(b) Есть ли гамильтонов цикл в графе на рисунке 8?
(c) Для каких n есть гамильтонов цикл в графе, вершинами кото- рого являются 3-элементные подмножества n-элементного множе- ства, и два подмножества соединены ребром, если они пересекаются ровно по одному элементу?
2. ОСНОВЫ ТЕОРИИ ГРАФОВ
67
Рис. 8: Граф многогранника Гринбергса. Есть ли в нём гамильтонов путь?
2.6.6.
Максимальное число попарно непересекающихся по рёбрам гамильтоновых циклов в графе K
n равно
[
n
− 1 2
]
2.6.7.
(a) В любом турнире имеется ориентированный гамильто- нов путь.
(b) Для любого n существует турнир с n вершинами, в котором имеется не менее n!/2
n ориентированных гамильтоновых путей.
2.6.8.
Рёберным графом графа G называется граф, вершины ко- торого — рёбра графа G; две вершины рёберного графа соединены ребром, если соответствующие рёбра графа G имеют общую верши- ну. Найдите в терминах графа G необходимое и достаточное условие наличия гамильтонова цикла в его рёберном графе.
См. также [Ve].
2.7 Экстремальные задачи (теорема Турана)
2.7.1.
Пункты этой задачи, кроме (b), являются различными вер- сиями и частными случаями теоремы Турана.
Треугольником в графе называется цикл длины 3.
(a) Если граф не содержит треугольников, то e
6 n
2
/4.
(b) Если e = [n
2
/4] + 1
, то в графе есть по крайней мере [n/2]
треугольников.
68
Элементы дискретной математики в задачах
(c) Если n = km и граф не содержит (k + 1)-клики, то 2e
6 k(k −
1)m
2
. (Переходя к дополнительному графу, получаем, что если n =
km и граф не содержит (k + 1)-антиклики, то 2e
> km(m − 1).)
(d) Если граф не содержит (k+1)-антиклики, то 2e
> km(m−1)+
2mr
, где m := [n/k] и r := k{n/k}.
2.7.2.
(a) Если граф не содержит несамопересекающегося цикла длины 4, то e < n
3/2
(b) Если граф не содержит подграфа K
3,2
, то e < 2n
3/2
(c) Если граф не содержит подграфа K
3,3
, то e < 2n
5/3
(d)* Для любых целых s, t, 2 6 s 6 t, если граф не содержит подграфа K
s,t
, то e < tn
2
−1/s
2.7.3.
Для любых n точек на плоскости существует не более n диа- метров, т. е. (неупорядоченных) пар точек, расстояние между ко- торыми равно максимуму из всех возможных расстояний между парами из этих n точек.
2.7.4.
Для любых n точек A
1
, . . . , A
n в R
d обозначим через D(A
1
, . . . , A
n
)
число (неупорядоченных) пар точек, расстояние между которыми равно 1. Обозначим
E
n
(d) = max
{D(A
1
, . . . , A
n
) : A
1
, . . . , A
n
∈ R
d
}.
Тогда:
(a) E
n
(2) > n[log
2
n]/4
; (b) E
n
(2)
6 2n
3/2
; (c) E
n
(3)
6 2n
5/3
;
(d)
(n
− 1)
2 4
6 E
n
(4)
6 2(n + 4)
2 5
2.7.5.
(a) Пусть V — 11
q
-элементное подмножество пространства
R
q
(определение пространства R
q см. в главе 7) любое 10
q
-элемент- ное подмножество которого содержит две точки x, y на расстоянии
1: |x−y| = 1. Докажите, что для достаточно большого q количество единичных расстояний между точками множества V больше, чем
12
q
/2
:
1 2
|{(x, y) ∈ V × V : |x − y| = 1}| >
12
q
2
(b) Докажите, что в условиях предыдущего пункта можно заме- нить число 12
q
/2
на 12
q
72
Элементы дискретной математики в задачах
2.10 Степенн ´
ые последовательности. В.А. Волков, М.Н.
Вялый и А.Б. Скопенков
1.
(a) При каких E и n существует граф с n вершинами и E
ребрами, каждая вершина которого имеет степень 3? (Такие графы называют кубичными или правильными степени 3.)
1 2 3 4 5 6
(b) При каких n и k существует граф на n вершинах, степени которых равны k?
2.
Графом с петлями и кратными ребрами называется набор точек среди которых некоторые пары, возможно совпадающих, вер- шин соединены линиями. Ребра, соединяющие вершину саму с со- бой, называются петлями, а несколько ребер, соединяющих одну и ту же пару вершин — кратными ребрами.
Даны целые положительные числа n, d
1
, . . . , d n
(a) При каких условиях существует граф с n вершинами (воз- можно, имеющий петли и кратные ребра), из которых выходит d
1
, . . . , d n
ребер, соответственно?
(b) То же, если граф не может иметь кратных ребер (но, воз- можно, имеет петли, даже кратные).
(c) То же, если граф не может иметь петель (но, возможно, имеет кратные ребра).
(d)* То же, если граф не может иметь ни петель, ни кратных ребер.
Основной вопрос (задача 2d): какие последовательности являют- ся степенными, то есть представляют последовательность степеней вершин некоторого графа без петель и кратных ребер? Невозраста- ющую последовательность из n положительных целых чисел будем называть правильной, если первый ее член не превосходит n − 1, а сумма всех членов четна.
3.
Докажите, что невозрастающая степенная последовательность является правильной.
4.
Являются ли степенными последовательности
(a) (4 3
, 1 6
)
,
(b) (6 4
, 2 3
)
,
(c) (5 3
, 3 3
)
,
(d) (18 10
, 12 3
, 6 8
)
,
(e)
(15 8
, 10 6
, 3 4
)
?
(Мы используем экспоненциальную запись невозрастающих це- лочисленных последовательностей: a k
означает, что k последова-
2. ОСНОВЫ ТЕОРИИ ГРАФОВ
73
тельных членов последовательности равны a.)
5.
Докажите, что для степенной последовательности d
1
, . . . , d n
(
∗)
k
∑
i=1
d i
6 k(k−1)+
n
∑
i=k+1
min(k, d i
)
для любого k = 1, 2, . . . , n−1.
6.
Пусть a, b, c, d — различные вершины графа, причем (ab),
(cd)
— ребра, а (ac), (bd) — не ребра. Назовем обменом преобра- зование графа, состоящее в удалении ребер (ab), (cd) и добавлении ребер (ac), (bd).
Пусть G
1
, G
2
— два графа с одинаковыми последовательностя- ми степеней d
1
> d
2
> . . . > d n
. Докажите, что обменами можно перевести граф G
1
в граф G
2 7.
(a) Приведите пример правильной, но не степенной, последо- вательности из n чисел, лежащих в промежутке [2004, n/2004].
(b) Докажите, что любая правильная последовательность из n чисел, меньших
√
n/2
, — степенная.
8.
Пусть последовательность d
1
, d
2
, . . . , d n
правильная, выполне- но условие (*) и не все d i
равны. Обозначим t = min{i : d i
> d i+1
}.
Определим новую последовательность c = (c
1
, c
2
, . . . , c n
)
формулой c i
:=
{
d i
,
i
̸= t, n,
d i
− 1, i = t, n.
Докажите, что если последовательность
(a) c степенная, то и d степенная.
(b) d правильная, то и c правильная.
9.
В обозначениях предыдущей задачи докажите условие (*) с заменой d на c
(a) при k
> t; (b) при d k
6 k−1 6 t−2; (c) при d k
= k
6 t−1;
(d) при d k
> k + 1 6 t.
10.
Докажите, что невозрастающая последовательность являет- ся степенной тогда и только тогда, когда сумма ее членов четна и выполнено условие (*).
11.*
(abcd) То же, что в задаче 2, для связных графов.