Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту

• Название: Редакционная коллегия серии учебники нгту
• Анкор: Судопланов
• Дата: 05.06.2022
• Размер: 2.01 Mb.
• Имя файла: Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016.pdf
• Тип: Учебники; #571403
• страница: 25 из 36

i+1
припишем минимальный цвет, не исполь- зованный при раскраске вершин из множества {a
j
| ρ(a
i+1
, a
j
) = 1, j < i}. ¤
Для некоторых классов графов последовательная раскраска является ми- нимальной. В общем случае это не так.
§ 4.15.
Планарные графы
Неорграф G называется планарным, если его можно изобразить на плос- кости так, что никакие два ребра не будут иметь общих точек, кроме, может быть, общего конца этих ребер. Такое изображение графа на плоскости на- зывается плоским. Таким образом, если граф имеет плоское изображение,
то он является планарным.
Пример 4.15.1. Граф K
4
(рис. 4.48а) планарен, поскольку может быть изображен, как показано на рис. 4.48б. ¤
Граф, описанный в примере 4.14.2, п. 2, является планарным. Также пла- нарным является граф, вершины которого — отверстия печатной платы, а ребра — проводники печатной платы, соединяющие отверстия.
Рассмотрим операцию подразбиения ребра в графе G = hM; Ri. После подразбиения ребра [a, b] ⊆ R получается граф G
0
= hM
0
; R
0
i, где M
0
= M∪
∪{ab}, R
0
= (R\[a, b])∪[a, ab]∪[ab, b], т. е. ребро [a, b] заменяется на (a, b)-цепь длины два. Два графа называются гомеоморфными, если их можно получить из одного графа с помощью последовательности подразбиений ребер.
•
•
•
•
¡
¡
¡
¡
¡
¡
@
@
@
@
@
@
•
•
•
•
¢
¢
¢
¢
¢
¢
¡
¡
¡
A
A
A
A
A
A
@
@
@
а
б
Рис. 4.48

164
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
•
•
•
•
•
•
•
•
•
•
•
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
@
@
@
@
@
@
@
@
@
@
@
@
©©
©©
©©
©©
©©
©
©
HH
HH
HH
HH
HH
H
H
K
5
K
3,3
Рис. 4.49
Не всякий неорграф является планарным. Критерий планарности опи- сывает
Теорема 4.15.1 (теорема Понтрягина—Куратовского). Неорграф G пла-
нарен тогда и только тогда, когда G не содержит часть, гомеоморфную K
5
или K
3,3
(рис. 4.49). ¤
Эквивалентная форма критерия планарности описана в следующей тео- реме.
Теорема 4.15.2. Тогда и только тогда неорграф G планарен, когда G не
содержит частей, стягиваемых (т. е. получаемых последовательностью
отождествлений вершин, связанных ребрами) к графу K
5
или K
3,3
(рис.
4.49). ¤
Вместе с тем трехмерного евклидова пространства оказывается доста- точно для изображения любого конечного и счетного графа без пересечения дуг вне их концов.
Теорема 4.15.3. Любой граф, состоящий не более чем из 2
ω
вершин,
может быть изображен в пространстве R
3
без пересечения дуг вне их
концов.
Доказательство. Пусть G = hM; Ri — граф, для которого |M| 6 2
ω
Тогда имеем |R| 6 2
ω
. Расположим все точки графа G на некоторой пря- мой l и каждой дуге из R разнозначно сопоставим плоскость, содержащую прямую l. Искомое изображение графа G получается после проведения всех дуг в соответствующих плоскостях. ¤
Известна оценка хроматического числа планарных графов.

ЗАДАЧИ И УПРАЖНЕНИЯ
165
Теорема 4.15.4 (теорема о четырех красках). Если G — планарный граф,
то χ(G) 6 4. ¤
При исследовании принципиальной электрической схемы радиоэлектрон- ного устройства с точки зрения возможности ее реализации с помощью пе- чатного монтажа или монтажа на слоях микросхемы важно знать ответ на следующие вопросы:
1) является ли граф, соответствующий рассматриваемой принципиаль- ной схеме, планарным?
2) если граф планарен, то как получить его изображение без пересечения ребер?
На первый вопрос принципиальный ответ дает теорема Понтрягина—
Куратовского, а методы получения плоских изображений планарных графов можно найти в книге Б. Н. Деньдобренько, А. С. Малика [8].
Если граф G непланарен, то для его геометрической реализации удаля- ют отдельные ребра (переносят на другую плоскость). Минимальное число ребер, которое необходимо удалить из графа для получения его плоского изображения, называется числом планарности графа G. При вынесении этих ребер на вторую плоскость получают часть графа, которая также может оказаться неплоской. Тогда вновь решают задачу вынесения отдельных ре- бер на следующую плоскость и т. д. Минимальное число плоскостей m, при котором граф G разбивается на плоские части G
1
, G
2
, . . ., G
m
(разбиение ведется по множеству ребер), называется толщиной графа G.
Таким образом, толщина планарного графа равна 1.
Пример 4.15.2. Каждый из графов K
5
и K
3,3
имеет толщину 2. ¤
Задачи и упражнения
1. Представить граф (рис. 4.50) в аналитической и матричной формах, списком дуг и структурой смежности.
2. Составить матрицу инцидентности для мультиграфа, изображенного на рис. 4.51.
3. Найти все неизоморфные подграфы и части графа K
3 4. Представить в геометрической и матричной формах графы G
1
∪ G
2
,
G
1
∩ G
2
, G
1
⊕ G
2
(рис. 4.52).
5. Для графов G
1
и G
2
из предыдущей задачи найти G
1
× G
2
, G
1
[G
2
] и G
2
[G
1
].

166
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
•
•
•
•
•
¡
¡
¡
¡
¡
¡
@
@
@
@
@
@
R ?
¾
-
±°
²¯
•
•
•
•
¡
¡
¡
¡
¡
¡
µ
¸
?
Y
K
*
¼
g
±°
²¯
Рис. 4.50
Рис. 4.51
6. С помощью матрицы смежности графа (рис. 4.53) найти его матрицы дости- жимости, контрдостижимости и сильных компонент.
7. Найти матрицу расстояний, диаметр, радиус, центральные и периферийные вершины графа, изображенного на рис. 4.54.
8. Найти все кратчайшие маршруты из вершины 2 для взвешенного графа
(рис. 4.55).
9. Доказать, что в любом конечном бесконтурном графе существуют вершины с нулевой полустепенью исхода и с нулевой полустепенью захода.
10. Проверить на эйлеровость и найти минимальное множество покрывающих цепей:
а) графа K
5
; б) графа K
3,3
; в) графа, изображенного на рис. 4.56.
•
•
•
¢
¢
¢
¢¢¸
A
A
A
AAU
1 2
3
G
1
•
•
•
•
¾
A
A
A
AAU
¢
¢
¢
¢
¢®
1 2
3 4
G
2
•
•
•
•
@
@
@
I
¡
¡
¡
µ
?
@
@
@
R
h
1 2
3 4
Рис. 4.52
Рис. 4.53
•
•
•
•
•
•
•
¡
¡
¡
¡
@
@
@
@
@
@
•
•
•
•
•
½
½
½
½
>
Z
Z
Z
Z

?
-
@
@
@
@
@
@
R
¡
¡
¡
¡
¡
¡
µ
¾
6
K
®
1 2
3 5
4
(3)
(4)
(6)
(2)
(1)
(2)
(2)
(3)
(−2)
(−5)
Рис. 4.54
Рис. 4.55

ЗАДАЧИ И УПРАЖНЕНИЯ
167
•
•
•
•
•
•
•
¶
¶
¶
¶
¶
¶
³³
³³
³³
³³
´
´
´
´
PPP
PPP
PP
Q
Q
Q
Q
E
E
E
E
E
E
E
E
¢
¢
¢
¢
¢
¢¡
¡
¡
•
•
•
•
•
•
•
¶
¶
¶
¶
¶
¶
@
@
@
´
´
´
´
@
@
@
@
@
@
E
E
E
E
E
E
E
E
S
S
S
S
S
S
¡
¡
¡
¡
¡
¡
¢
¢
¢
¢
¢
¢
(2)
(2)
(3)
(3)
(1)
(2)
(2)
(4)
(3)
(1)
Рис. 4.56
Рис. 4.57
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
@
@
R
¡
¡
ª
¡
¡
ª ?
?
¡
¡
ª
@
@
R
@
@
R
@
@
R
@
@
R
¡
¡
ª
¡
¡
ª
¡
¡
ª
¡
¡
ª
@
@
R
¡
¡
ª
1 2
3 4
5 6
7 8
9 10 11 12 13 14 15 16
•
•
•
•
•
•
•
J
J
JJ
1 2
3 4
5 9
7 8
6 10
Рис. 4.58
Рис. 4.59
11. Построить все неизоморфные трех-, четырех- и пятивершинные деревья.
12. Найти остов минимального веса взвешенного графа (рис. 4.57).
13. Найти упорядоченный лес, соответствующий бинарному дереву, изображен- ному на рис. 4.58.
14. Найти матрицы фундаментальных циклов и фундаментальных разрезов гра- фа (рис. 4.59).
15. Найти хроматическое число графа (рис. 4.60).
16. Найти толщину графа (рис. 4.61).
•
•
•
•
•
•
•
¡
¡
¡
@
@
@
@
@
@
@
@
@
S
S
S
S
S
S
¦
¦
¦
¦
¦
¦
¦
¦
•
•
•
•
•
•
¡
¡
¡
¡
@
@
@
@
HH
HH
HH
H
HH
HH
HH
H
©©
©©
©©
©
©©
©©
©©
©
Рис. 4.60
Рис. 4.61

Глава 5
КОМБИНАТОРИКА
Комбинаторика — раздел математики, посвященный решению задач вы- бора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множе- ства, называемой комбинаторной конфигурацией. Поэтому целями комби- наторного анализа являются изучение комбинаторных конфигураций, алго- ритмов их построения, оптимизация таких алгоритмов, а также решение за- дач перечисления. Простейшими примерами комбинаторных конфигураций являются перестановки, размещения, сочетания и разбиения. При подсчете комбинаторных конфигураций используются правила суммы, произведения и степени, сформулированные в § 1.4.
§ 5.1.
Перестановки и подстановки
Пусть дано множество M = {a
1
, a
2
, . . . , a
n
}. Перестановкой элементов множества M называется любой кортеж (a
i
1
, a
i
2
, . . . , a
i
n
), состоящий из n
различных элементов множества M.
Перестановки отличаются друг от друга только порядком входящих в них элементов. Покажем, что число P
n
всех перестановок множества M
равно n!. Действительно, на первое место в кортеже можно подставить лю- бой из n элементов, на второе место — любой из n − 1 оставшихся и т. д. Для последнего места остается единственный элемент. Поэтому получаем всего
n(n − 1)(n − 2) . . . 2 · 1 = n! перестановок.

5.1. ПЕРЕСТАНОВКИ И ПОДСТАНОВКИ
169
Пример 5.1.1. 1. Расставить на полке 10 книг можно P
10
= 10! =
= 3 628 800 различными способами.
2. Список студентов группы, состоящей из 25 человек, можно составить
P
25
= 25! способами. ¤
Напомним, что биекция σ: M ↔ M называется подстановкой множе- ства M. Пусть σ — подстановка множества M = {1, 2, . . . , n}. Тогда
σ(k) = s
k
, где 1 6 s
k
6 n, k = 1, 2, . . . , n, {s
1
, s
2
, . . . , s
n
} = {1, 2, . . . , n},
и поэтому подстановку σ можно представить в виде матрицы, состоящей из двух строк:
[σ] ­
µ
1 2 . . . n
s
1
s
2
. . . s
n
¶
.
Ясно, что если в матрице [σ] переставить столбцы, то полученная матрица будет также определять подстановку σ. Множество всех подстановок мно- жества {1, 2, . . . , n} обозначается через S
n
. Для подстановок σ, τ ∈ S
n
можно определить произведение σ · τ как произведение двух функций. Зная матри- цы подстановок
[σ] =
µ
1 2 . . . n
s
1
s
2
. . . s
n
¶
и [τ ], переставив столбцы матрицы [τ ] так, чтобы ее первая строка совпала со второй строкой матрицы [σ]:
µ
s
1
s
2
. . . s
n
t
1
t
2
. . . t
n
¶
,
получаем
[στ ] =
µ
1 2 . . . n
s
1
s
2
. . . s
n
¶ µ
s
1
s
2
. . . s
n
t
1
t
2
. . . t
n
¶
=
µ
1 2 . . . n
t
1
t
2
. . . t
n
¶
.
Пример 5.1.2. Если [σ] =
µ
1 2 3 4 2 1 4 3
¶
, [τ ] =
µ
1 2 3 4 3 1 4 2
¶
, то
[στ ] =
µ
1 2 3 4 2 1 4 3
¶ µ
2 1 4 3 1 3 2 4
¶
=
µ
1 2 3 4 1 3 2 4
¶
. ¤
Теорема 5.1.1. Алгебра hS
n
; ·i является группой. При n > 3 она неком-
мутативна.

170
Глава 5. КОМБИНАТОРИКА
Доказательство. Операция · ассоциативна как операция произведе- ния функций. Легко проверяется, что существует единичная подстановка ε
с матрицей [ε] =
µ
1 2 . . . n
1 2 . . . n
¶
и для любой подстановки σ с матрицей
[σ] =
µ
1 2 . . . n
s
1
s
2
. . . s
n
¶
существует обратная подстановка σ
−1
, соответству- ющая матрице
µ
s
1
s
2
. . . s
n
1 2 . . . n
¶
Если n > 3, то рассмотрим подстановки σ и τ
с матрицами
[σ] =
µ
1 2 3 4 . . . n
2 1 3 4 . . . n
¶
и [τ ] =
µ
1 2 3 4 . . . n
3 2 1 4 . . . n
¶
Имеем [στ ] =
µ
1 2 3 4 . . . n
2 3 1 4 . . . n
¶
, [τ σ] =
µ
1 2 3 4 . . . n
3 1 2 4 . . . n
¶
, т. е.
στ 6= τ σ. Таким образом, группа hS
n
; ·i некоммутативна. ¤
Группа hS
n
; ·i называется симметрической группой степени n. Число элементов этой группы |S
n
| равно P
n
­ n!.
Подстановка σ называется циклом длины r, если матрицу [σ] переста- новкой столбцов можно привести к виду
µ
s
1
s
2
s
3
. . . s
r−1
s
r
s
r+1
. . . s
n
s
2
s
3
s
4
. . .
s
r
s
1
s
r+1
. . . s
n
¶
.
Очевидно, что в этом случае σ задает биекцию, в которой s
1
7→ s
2
,
s
2
7→ s
3
, . . ., s
r
7→ s
1
, а остальные элементы неподвижны. Описанный цикл σ
обозначается через (s
1
s
2
. . . s
r
).
Пример 5.1.3. Подстановка с матрицей
µ
1 2 3 4 5 6 1 5 6 4 3 2
¶
является циклом (2 5 3 6), а подстановка с матрицей
µ
1 2 3 4 5 6 4 5 2 1 6 3
¶
циклом не яв- ляется, так как из нее можно выделить два цикла (1 4) и (2 5 6 3). ¤
Циклы (s
1
s
2
. . . s
r
) и (t
1
t
2
. . . t
p
) называются независимыми, если
{s
1
, s
2
, . . . , s
r
} ∩ {t
1
, t
2
, . . . , t
p
} = ∅.
Теорема 5.1.2. Каждую подстановку можно однозначно, с точностью
до порядка сомножителей, представить в виде произведения независимых
циклов. ¤

5.2. РАЗМЕЩЕНИЯ И СОЧЕТАНИЯ
171
В примере 5.1.3 имеем
µ
1 2 3 4 5 6 1 5 6 4 3 2
¶
= (2 5 3 6) и
µ
1 2 3 4 5 6 4 5 2 1 6 3
¶
= (1 4)(2 5 6 3).
Двухэлементный цикл (i j) называется транспозицией. При транспози- ции i-й и j-й элементы меняются местами, а остальные сохраняют свое по- ложение.
Теорема 5.1.3. Каждая подстановка есть произведение транспозиций.
Доказательство. По теореме 5.1.2 достаточно установить, что любой цикл (s
1
s
2
. . . s
r
) можно представить в виде произведения транспозиций,
но легко проверяется, что (s
1
s
2
. . . s
r
) = (s
1
s
2
)(s
1
s
3
) . . . (s
1
s
r
). ¤
Пример 5.1.4. (1 2 3 4) = (1 2)(1 3)(1 4). ¤
§ 5.2.
Размещения и сочетания
Пусть