1) является ли граф, соответствующий рассматриваемой принципиаль- ной схеме, планарным?
2) если граф планарен, то как получить его изображение без пересечения ребер?
На первый вопрос принципиальный ответ дает теорема Понтрягина—
Куратовского, а методы получения плоских изображений планарных графов можно найти в книге Б. Н. Деньдобренько, А. С. Малика [7].
Если граф 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
].
ЗАДАЧИ И УПРАЖНЕНИЯ 163 •••••¡ ¡ ¡ ¡ ¡ ¡ @ @ @ @ @ @ R ? ¾ - ±° ²¯ ••••¡ ¡ ¡ ¡ ¡ ¡ µ ¸ ? Y K * ¼ g ±° ²¯ Рис. 4.50Рис. 4.516. С помощью матрицы смежности графа (рис. 4.53) найти его матрицы дости- жимости, контрдостижимости и сильных компонент. 7. Найти матрицу расстояний, диаметр, радиус, центральные и периферийные вершины графа, изображенного на рис. 4.54. 8. Найти все кратчайшие маршруты из вершины 2 для взвешенного графа (рис. 4.55). 9. Доказать, что в любом конечном бесконтурном графе существуют вершины с нулевой полустепенью исхода и с нулевой полустепенью захода. 10. Проверить на эйлеровость и найти минимальное множество покрывающих цепей: а) графа K5 ; б) графа K3 ,3 ; в) графа, изображенного на рис. 4.56. •••¢ ¢ ¢ ¢¢¸ A A A AAU 1 2 3 G1 ••••¾ A A A AAU ¢ ¢ ¢ ¢ ¢® 1 2 3 4 G2 ••••@ @ @ 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
164
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
•
•
•
•
•
•
•
¶
¶
¶
¶
¶
¶
³³
³³
³³
³³
´
´
´
´
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! перестановок.
166
Глава 5. КОМБИНАТОРИКА
Пример 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 она неком-
мутативна.
5.1. ПЕРЕСТАНОВКИ И ПОДСТАНОВКИ 167 Доказательство. Операция · ассоциативна как операция произведе- ния функций. Легко проверяется, что существует единичная подстановка εс матрицей [ ε] = µ 1 2 . . . n1 2 . . . n¶ и для любой подстановки σ с матрицей [ σ] = µ 1 2 . . . ns1 s2 . . . sn¶ существует обратная подстановка σ−1 , соответству- ющая матрице µ s1 s2 . . . sn1 2 . . . n¶ Если n > 3, то рассмотрим подстановки σ и τс матрицами [ σ] = µ 1 2 3 4 . . . n2 1 3 4 . . . n¶ и [ τ ] = µ 1 2 3 4 . . . n3 2 1 4 . . . n¶ Имеем [ στ ] = µ 1 2 3 4 . . . n2 3 1 4 . . . n¶ , [ τ σ] = µ 1 2 3 4 . . . n3 1 2 4 . . . n¶ , т. е. στ 6= τ σ. Таким образом, группа hSn; ·i некоммутативна. ¤ Группа hSn; ·i называется симметрической группой степени n. Число элементов этой группы |Sn| равно Pn n!. Подстановка σ называется циклом длины r, если матрицу [ σ] переста- новкой столбцов можно привести к виду µ s1 s2 s3 . . . sr−1 srsr+1 . . . sns2 s3 s4 . . .srs1 sr+1 . . . sn¶ .Очевидно, что в этом случае σ задает биекцию, в которой s1 7→ s2 , s2 7→ s3 , . . ., sr7→ s1 , а остальные элементы неподвижны. Описанный цикл σобозначается через ( s1 s2 . . . sr). Пример 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). ¤ Циклы ( s1 s2 . . . sr) и ( t1 t2 . . . tp) называются независимыми, если {s1 , s2 , . . . , sr} ∩ {t1 , t2 , . . . , tp} = ∅. Теорема 5.1.2. Каждую подстановку можно однозначно, с точностьюдо порядка сомножителей, представить в виде произведения независимыхциклов. ¤ 168 Глава 5. КОМБИНАТОРИКАВ примере 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 достаточно установить, что любой цикл ( s1 s2 . . . sr) можно представить в виде произведения транспозиций, но легко проверяется, что ( s1 s2 . . . sr) = ( s1 s2 )( s1 s3 ) . . . ( s1 sr). ¤ Пример 5.1.4. (1 2 3 4) = (1 2)(1 3)(1 4). ¤ § 5.2. Размещения и сочетания Пусть M — множество, состоящее из n элементов, m 6 n. Размещениемиз n элементов по m или упорядоченной ( n, m)- выборкой, называется любой кортеж ( ai1 , ai2 , . . . , aim), состоящий из m попарно различных элементов мно- жества M. Размещение можно рассматривать как разнозначную функцию f : {1 , 2 , . . . , m} → M, для которой f ( j) = aijПример 5.2.1. Для множества M = {a, b, c} пары ( a, b) и ( b, a) являются размещениями из 3 по 2, тройка ( a, c, b) — размещением из 3 по 3, а тройка ( b, a, b) размещения не образует. ¤ Число размещений из n по m обозначается через Amnили P ( n, m). Пока- жем, что Amn= n! ( n − m)! = n( n − 1) . . . ( n − m + 1) (5.1) (напомним, что 0! = 1). Действительно, размещение m элементов мож- но представить как заполнение некоторых m позиций элементами множе- ства M. При этом первую позицию можно заполнить n различными спосо- бами. После того как 1-я позиция заполнена, элемент для заполнения 2-й позиции можно выбрать ( n − 1) способами. Если продолжить этот процесс,
5.2. РАЗМЕЩЕНИЯ И СОЧЕТАНИЯ
169
то после заполнения позиций с 1-й по (m − 1)-ю будем иметь (n − m + 1) спо- собов заполнения последней, m-й позиции. Перемножая эти числа, получаем формулу (5.1).
Пример 5.2.2. Из десяти различных книг произвольным образом бе- рутся и ставятся на полку одна за другой 3 книги. Имеется A
3 10
вариантов расстановок, где A
3 10
=
10!
7!
= 10 · 9 · 8 = 720. ¤
Cочетанием из n элементов по m или неупорядоченной (n, m)-выборкой
называется любое подмножество множества M, состоящее из m элементов.
Пример 5.2.3. Если M = {a, b, c}, то {a, b}, {a, c}, {b, c} — все сочетания из 3 по 2. ¤
Число сочетаний из n по m обозначается через C
m
n
,
¡
n
m
¢
или C(n, m).
Если объединить размещения из n элементов по m, состоящие из од- них и тех же элементов (не учитывая порядка их расположения), в клас- сы эквивалентности, то можно установить биекцию ϕ между сочетаниями и полученными классами по следующему правилу: ϕ({a
i
1
, a
i
2
, . . . , a
i
m
})
{(b
1
, b
2
, . . . , b
m
) | {b
1
, b
2
, . . . , b
m
} = {a
i
1
, a
i
2
, . . . , a
i
m
}}. Так как из каждого сочетания C можно получить m! размещений (упорядочивая m! способами элементы из множества C по числу перестановок этого множества), то каж- дый класс эквивалентности содержит m! размещений и, значит, A
m
n
= m!·C
m
n
,
т. е. C
m
n
=
A
m
n
m!
. Таким образом,
C
m
n
=
n!
(n − m)! m!
.
Пример 5.2.4. Из десяти чисел четыре можно выбрать C
4 10
=
10!
6!4!
=
=
7·8·9·10 4!
=
7·8·9·10 1·2·3·4
= 210 способами. ¤
Число C
m
n
обладает следующими свойствами:
1) C
m
n
= C
n−m
n
;
2) C
m
n
+ C
m+1
n
= C
m+1
n+1
(правило Паскаля);
3) (a + b)
n
=
n
P
m=0
C
m
n
a
m
b
n−m
для любых a, b ∈ R, n ∈ ω (бином Ньютона).
В силу последнего свойства числа C
m
n
называются биномиальными коэф-
фициентами.
Пример 5.2.5. Из свойства 3 следует, что 2
n
=
n
P
m=0
C
m
n
. Действительно,
2
n
= (1 + 1)
n
=
n
P
m=0
C
m
n
1
m
1
n−m
=
n
P
m=0
C
m
n
. ¤
170
Глава 5. КОМБИНАТОРИКА
§ 5.3.
Размещения и сочетания с повторением
Размещением с повторением из n элементов по m или упорядоченной
(n, m)-выборкой с возвращениями называется любой кортеж (a
1
, a
2
, . . . , a
m
)
элементов множества M, для которого |M| = n.
Поскольку в кортеж (a
1
, a
2
, . . . , a
m
) на каждое место может претендовать любой из n элементов множества M, число размещений с повторениями
ˆ
P (n, m) равно n · n · . . . · n
|
{z
}
m раз
= n
m
:
ˆ
P (n, m) = n
m
.
Пример 5.3.1. Из цифр 1, 2, 3, 4 можно составить ˆ
P (4, 3) = 4 3
= 64
трехзначных числа. ¤
Определим отношение эквивалентности на множестве размещений с по- вторениями из n по m:
(a
1
, a
2
, . . . , a
m
) ∼ (b
1
, b
2
, . . . , b
m
) ⇔ для любого c ∈ M число элементов a
i
,
равных c, совпадает с числом элементов b
i
, равных c.
Сочетанием с повторением из n элементов по m или неупорядоченной
(n, m)-выборкой с возвращениями называется любой класс эквивалентности по отношению ∼ множества размещений с повторениями из n элементов по
m. Другими словами, сочетания с повторениями суть множества, которые состоят из элементов, выбранных m раз из множества M, причем один и тот же элемент допускается выбирать повторно.
Число сочетаний с повторениями из n элементов по m обозначается через ˆ
C(n, m) и вычисляется по формуле
ˆ
C(n, m) = C
m
n+m−1
=
(n + m − 1)!
m!(n − 1)!
.
Пример 5.3.2. Число различных бросаний двух одинаковых кубиков равно ˆ
C(6, 2) = C
2 7
= 21. ¤
§ 5.4.
Разбиения
Пусть M — множество мощности n, {M
1
, M
2
, . . . , M
k
} — разбиение мно- жества M на k подмножеств, |M
i
| = m
i
, m
1
+ m
2
+ . . . + m
k
= n. Кортеж
(M
1
, . . . , M
k
) называется упорядоченным разбиением множества M.
5.4. РАЗБИЕНИЯ
171
Если k = 2, то упорядоченное разбиение множества M на два подмноже- ства, имеющие соответственно m
1
и m
2
элементов, определяется сочетанием
(без повторений) из n элементов по m
1
или из n по m
2
(m
2
= n − m
1
). Следо- вательно, число разбиений R(m
1
, m
2
) равно биномиальному коэффициенту
C
m
1
n
= C
m
2
n
. Таким образом,
R(m
1
, m
2
) =
n!
m
1
!(n − m
1
)!
=
n!
m
1
! m
2
!
.
В общем случае число R(m
1
, m
2
, . . . , m
k
) упорядоченных разбиений
(M
1
, M
2
, . . . , M
k
), для которых |M
i
| = m
i
, равно
n!
m
1
! m
2
! . . . m
k
!
, а число
R
0
(n, k) упорядоченных разбиений на k подмножеств вычисляется по фор- муле
R
0
(n, k) =
X
m
1
+ ... +m
k
=n,
m
i
>0
R(m
1
, m
2
, . . . , m
k
).
Числа R(m
1
, m
2
, . . . , m
k
) называются полиномиальными коэффициентами,
поскольку для всех a
1
, a
2
, . . . , a
k
∈ R справедливо соотношение
(a
1
+ a
2
+ . . . + a
k
)
n
=
X
m
1
+ ... +m
k
=n,
m
i
>0
n!
m
1
! . . . m
k
!
· a
m
1 1
a
m
2 2
. . . a
m
k
k
.
Пример 5.4.1. В студенческой группе, состоящей из 25 человек, при вы- боре старосты за выдвинутую кандидатуру проголосовали 12 человек, про- тив — 10, воздержались — 3. Сколькими способами могло быть проведено такое голосование?
Пусть M — множество студентов в группе, M
1
— множество студентов,
проголосовавших за выдвинутую кандидатуру, M
2
— множество студентов,
проголосовавших против, M
3
— множество студентов, воздержавшихся от голосования. Тогда |M| = 25, |M
1
| = 12, |M
2
| = 10, |M
3
| = 3, (M
1
, M
2
, M
3
) —
упорядоченное разбиение множества M. Искомое число R(12, 10, 3) равно
25!
12!10!3!
= 1487285800. ¤
Число ˆ
R(l
1
, l
2
, . . . , l
r
; m
1
, m
2
, . . . , m
r
) разбиений исходного множества M
на k подмножеств, неупорядоченных между собой, среди которых l
i
множеств
172 Глава 5. КОМБИНАТОРИКАимеет мощность mi, i = 1 , . . . , r, l1 + . . . + lr= k, m1 l1 + . . . + mrlr= n, вычисляется по формуле ˆ R( l1 , . . . , lr; m1 , . . . , mr) = n! l1 ! . . . lr!( m1 !) l1 . . . ( mr!) lr,а число всех возможных разбиений множества M на k подмножеств, неупо- рядоченных между собой, равно X l1 + ...+ lr= k,m1 l1 + ... + mrlr= n,mi>0 при li>0 ˆ R( l1 , . . . , lr; m1 , . . . , mr) . |
Скачать 1.99 Mb.