- •СОДЕРЖАНИЕ
- •§ 1. Множества и операции над ними
- •2. Способы задания множеств
- •3. Операции над множествами
- •4. Свойства операций над множествами. Алгебра множеств
- •5. Декартово произведение множеств
- •§ 2. Отображения множеств
- •2. Произведение (композиция) отображений
- •3. Обратные отображения
- •§ 3. Отношения
- •2. Операции над бинарными отношениями и их свойства
- •§ 4. Отношения экивалентности
- •2. Отношения частичного порядка
- •§ 5. Комбинаторика
- •1. Размещения
- •2. Перестановки
- •3. Сочетания
- •4. Сочетания с повторениями
- •5. Бином Ньютона. Понятие о производящей функции
- •6. Числа Стирлинга
- •7. Число Белла
- •§ 6. Мощности множеств
- •2. Мощности бесконечных множеств. Счетные множества
- •4. Кардинальные числа. Гипотеза континуума
- •§ 7. Основные определения и типы графов
- •2. Основные типы графов
- •3. Обобщения понятия графа
- •4. Изоморфные графы
- •5. Количество различных графов порядка n
- •§ 8. Основные числовые характеристики и матрицы графа
- •2. Матрица смежности
- •3. Матрица Кирхгофа
- •4. Матрица инцидентности
- •§ 9. Подграфы и операции на графах
- •1. Подграфы
- •2. Операции над графами
- •§ 10. Связные графы и расстояние в графах
- •2. Компоненты связности. Связность графа и его дополнения
- •3. Расстояния на графах
- •§ 11. Деревья и остовы
- •1. Критерии дерева
- •2. Корневое дерево
- •3. Типы вершин дерева, радиус и центры
- •4. Остовы графа, циклический ранг и ранг разрезов
- •5. Задача о минимальном остове
- •7. Линейное пространство графа
- •§ 12. Эйлеровы и гамильтоновы графы
- •1. Эйлеровы графы
- •2. Гамильтоновы графы
- •§ 13. Планарные графы
- •2. Планарные графы. Формула Эйлера
- •3. Следствия из формулы Эйлера
- •4. Гомеоморфные графы. Критерий планарности
- •§ 14. Раскраски графов
- •2. Хроматическое число 2–дольного графа. Критерий 2-дольности
- •3. Некоторые оценки хроматического числа
- •4. Раскраски планарных графов
- •5. Реберная раскраска графа
- •§ 15. Паросочетания
- •1. Паросочетания
- •2. Теорема Холла о свадьбах
- •§ 16. Сети
- •1. Основные понятия
- •2. Потоки в сетях
- •3. Сетевое планирование
- •ТИПОВОЙ РАСЧЕТ «ГРАФЫ»
- •Задание
- •Варианты индивидуальных заданий
- •ЛИТЕРАТУРА
Замечание. Пусть X и Y – конечные множества, |
|
X |
|
= n , |
|
Y |
|
= m , n ≥ m . Тогда |
|
|
|
|
|||||
существуют сюръективные отображения X → Y . Их |
|
количество равно Snm m!. |
Действительно, чтобы получить сюръективное отображение X →Y необходимо для каждого из m элементов множества Y указать множество прообразов. Такие множества
прообразов представляют собой разбиение множества X (число разбиений равно Snm ).
Для каждого разбиения, устанавливая взаимно однозначные соответствие между блоками разбиения множества X и соответствующими им образами, можно построить
m! различных сюръективных отображений. Числа S(n,m) = Snm m! называются
числами Стирлинга первого рода.
7. Число Белла
Число всех разбиений n-элементного множества называется числом Белла и обозначается Bn . По определению
n
B0 =1 и Bn = ∑Snm при n > 0 .
m=0
n
Теорема. Bn+1 = ∑Cnk Bk .
k =0
Доказательство. Пусть X – множество всех разбиений множества {1, 2,..., n +1} . Рассмотрим все подмножества множества {1, 2,..., n +1} , содержащие n +1. Для каждого такого множества A рассмотрим все разбиения, которые содержат A в качестве
отдельного |
блока. |
Обозначим |
|
множество таких разбиений |
через X A .Тогда |
||||||
совокупность всех X A |
есть разбиение множества X. |
|
|
||||||||
Пусть |
|
A |
|
= a . |
Тогда |
|
X A |
|
= Bn+1−a . Кроме |
того, число |
таких множеств A |
|
|
|
|
(состоящих из a элементов, один из которых равенn +1) равно Cna−1 . Следовательно,
|
|
|
|
|
|
|
|
|
|
n+1 |
|
|
|
|
|
|
|
n+1 |
n |
n |
Bn+1 = |
|
X |
|
= |
UX A |
= ∑ |
|
X A |
|
=∑ ∑ |
|
X A |
|
= ∑Cna−1 Bn+1−a =∑Cnn−k Bk =∑Cnk Bk . |
||||||
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
A |
A |
|
|
|
a=1 |
|
A |
|
=a |
|
|
|
a=1 |
k =0 |
k =0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
§6. Мощности множеств
1.Мощность конечного множества
Как уже отмечалось, если А – конечное множество, то его мощность A есть
количество элементов, принадлежащих А. Легко видеть, что
1). Если A ∩ B = , то A B = A + B .
2). В общей ситуации: A B =| A | + | B | − A ∩ B . 3). | A \ B |=| A | − | A ∩ B |.
Теорема1. Если A1 ,…, An – конечные множества, то
| Α1 ×Α2 × .....×Αn |= A1 A2 ...... An .
Доказательство непосредственно следует из подсчета числа различных n-ок.
25
Следствие. Если А – конечное множество, то An = A n
Теорема 2. Два конечных множества равномощны тогда и только тогда, когда
между ними существует биекция.
Доказательство очевидно.
Следствие. Никакое собственное подмножество или надмножество конечного
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
множества A не равномощно множеству А. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
Теорема 3. Пусть A – конечное множество, Ω (A) |
− множество всех |
||||||||||||||||
|
|
|
|
|
|
Α |
|
|
|
|
|
|
|
|
|
|||
подмножеств (булеан) множества А. Тогда | Ω (A) |
|
= 2 |
|
|
. |
|
|
A |
|
= n . |
|
|||||||
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
||||||||||||
|
Доказательство. |
Рассмотрим Β = {0, 1 } |
|
и |
пусть |
|
|
Тогда Bn – |
||||||||||
|
|
|
|
|||||||||||||||
множество бинарных n-ок. Существует биекция между Ω(A) |
|
и |
An . |
Действительно, |
||||||||||||||
пусть |
A = {a1 , a2 , ..., an } и Μ Ω(A), т. е. |
|
Μ A. |
Поставим |
в соответствие |
|||||||||||||
множеству М такую n-ку |
( , , ..., ), в которой i-ый элемент равен 1, если ai Μ , и |
|||||||||||||||||
равен |
0, если ai Μ . |
Обратно, всякой бинарной |
n-ке |
однозначно соответствует |
некоторое множество М, элементы которого определяются по n-ке описанным выше способом. Поскольку биективные множества имеют равное количество элементов
(теорема 2) и Bn =2n (следствие к теореме 1), то Ω (A) = 2n, что и требовалось доказать.
2. Мощности бесконечных множеств. Счетные множества
Определение. Говорят, что множества А и В имеют одинаковую мощность (или, что они равномощны), если между А и В можно установить биекцию. Множества, равномощные множеству натуральных чисел, называются счетными.
Установить биекцию с множеством натуральных чисел N фактически означает: сопоставить каждому элементу рассматриваемого множества номер, т.е. пронумеровать все элементы, или другими словами – пересчитать.
Конечное или счетное множество называется не более чем счетным.
Примеры и свойства счетных множеств.
•Множество четных чисел 2N – счетное. Действительно, биекцию 2N → N задает, например, отображение 2n a n .
•Множество целых чисел Z счетно. Соответствующей биекцией, очевидно, является следующее отображение
... |
−3 |
− 2 |
−1 |
0 |
1 |
2 |
3 |
... |
|
7 |
5 |
3 |
1 |
2 |
4 |
6 |
. |
... |
... |
•Объединение не более чем счетного множества счетных множеств – счетно. Доказательство. Можно считать, что все множества и элементы в них уже
}, Α2 = {a21 , a22 , a23 , a24 , ...},
}…. Расположим все элементы, 43 43 4441 4231 32 33 34
объединения A1 A2 A3 A4 ... следующим образом и пронумеруем в порядке, указанном стрелкой (рис. 6.1).
26
a11 |
→ a12 |
|
a13 |
→ a14 |
... |
|
↓ |
|
↑ |
↓ |
|
a21 |
← a22 |
|
a23 |
a24 |
... |
↓ |
|
|
↑ |
↓ |
|
a31 |
→ a32 |
→ |
a33 |
a34 |
... |
|
|
|
|
↓ |
|
a41 |
← a42 |
← |
a43 |
← a44 |
... |
↓ |
|
|
|
|
|
... |
... |
|
... |
... |
... |
|
|
Рис. 6.1 |
|
|
Понятно, что при указанном способе рассмотрения элементов всякий элемент рано или поздно получит свой номер. Если Αi имеют непустые пересечения и в процессе
нумерации встречаются элементы уже ранее пронумерованные, то их будем пропускать
и переходить к следующим элементам. |
|
|
|
• Прямое произведение конечного числа счетных множеств – счетно. |
|||
Доказательство. Пусть |
Α = {a1 , |
a2 , ...}, |
Β = {в1 , в2 , ...}. Элементы декартового |
произведения Α× Β = {(a1 , в1 ), |
(a1 , в2 ), |
(a1 , в3 ), |
..., (a2 , в1 ), (a2 , в2 ), (a2 , в3 ), ..., ....} |
расположим так же, как и в предыдущем примере (в виде бесконечной вправо и вниз прямоугольной таблицы) и пронумеруем аналогично. Таким образом, произведение двух счетных множеств – счетно. Дальше по индукции для любого числа множителей.
•Множество Q – рациональных чисел счетно.
Доказательство. |
Представим |
множество всех рациональных чисел в виде |
|||||||||||||||||
Q = Q+ Q= {0}, |
где Q+ и Q- – |
подмножества положительных и отрицательных |
|||||||||||||||||
рациональных чисел, соответственно. Достаточно показать, что Q+ счетно. А это |
|||||||||||||||||||
действительно так, поскольку |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
Q+ ={ |
1 |
, |
|
2 |
, |
3 |
, ... } { |
1 |
, |
2 |
, |
3 |
, ... } { |
1 |
, |
2 |
, |
3 |
, ... } ... |
|
1 |
|
2 |
2 |
2 |
|
3 |
3 |
|||||||||||
1 |
|
1 |
|
|
|
3 |
|
|
|
есть объединение счетного количества счетных множеств.
•Множество алгебраических чисел A (корней всевозможных многочленов с целыми коэффициентами) – счетно (докажите).
3.Несчетные множества. Мощность континуума
Теорема(Кантор).
Множество всех действительных чисел из отрезка [0; 1] – несчетно.
Доказательство. Представим все числа в двоичной системе счисления в виде бесконечных двухзначных дробей (в случае конечных дробей дополним справа нулями до бесконечности). Предположим, что количество рассматриваемых чисел счетно. Расположим их в порядке возрастания номеров:
1) |
0, a11a12 a13 a14 ..... |
Здесь везде aij – 0 или 1. |
|
2) |
0, a21a22 a23 a24 ..... |
||
Рассмотрим число 0, a *11 a *22 a *33 a *44 ....., |
|||
3) |
0, a31a32 a33 a34 ..... |
||
где a *ii ≠ aii ( т.е. a *ii =1, если aii = 0 , и |
|||
4) |
0, a41a42 a43 a44 ..... |
||
5) |
. . . . . . . . . . . |
a *ii = 0 , если aii =1). |
27
Легко видеть, что этого числа нет среди пронумерованных, так как оно отличается от 1-го числа в 1-ом разряде, от второго – во 2-ом разряде, от третьего – в 3- ем разряде, … . Полученное противоречие показывает, что множество действительных чисел из отрезка [0; 1] не является счетным.
Определение. Мощность множества действительных чисел отрезка[0; 1]
называется мощностью континуума.
Примеры.
1)Множество всех действительных чисел R имеет мощность континуума. Доказательство. Прежде всего, отметим, что любые два отрезка равномощны.
Это следует, например, |
из того, что отображение f (x) = |
x − a |
|
биективно переводит |
||||
b − a |
|
|||||||
|
|
|
|
|
|
|||
отрезок [a; b] в отрезок |
|
− |
π |
; |
π |
|
→ R. , определяемую, |
|
[0; 1]. Далее получаем биекцию |
2 |
2 |
|
|||||
|
|
|
|
|
|
например, формулой g(x) = tg x .
2)Множество иррациональных чисел имеет мощность континуума, так как оно равно R \ Q, а Q – счетно.
3)Множество трансцендентных чисел имеет мощность континуума. Действительно, оно равно R\A, где A – счетное множество алгебраических чисел.
4)Множество комплексных чисел C.
5)Множество непересекающихся окружностей на плоскости.
4. Кардинальные числа. Гипотеза континуума
Теорема. Булеан счетного множества имеет мощность континуума. Доказательство. Пусть A = {a1 , a2 ,..., an ,...}. Построим биекцию Ω(A)→[0, 1].
Пусть |
M A . Отобразим M a 0, a1a2 a3 ..... , где |
0, a1a2 a3 .... – число из отрезка |
|||||
[0, 1], |
представленное |
в виде бесконечной |
дроби |
в двоичной системе счисления, |
|||
причем такое, что ai |
=1, |
если ai M , и |
ai = 0 , |
если ai M . |
Очевидно, |
такое |
|
отображение обратимо и, |
значит, биективно. Таким образом, Ω (A) |
и отрезок |
[0, 1] |
равномощны, что и требовалось доказать.
Для обозначения мощностей бесконечных множеств используются так называемые кардинальные числа. Мощность счетного множества обозначается0 (алеф− ноль). Мощность континуума – 1 (алеф− один).
Поскольку Ω(A) = 2 A для конечных множеств и булеан счетного множества
имеет мощность континуума, то и для бесконечных множеств имеем: 2 0 = 1 .
Можно показать, что вообще (теорема Кантора) булеан всякого множества A имеет мощность большую чем A (и всякое его подмножество). Таким образом,
2 1 = 2 , ... , 2 n = n+1 , …
Подобно тому, как не существует наибольшего натурального числа, не существует множества, имеющего наибольшую мощность.
Континуум – гипотеза утверждает, что всякое бесконечное подмножество R имеет мощность 0 или 1 , т.е. нет множеств, мощности которых выражаются
промежуточными «дробными» кардинальными числами. В более общей форме, не существует бесконечных множеств, имеющих другие мощности, кроме
i , i N {0} .
28