Файл: Элементы комбинаторики.pdf

74
Элементы дискретной математики в задачах
(a’b’c’d’) Сформулируйте и решите аналог задачи 2 для ориен- тируемых графов.
Ответы, указания и решения
2.9.1.
(a) Ясно, что цепь и антицепь могут пересекаться не более чем по одному элементу. Поэтому количество цепей, на которые можно разбить частично упорядоченное множество, не меньше его диаметра.
(b) (Доказательство теоремы Дилуорса.) Рассмотрим мини- мальный контрпример. Пусть C — цепь диаметра D. Тогда каж- дый элемент множества M − D либо больше некоторого элемента из D, либо строго его меньше. Таким образом, M −D есть несвязное объединение двух частей M
′
(выше D) и M
′′
(ниже D).
Если M
′
∪ D и M
′′
∪ D разбиваются на d цепей, то и все M раз- бивается на d цепей (каждая цепь склеивается из верхней и нижней половин).
Если
M
′
̸= ∅ и M
′′
̸= ∅, то #(M
′
∪D) < #M и #(M
′′
∪D) < #M.
Мы осуществили спуск. В противном случае имеется не более двух максимальных антицепей: верхняя (если M
′
=
∅) и нижняя (если
M
′′
=
∅). Рассмотрим случай наличия только верхней антицепи
(случай наличия только нижней антицепи симметричен).
Пусть имеется единственная максимальная антицепь D и x ∈
D
. Тогда M − {x} имеет диаметр d − 1 и в силу минимальномти контрпримера разбивается на d − 1 цепь C
1
, . . . , C
d
−1
. Поэтому x ∪
{C
i
}
d
−1
i=1
есть искомое разбиение на d цепей.
Пусть имеются две максимальные антицепи D
1
и D
2
. Легко по- казать, что найдется пара элементов x ∈ D
1
и y ∈ D
2
таких, что x
≺ y. Тогда диаметр множества M −{x, y} строго меньше диаметра
M
и доказательство завершается аналогично.
2.10.1.
(a) Ответ: такой граф существует при (V, E) = (2k, 3k)
для произвольного целого k > 1.
Рассмотрим произвольный кубический граф: каждая его верши- на имеет степень 3. Сумма степеней всех вершин есть 2E. Поэтому

2. ОСНОВЫ ТЕОРИИ ГРАФОВ
75 3V = 2E
. Тогда пары чисел (V, E) имеют вид (2k, 3k) для некото- рого натурального k. Так как нет петель и кратных ребер, то k = 1
невозможно.
При k > 1 условию удовлетворяют, например, 2k-угольник с проведенными в нем диагоналями, соединяющими i-тые и (i + k)- тые вершины.
(b) Ответ: такой граф существует при k ∈ {0, 1, . . . , n − 1} и kn четном.
Для доказательства достаточности расположите вершины гра- фа в вершинах правильного n-угольника. Соедините ребрами вер- шины, расстояние между которыми по окружности не превосходит
[k/2]
. Для четного k построение графа закончено. Для нечетного k число n четно, поэтому можно и нужно добавить большие диагона- ли.
Обозначим e := (d
1
+
· · · + d n
)/2 2.10.2.
Ответы: (a,b) e целое.
(c) e целое и d i
6 e для любого i
(d) См. задачи 5 и 10.
(с) Теорема. Граф без петель (но, возможно, с кратными реб- рами и, возможно, не связный) с n вершинами степеней d
1
, d
2
, ..., d n
>
0
существует тогда и только тогда, когда e := (d
1
+
· · · + d n
)/2
целое и d i
6 e для любого i.
Доказательство (предложено А. Руховичем). Необходимость целочисленности e вытекает из того, что e равно числу ребер в графе. Второе условие необходимо, поскольку в графе нет петель, а значит степень каждой вершины не больше суммы степеней осталь- ных вершин.
Докажем достаточность индукцией по e. База индукции: утвер- ждение для e = 0 очевидно. Докажем шаг индукции. Пусть утвер- ждение для e < k. Докажем, что оно верно и для e = k
> 1. Из k
> 1 и условия d i
6 e следует, что найдутся хотя бы две вершины ненулевой степени. Можно считать, что d
1
> d
2
> ... > d n
. Рас- смотрим набор d
1
− 1, d
2
− 1, d
3
, ..., d n
. Условия теоремы для него выполнены, поскольку сумма степеней вершин уменьшилась на 2,
а степень каждой вершины понизилась не более, чем на 1. Поэто- му можно воспользоваться предположением индукции: существует граф для набора d
1
− 1, d
2
− 1, d
3
, ..., d n
. В этом графе соединим реб-

76
Элементы дискретной математики в задачах ром вершины 1 и 2. Поскольку эти вершины различны, то петель не появилось. Следовательно, новый граф не содержит петель. Ясно,
что набор степеней его вершин — d
1
, d
2
, d
3
, ..., d n
. QED
2.10.4.
(a,c) да.
(b,d,e) нет.
2.10.5.
Оцените сверху количество ребер, выходящих из первых k
вершин.
2.10.8.
(a) Если хотим добавить ребро AB, а оно уже есть, то возьмем вершину C, не соединенную с A. А потом возьмем вершину
D
, соединенную с C, но не с B.
Доказательство С.А. Чоудама теоремы о степенных последо- вательностях (решение задач 9, 10). Докажем, что если последо- вательность d
1
, d
2
, . . . , d n
неотрицательных чисел правильная и k
∑
i=1
d i
6 k(k − 1) +
n
∑
j=k+1
min(k, d j
),
для любого k = 1, 2, . . . , n − 1, то существует граф со степенями d
1
, d
2
, . . . , d n
Доказательство ведем индукцией по сумме элементов последо- вательности
∑
d i
. Случай, когда все d i
равны, рассмотрен в зада- че 1b. Пусть теперь не все d i
равны. Можно считать, что d n
> 0
Обозначим 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.
Обозначим
S
k
=
k
∑
i=1
d i
,
S
′
k
=
k
∑
i=1
c i
. По задаче 8 достаточно до- казать неравенства
(
∗)
S
′
k
6 k(k − 1) +
n
∑
i=k+1
min
{k, c i
}.
При k
> t
S
′
k
= S
k
−1 6 k(k−1)+
n
∑
i=k+1
min
{k, d i
}−1 6 k(k−1)+
n
∑
i=k+1
min
{k, c i
}.

2. ОСНОВЫ ТЕОРИИ ГРАФОВ
77
Пусть теперь k
6 t − 1. Тогда S
′
k
= S
k
= kd k
Для d k
6 k − 1 неравенство (*) тривиально.
Для d k
= k
S
′
k
− k(k − 1) = k
2
− k(k − 1) = k
(3)
= d k+1
(4)
6 6 d k+1
+
(
n
∑
i=k+2
d i
− 2
)
(5)
=
n
∑
i=k+1
min
{k, c i
}, где
• равенство (3) выполнено, поскольку k 6 t − 1;
• неравенство (4) очевидно, если k + 2 < n; если же k + 2 = n, то d = ((n
−2)
(n
−1)
, d n
)
и d n
> 2 в силу четности суммы d
1
+d
2
+
· · ·+d n
• равенство (5) выполнено, поскольку min{k, c i
} = c i
при i
>
k + 1
Случай d k
> k+1. Если d n
> k+1, то min{k, d i
} = min{k, c i
} = k при i
> k + 1 и неравенство (*) следует из аналогичного для S
k
Пусть теперь d n
6 k. Имеем min
{k, c i
} = min{k, d i
} при k+1 6 i < n и min{k, c n
} = min{k, d n
}−1.
В нашем случае S
′
k
= S
k
, поэтому достаточно показать, что
(
∗∗)
S
k
6 k(k−1)+
n
∑
i=k+1
min
{k, c i
} = k(k−1)+
n
∑
i=k+1
min
{k, d i
}−1.
Учитывая, что d k+1
= d k
> k + 1, получаем
S
k+1
= (k+1)d k
=
k + 1
k
S
k
(3)
6 (k+1)(k−1)+
k + 1
k n
∑
i=k+1
min
{k, d i
} =
= (k + 1)(k
− 1) + (k + 1) +
k + 1
k n
∑
i=k+2
min
{k, d i
}
(5)
>
> (k + 1)k +
n
∑
i=k+2
min
{k + 1, d i
} > S
k+1

78
Элементы дискретной математики в задачах
Неравенство (5) выполнено, так как при всех k + 2 6 i < n имеем нестрогое неравенство и при i = n строгое. Значит, в (3) неравенство строгое. Отсюда вытекает (**).
Комментарий.
Можно также доказать, что если для правиль- ной последовательности d
1
, . . . , d n
выполняются неравенства из за- дачи 5, то последовательность, полученная из d
2
−1, d
3
−1, . . . , d d
1
+1
−
1, d d
1
+2
, d d
1
+3
, . . . , d n
−1
, d n
расположением чисел по возрастанию, пра- вильная и для нее выполняются аналогичные неравенства.
2.10.11.
(abcd) То же, что в соответствующих пунктах задачи
2, с добавлением условия e
> n − 1.
(c) Теорема. Связный граф без петель (но, возможно, с крат- ными ребрами) с n вершинами степеней d
1
, d
2
, ..., d n
> 1 сушеству- ет тогда и только тогда, когда выполнены следующие три усло- вия:
(1) e := (d
1
+ d
2
+ ... + d n
)/2
целое;
(2) d i
6 e для любого i;
(3) n − 1 6 e.
Доказательство (предложено А. Руховичем). Для доказатель- ства необходимости обозначим через e количество ребер в графе.
Условия (1) и (2) необходимы по задаче 2.c. Необходимость условия
(3) легко проверяется.
Для доказательства достаточности рассмотрим граф, получен- ный по задаче 2.c. Обозначим через c количество компонент связ- ности этого графа.
Докажем, что если c > 1, то можно уменьшить количество ком- понент связности, не меняя степеней вершин. Ввиду условия (3)
e
> n − 1 > n − c. Поэтому хотя бы в одной компоненте связности есть цикл. Тогда можно взять ребро a
1
a
2
этого цикла и ребро b
1
b
2
из другой компоненты связности. Удалим эти ребра, и вместо них добавим ребра a
1
b
1
и a
2
b
2
(ср. с задачей 6). Тогда степени вершин сохранятся, а количество компонент связности уменьшится на 1.
Такими операциями можно понизить количество компонент связ- ности до 1. Получится связный граф без петель с заданными сте- пенями вершин. QED

3. РАСКРАСКИ ГРАФОВ И МНОГОЧЛЕНЫ
95 3 Раскраски графов и многочлены
3.1 Раскраски графов
Раскраска графа (т.е. вершин графа) в несколько цветов назы- вается правильной, если концы любого ребра разноцветны.
3.1.1.
Докажите, что следующие три условия эквивалентны:
• граф двудолен;
• граф можно правильно раскрасить в 2 цвета;
• граф содержит циклы только чётной длины.
3.1.2.
(a) Если в графе степень каждой вершины не превосходит d
, то его можно правильно раскрасить в d + 1 цвет.
(b) Если в связном графе степень каждой вершины не превосхо- дит d и есть вершина степени менее d, то его можно правильно раскрасить в d цветов.
(c) Если в связном графе степень каждой вершины не превосходит d
, и есть вершина, после удаления которой граф перестает быть связным, то граф можно правильно раскрасить в d цветов.
(d) Если связный граф G, имеющий более двух вершин, при уда- лении некоторого ребра распадается на два графа, каждый из ко- торых можно правильно раскрасить в d цветов, то и исходный граф можно правильно раскрасить в d цветов.
3.1.3.
Если для некоторого k в графе с n вершинами среди любых k + 1
вершин есть ребро, то граф невозможно правильно покрасить менее, чем в n/k цветов.
3.1.4.
В выпуклом многоугольнике провели несколько диагоналей,
не имеющих общих внутренних точек. Полученный плоский граф можно правильно раскрасить в 3 цвета.
3.1.5.
(a) В связном графе степень каждой вершины не превосхо- дит трёх. Известно, что его можно правильно раскрасить в 3 цвета так, чтобы соседи некоторой вершины были одноцветны. Добавили одну вершину и выходящие из нее рёбра так, что по-прежнему сте- пени всех вершин не превосходят трёх. Докажите, что полученный граф можно правильно раскрасить в 3 цвета.

3. РАСКРАСКИ ГРАФОВ И МНОГОЧЛЕНЫ
97 3.1.9.
Ориентированный граф, из каждой вершины которого вы- ходит не более d рёбер, можно правильно раскрасить в 2d + 1 цвет.
3.1.10.
Имеется несколько цветов. Каждой вершине двудольного графа с n
6 2
k
−1
вершинами сопоставлено не менее, чем k цве- тов. («Списки» цветов, сопоставленные разным вершинам, могут быть и одинаковыми, и различными.) Тогда существует правиль- ная раскраска графа, приписывающая каждой вершине некоторый сопоставленный ей цвет.
3.1.11.
(a) Если степень каждой вершины графа не превосходит d
, то рёбра графа можно раскрасить в d + 1 цвет так, чтобы рёбра,
имеющие общий конец, были разноцветны.
(b) Существует такая раскраска рёбер графа K
m,n в два цвета, что число одноцветных подграфов K
a,b не больше
(
m a
)(
n b
)
2 1
−ab
3.2 Хроматические число и индекс
Хроматическим числом χ(G) графа G называется минимальное количество цветов, в которые можно правильно покрасить вершины графа G.
3.2.1.
Если при удалении из графа любой вершины хроматическое число уменьшается, то χ(G)
6 1 + [2e/n].
3.2.2.
(a) На какое число может измениться хроматическое число графа, если добавить к графу одно ребро? Или, формально, най- дите все целые k, для которых существует граф G и его ребро u такие, что χ(G) − χ(G − u) = k.
(b) χ(V, E
1
∪E
2
)
6 χ(V, E
1
)χ(V, E
2
).
(Напомним, см. §2.1, что через
(V, E)
обозначается граф со множеством вершин V и множеством ребер E.)
(c) Для любых r
1
, r
2
∈ N постройте такие графы (V, E
1
)
и (V, E
2
)
,
что χ(V, E
1
∪E
2
) = χ(V, E
1
)χ(V, E
2
)
, χ(V, E
1
) = r
1
и χ(V, E
2
) = r
2 3.2.3.
Следующий алгоритм раскраски вершин графа называется жадным. Сначала все вершины произвольно нумеруются. После этого последовательно каждую вершину, начиная с первой, красим

98
Элементы дискретной математики в задачах в цвет с минимальным номером, отсутствующим среди уже покра- шенных соседей этой вершины.
(a) Вершины произвольного графа G можно занумеровать так,
чтобы жадный алгоритм его раскраски использовал ровно χ(G)
цветов.
(b) Для каждого целого k > 0 постройте такие двудольный граф и нумерацию его вершин, что раскраска графа, построенная жадным алгоритмом, отвечающим построенной нумерации, имеет не менее k
цветов.
Эта задача показывает, что «качество» раскраски, построенной жадным алгоритмом, сильно зависит от упорядочения вершин.
Раскраска рёбер графа называется правильной, если любые два ребра, имеющие общую вершину, окрашены в разные цвета. Хро- матический индекс графа — минимальное число цветов, в которые можно правильно раскрасить рёбра этого графа.
Рис. 10: Граф Петерсена
3.2.4.
Исследуйте на планарность (§2.4), найдите хроматическое число и хроматический индекс графов:
(a) графа Петерсена, изображённого на рисунке 10;
(b) графов с рисунка 11.
3.3 Хроматический многочлен и многочлен Татта
Значением хроматической функции χ
G
графа G в точке t назы- вается количество правильных раскрасок графа в t цветов.

3. РАСКРАСКИ ГРАФОВ И МНОГОЧЛЕНЫ
99
◦
jjjj jjj
T
T
T
T
T
T
T
◦
=
=
=
''
''
''
''
''
◦







◦
I
I
I
I
I
I
I
I
◦
◦
uu uu uu uu
◦


◦
=
=
=
◦
◦
◦
GF
ED
C


=
=
=
=
N
N
N
N
N
N
◦


ppp ppp
◦


◦
ppp ppp
◦
N
N
N
N
N
N
◦
=
=
=
=
◦
@A
BC
--
--
--
-
◦
◦
jjjj jjj
T
T
T
T
T
T
T



◦
=
=
=
''
''
''
''
''
◦







◦
◦
◦
uu uu uu uu
◦


◦
=
=
=
◦
◦
1 2
3
Рис. 11: Исследуйте на планарность, найдите хроматическое число и хроматический индекс графов
3.3.1.
Найдите хроматическую функцию для (a) полного графа;
(b) графа, не имеющего ребер; (c) пути; (d) цикла; (e) де- рева с n вершинами.
3.3.2.
(a) χ
G
= χ
G
−u
− χ
G/u для любого ребра u графа G.
(b) Теорема Биркгофа–Уитни. Для каждого графа G существует ровно один такой многочлен, что для любого t число χ
G
(t)
правиль- ных раскрасок графа G в t цветов равно значению в точке t этого многочлена.
Ввиду этой теоремы хроматическая функция называется хромати- ческим многочленом и считается определенной не только для целых t > 0
(ср. с (e)).
(c) Степень хроматического многочлена χ
G
равна n, старший ко- эффициент равен 1, второй коэффициент равен (−e), коэффициен- ты знакопеременны (т. е. коэффициент при t n
−2k неотрицателен и коэффициент при t n
−2k+1
неположителен для любого целого k).
(d) Третий коэффициент хроматического многочлена графа, счи- тая с самого старшего, однозначно определяется набором подгра- фов графа, содержащих 3 вершины.
(e) Число |χ
G
(
−1)| равно числу ациклических ориентаций графа
G
, т. е. числу способов так расставить стрелки на его рёбрах, чтобы полученный ориентированный граф не содержал ориентированных циклов.
3.3.3.
(a) Если хроматический многочлен графа равен t(t−1)
n
−1
,

100
Элементы дискретной математики в задачах то граф — дерево.
(b) Не существует графа с хроматическим многочленом t
4
− 3t
3
+
3t
2 3.3.4.
(a) Найдите χ
G
⊔H
, зная χ
G
и χ
H
(b) Путь из m вершин «прицепили» за один из концов к одной из вершин графа G, содержащего n вершин. Выразите хроматический многочлен полученного графа с m + n − 1 вершиной через χ
G
(c) Если H, K — графы, на которые распадается связный граф G
при удалении его ребра, то tχ
G
= (t
− 1)χ
H
χ
K
3.3.5.
Обозначим через χ
′
G
= χ
′
G
(t)
количество правильных рас- красок рёбер графа G в t цветов.
(a) Функция χ
′
G
является многочленом от t.
(b) Старший моном в χ
′
G
равен t e
(c) Коэффициент при t e
−1
в χ
′
G
равен −
∑
v
∈V (G)
(
deg v
2
)
Мостом называется ребро, при удалении которого количество связных компонент графа увеличивается. Граф называется лесом,
если он не содержит несамопересекающихся циклов. Напомним, что при стягивании ребра в мультиграфах, в отличие от графов, полу- чившиеся ребра кратности больше 1 не заменяются на ребра крат- ности 1.
3.3.6.
Для любого мультиграфа G выполнено T
G
= T
G
−u
+ T
G/u
,
где u — ребро мультиграфа G, не являющееся ни петлей, ни мостом,
и T
G
— число
(a) остовных лесов (т. е. объединений остовов его компонент);
(b) таких наборов рёбер, что для любой компоненты связности графа лежащие в ней рёбра из набора образуют связный подграф;
(c) подграфов, являющихся лесами.
3.3.7.
Даны связный мультиграф и набор ребер в нем, не содержа- щий несамопересекающихся циклов и ни одного ребра некоторого максимального дерева. В мультимножестве (т. е. в неупорядочен- ном наборе с кратностями) мультиграфов разрешается для любого мультиграфа G и его ребра u, не являющегося ни петлёй, ни мостом,
заменять один мультиграф G на два мультиграфа G − u, G/u. Эта