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

2. ОСНОВЫ ТЕОРИИ ГРАФОВ
53
вершинами, то при стягивании любого его ребра получится цикл с тремя вершинами.
Ориентированным графом (без петель и кратных рёбер) G =
(V, E)
называется конечное множество V = V (G), некоторые упоря- доченные пары несовпадающих элементов которого выделены. Мно- жество выделенных пар обозначается E = E(G). Таким образом,
E
⊂ {(x, y) ∈ V × V | x ̸= y}. Если выделены и пара (a, b), и пара
(b, a)
, то это ребро не называется кратным.
Ориентированный путь в ориентированном графе — такая по- следовательность вершин, что в каждую следующую вершину ведет ориентированное ребро из предыдущей.
2.1.4.
Пусть дан ориентированный граф G, у которого на каждом ребре u написан вес f(u). (Этот вес можно понимать как работу,
которую нужно затратить для того, чтобы пройти по ребру от на- чала до конца.) Функция p : V (G) → R («потенциал») такая, что f (x, y) = p(x)
− p(y) для любого ребра u = (x, y), существует тогда и только тогда, когда сумма весов рёбер любого ориентированного цикла равна нулю (при прохождении ребра по циклу в направле- нии, противоположном ориентации, вес в сумму берётся с отрица- тельным знаком).
Турниром называется ориентированный граф, любые две вер- шины которого соединены ребром. (Т.е. для любых двух вершин v, w турнира среди его ребер есть (v, w) или (w, v), но не оба ребра сразу.)
Некоторые другие определения приведены в начале каждого раздела.
2.2 Перечисление деревьев
Граф называется деревом, если он связен и не содержит неса- мопересекающихся циклов. Остовом графа называется любой его подграф, являющийся деревом и содержащий все вершины графа.
2.2.1.
(a) В любом дереве найдется лист, т.е. вершина степени 1.
(b) В любом дереве с n вершинами n − 1 ребро.

54
Элементы дискретной математики в задачах
(c) В любом дереве между любыми двумя вершинами существу- ет единственный путь.
(b’) Граф с n вершинами является деревом тогда и только тогда,
когда он не содержит несамопересекающихся циклов и имеет n − 1
ребро.
(b”) Граф с n вершинами является деревом тогда и только тогда,
когда он связен и имеет n − 1 ребро.
(c’) Если в графе между любыми двумя вершинами существует единственный путь, то граф является деревом.
(d) Последовательность из n натуральных чисел является после- довательностью степеней вершин некоторого дерева тогда и только тогда, когда сумма её членов равна 2n − 2.
Заметим, что графы ({1, 2, 3}, {{1, 2}}) и ({1, 2, 3}, {{1, 3}}) раз- личны. Графом называется именно граф, а не класс изоморфизма графов (определение изоморфизма приведено в начале §2.3). Или,
говоря неформально, вершины графов считаются занумерованны- ми. Поэтому вместо слова ‘граф’ иногда употребляют термин ‘по- меченный граф’.
2.2.2.
Каких графов с данными n вершинами больше:

(a) имеющих изолированную вершину или не имеющих?
(b) связных или несвязных?
2.2.3.
(a) Формула Кэли. Число деревьев с данными n вершинами равно n n
−2
(b) Если сумма целых положительных чисел d
1
, . . . , d n
равна 2n−
2
, то число деревьев с данными n вершинами, у которых i-я верши- на имеет степень d i
, равно
(n
− 2)!
(d
1
− 1)! · . . . · (d n
− 1)!
Иными словами, (x
1
+ . . . + x n
)
n
−2
=
∑
T
x deg
T
(1)
−1 1
· . . . · x deg
T
(n)
−1
n
,
где сумма берётся по всем деревьям T с вершинами 1, 2, . . . , n, и через deg
T
(k)
обозначена степень вершины k дерева T .
(c) * Пусть T
1
, . . . , T
r
— деревья, множества вершин которых не пе- ресекаются. Сколько есть деревьев, множество вершин которых есть объединение множества вершин этих r деревьев, и которые содер- жат T
1
, . . . , T
r
?

2. ОСНОВЫ ТЕОРИИ ГРАФОВ
55 2.2.4.
Код Прюфера сопоставляет дереву с вершинами 1, 2, . . . , n по- следовательность чисел от 1 до n по следующему алгоритму. Снача- ла код Прюфера — пустое слово. Пока количество вершин больше двух,
1. Выбирается лист (см. задачу 2.2.1) v с минимальным номером.
2. В код Прюфера добавляется номер вершины, смежной с v.
3. Вершина v и инцидентное ей ребро удаляются из дерева.
Когда осталось две вершины, алгоритм завершает работу.
(a) Найдите код Прюфера дерева с вершинами 1, 2, . . . , 10 и рёб- рами (8,9),(8,4),(4,10),(10,3),(3,5),(10,6),(10,1),(1,7),(1,2).
(b) Восстановите дерево по коду Прюфера 1,1,2,5,4,2,7.
(c) Код Прюфера определяет взаимно-однозначное соответствие между множеством деревьев с данными n вершинами и множеством слов длины n − 2 из этих вершин.
(d) В коде Прюфера вершина степени d встречается d − 1 раз.
2.2.5.
Граф называется унициклическим, если он становится дере- вом после удаления некоторого ребра. (Или, эквивалентно, если он связен и имеет ровно один — с точностью до циклического сдвига и симметрии — несамопересекающийся цикл.)

(a) Каких графов больше, деревьев с данными 100 вершинами или унициклических графов с данными 98 вершинами?
(b) Выразите число унициклических графов с данными n верши- нами в виде суммы не более чем n слагаемых.
2.2.6.
(a) В дереве нет непустых подграфов, у которых степень каждой вершины чётная и положительная.
(b) Для графа G обозначим через h
1
(G)
число его подграфов без изолированных вершин, у которых степень каждой вершины чёт- на. (Пустой подграф удовлетворяет этому условию.) Докажите, что h
1
(G)
– степень двойки. Выразите h
1
(G)
через количества n вер- шин, e рёбер и k компонент связности графа.
Замечание. Такие подграфы называют циклами в смысле теории гомологий (не путайте с циклами в смысле теории графов). Как они возникают, написано, например, в [S3, §6].
(c) На рёбрах дерева стоят знаки + и −. Разрешается менять зна- ки на всех рёбрах, выходящих из одной вершины. Тогда из любой расстановки можно получить любую другую.

56
Элементы дискретной математики в задачах
(d) Для графа G обозначим через h
1
(G)
наибольшее количество расстановок знаков + и − на его рёбрах, ни одну из которых нельзя получить из другого описанными выше операциями. Докажите, что h
1
(G)
— степень двойки. Выразите h
1
(G)
через n, e и k.
Замечание. В теории когомологий такие узоры называют коцикла- ми, а приведенное отношение эквивалентности на коциклах — ко- гомологичностью. Как возникает когомологичность коциклов, на- писано, например, в [S7, §11.1, §11.2].
(e)* Докажите, что h
1
(G)
и h
1
(G)
не меняются при стягивании реб- ра, и выведите отсюда, что h
1
(G) = h
1
(G)
2.3 Графы с точностью до изоморфизма
Грубо говоря, графы изоморфны, если они одинаковы (при этом их изображения на плоскости могут быть разными). Формально,
графы G
1
и G
2
называются изоморфными, если существует взаимно однозначное отображение f : V (G
1
)
→ V (G
2
)
, удовлетворяющее условию: вершины A, B ∈ V (G
1
)
соединены ребром в том и только в том случае, если вершины f(A), f(B) ∈ V (G
2
)
соединены ребром.
◦
lll lll lll lll



'
'
'
'
'
'
'
'
'
◦
◦



◦
>
>
>
>
>
>
◦
◦
◦
lll lll lll lll uu uu uu uu
'
'
'
'
'
'
'
'
'
◦
◦
◦
uu uu uu uu
>
>
>
>
>
>
◦
◦
◦


◦
=
=
=
=
vv vv vv vv vv
◦
=
=
=
=
◦


◦
◦
◦


I
I
I
I
I
I
I
I
I
I
◦
=
=
=
=
vv vv vv vv vv
◦
=
=
=
=
◦


◦
◦

2. ОСНОВЫ ТЕОРИИ ГРАФОВ
57
(b) клик размера k в графе K
m,n
,
(c) независимых множеств размера k в графе K
n
,
(d) независимых множеств размера k в графе K
m,n
,
(e) подграфов в K
n
, изоморфных K
k,l
,
(f) подграфов в K
m,n
, изоморфных K
k,l
Будьте внимательны: эти задачи простые, но почти все требуют разбора случаев.
2.3.3.
Перечислите все попарно неизоморфные
(a) графы с четырьмя вершинами,
(b) связные графы с пятью вершинами и пятью рёбрами,
(c) несвязные графы с пятью вершинами.
2.3.4.

Сколько существует попарно неизоморфных графов, имею- щих 8 вершин и 25 рёбер?
2.3.5.
Количество классов изоморфизма деревьев с n вершинами
(т. е. количество различных деревьев с n незанумерованными вер- шинами) меньше 4
n
2.4 Плоские графы
Плоским графом называется изображение графа на плоскости,
для которого любые два ребра пересекаются только по их общим вершинам (в частности, если таких вершин нет, то не пересекаются).
Иногда такое изображение называют просто графом, но это неточ- но, поскольку один и тот же планарный граф можно изобразить
(без самопересечений) на плоскости разными способами.
Рис. 3: Различные изображения графа на плоскости
Плоский граф делит плоскость на части, называемые гранями графа. Заметим, что одна из таких частей будет ‘бесконечной’.

58
Элементы дискретной математики в задачах
2.4.1.
Дан плоский граф с треугольными гранями, имеющий бо- лее трех вершин. Удалили вершину вместе с выходящими из нее рёбрами.

(a) Верно ли, что получившаяся грань ограничена несамопересе- кающимся циклом?
(b) Верно ли, что если выкинуть еще одну вершину, то все грани опять будут ограничены несамопересекающимися циклами?
(c) Пусть в полученном графе степень каждой вершины не менее
3. Верно ли, что любую вершину нового графа можно удалить и получить граф, все грани которого будут ограничены несамопере- секающимися циклами?
2.4.2.
(a) Формула Эйлера. Для любого связного плоского графа с f гранями имеет место равенство n −e+f = 2. n, e не определены
(Доказательство см., например, в [P]. Далее этим результатом мож- но пользоваться без доказательства. Эта формула часто записыва- ется в виде V − E + F = 2.)
(b) Найдите аналог формулы Эйлера для плоского графа с k ком- понентами связности.
K
5
K
3,3
Рис. 4: Непланарные графы
2.4.3.
Применения формулы Эйлера.
(a) Ни один из графов K
5
и K
3,3
невозможно без самопересечений нарисовать на плоскости.
(b) На плоскости отмечено n точек. Разрешается соединять неко- торые две из них ломаной, не проходящей через другие точки. Два игрока по очереди соединяют ломаной какие-то две еще не соеди- нённые точки. При этом требуется, чтобы эти ломаные не самопере- секались и не пересекались нигде, кроме отмеченных точек. Проиг-

2. ОСНОВЫ ТЕОРИИ ГРАФОВ
59

рывает тот, кто не может сделать ход. Для каких n при правильной игре выигрывает тот, кто ходит первым?
(c) Перечислите все связные плоские графы (с точностью до изо- морфизма), у которых степени всех вершин равны и «степени» всех граней равны (т. е. граница каждой грани состоит из одного и того же числа рёбер).
Замечание. Если пункты (a), (b) или (c) не получаются, решайте следующие пункты. Определение изоморфизма см. в §2.3.
(d)* Выпуклых правильных многогранников (все грани — правиль- ные многоугольники с одинаковым числом сторон, степени всех вер- шин равны) ровно 5 (с точностью до изоморфизма их графов). Кон- струкцию соответствующих многогранников нужно привести, она не предполагается известной.
(e) Для любого плоского связного графа без петель и кратных рёбер, имеющего более двух вершин, 2e
> 3f и e 6 3n − 6.
(f) В любом плоском графе есть вершина степени не более 5.
(g) Если каждая вершина плоского связного графа имеет степень d
, а граница каждой грани состоит из ровно k
> 3 рёбер, то
1
d
+
1
k
=
1 2
+
1
e
2.4.4.
Картой на плоскости называется разбиение плоскости на конечное число многоугольников (возможно, ‘бесконечных’). Рас- краска карты называется правильной, если разные многоугольники,
имеющие общий граничный отрезок, имеют разные цвета. Докажи- те, что любую карту можно правильно раскрасить в
(a) 6 цветов; (b) * 5 цветов; (c)** [Всё равно не докажете.]
Замечание. Используя конструкцию двойственного графа, мож- но доказать, что правильная раскрашиваемость любой карты на плоскости в d цветов равносильна правильной раскрашиваемости любого плоского графа в d цветов (§3.1).
Граф называется планарным, если его можно без самопересече- ний нарисовать на плоскости. Ясно, что любой подграф планарного графа планарен.
Операция подразделения ребра графа показана на рисунке.

60
Элементы дискретной математики в задачах
Рис. 5: Подразделение ребра
Два графа называются гомеоморфными, если от одного можно перейти к другому при помощи операций подразделения ребра и обратных к ним; или, эквивалентно, если существует граф, полу- ченный из каждого из данных графов операциями подразделения ребра.
Ясно, что гомеоморфные графы являются или не являются пла- нарными одновременно.
Теорема Куратовского.
Граф является планарным тогда и только тогда, когда он не содержит подграфа, гомеоморфного гра- фу K
5
или K
3,3
(рис. 4). (Доказательство этой теоремы см., напри- мер, в [S1].)
2.4.5.
Придумайте алгоритм
(a) распознавания планарности графа (здесь можно использовать без доказательства теорему Куратовского);
(b)* рисования без самопересечений заведомо планарного графа на плоскости.
Найдите асимптотику сложности вашего алгоритма в зависимо- сти от числа n рёбер графа. т. е. асимптотику максимума по графам с n рёбрами от числа шагов в алгоритме, примененному к данному графу. См. «определение» нахождения асимптотики в §6.1.
Теорема Хопкрофта-Тарджана.
Существует линейный по количеству рёбер алгоритм распознавания планарности графа.
2.4.6.
(a) Теорема Фари. Плоский граф можно нарисовать без са- мопересечений на плоскости так, что все рёбра будут отрезками.
(b) Дан невыпуклый многоугольник с непрозрачными сторонами.
Назовем вершину A видимой из точки X, если внутренность отрез- ка AX не пересекается с границей многоугольника. Назовем ядром многоугольника множество его внутренних точек, из которых вид- ны все вершины многоугольника. Докажите, что если точку из ядра

2. ОСНОВЫ ТЕОРИИ ГРАФОВ
61
соединить отрезками с произвольно выбранными несколькими (не менее чем с двумя, и не обязательно со всеми) вершинами исходного многоугольника, то многоугольник разобьется на многоугольники с непустыми ядрами.
Тор и лента Мёбиуса изображены на рис. 6. Эти фигуры предпо- лагаются прозрачными, т. е. точка (или подмножество), «лежащая на одной стороне поверхности», «лежит и на другой стороне». Это аналогично тому, что при изучении геометрии мы говорим, напри- мер, о треугольнике на плоскости, а не о треугольнике на верхней
(или нижней) стороне плоскости.
Рис. 6: Тор, лист Мёбиуса и цилиндр
2.4.7.
Нарисуйте без самопересечений на торе граф
(5) K
5
;
(33) K
3,3
;
(6) K
6
;
(34) K
3,4
;
(7) K
7
;
(44) K
4,4 2.4.8.
Нарисуйте без самопересечений на ленте Мёбиуса граф
(5) K
5
;
(33) K
3,3
;
(6) K
6
;
(34) K
3,4 2.4.9.
Картой на торе называется разбиение тора на конечное чис- ло (криволинейных и изогнутых) многоугольников. Раскраска кар- ты на торе называется правильной, если разные многоугольники,
имеющие общую граничную кривую, имеют разные цвета. Любую ли карту на торе можно правильно раскрасить в
(5) 5 цветов;
(6) 6 цветов;

(7) 7 цветов?
Подробнее см. [S3, §2].
Замечание. Любой связный граф с g рёбрами можно так нарисо- вать «на сфере с g ручками» (т.е. внутри правильного 2g-угольника,
диаметрально противоположные стороны которого «склеены»), что

62
Элементы дискретной математики в задачах некоторые рёбра являются отрезками, а остальные рёбра являют- ся объединениями двух непересекающихся отрезков, у каждого из которых один конец — вершина графа, а другой конец лежит на стороне 2g-угольника.
2.5 Эйлеровы пути и циклы
Мультиграфом (или графом с петлями и кратными рёбрами)
называется квадратная таблица из целых неотрицательных чисел,
симметричная относительно главной диагонали. (Мы не использу- ем более правильную, но более громоздкую, терминологию: муль- тиграф — граф с кратными рёбрами, псевдограф — графом с пет- лями, псевдомультиграф — граф с петлями и кратными рёбрами.)
При этом число, стоящее на пересечении i-й строки и j-го столб- ца, интерпретируют как число рёбер (или кратность ребра) между вершинами с номерами i и j при i ̸= j и как число петель в вер- шине с номером i при i = j. Ребро называется кратным, если его кратность больше единицы.
Степенью вершины мультиграфа называется число выходящих из нее рёбер. При этом ребро кратности k, соединяющее вершину с другой вершиной, ‘вносит вклад’ k в степень, а петля кратности k
‘вносит вклад’ 2k в степень.
Ориентированным мультиграфом (или ориентированным гра- фом с петлями и кратными рёбрами) называется квадратная таб- лица из целых неотрицательных чисел. Если в некоторой клетке
(неважно, диагональной или нет) стоит число, большее 1, то гово- рят, что ориентированный мультиграф имеет кратные рёбра.
Читатель легко сообразит, как определить (ориентированный)
путь в (ориентированном) мультиграфе, а также как изображать с самоперечечениями на плоскости (ориентированные) мультиграфы.
2.5.1.
Сколько всего мультиграфов с данными n вершинами

(a) ориентированных без кратных рёбер, но, возможно, с петлями?
(b) неориентированных без петель, но, возможно, с кратными рёб- рами?
2.5.2.
Сколько всего мультиграфов с данными n вершинами, име- ющих k рёбер и