- •Лекция 1. Метод математической индукции.
- •Принцип индукции.
- •Неравенство Коши-Буняковского.
- •Лекция 2. Комбинаторика.
- •Принцип умножения.
- •Перестановки.
- •Размещения.
- •Рассмотрим первый набор чисел.
- •Сочетания.
- •Некоторые свойства биномиальных коэффициентов:
- •Перестановки с повторениями.
- •Сочетания с повторениями.
- •Бином Ньютона.
- •1). База индукции.
- •2). Индуктивное предположение.
- •3). Индуктивный переход.
- •Лекция 3. Введение в теорию множеств. Понятия о множестве.
- •Два основных интуитивных принципа наивной теории множеств.
- •Интуитивный принцип объемности.
- •Интуитивный принцип абстракции.
- •Парадокс Рассела.
- •Лекция 4. Операции над множествами. Сравнение множеств.
- •Свойства отношения включения.
- •Операции над множествами.
- •Лекция 5. Свойства операций над множествами.
- •Формула включения и исключения.
- •Лекция 6.
- •Упорядоченные пары.
- •Прямое произведение множеств.
- •Бинарные отношения.
- •Композиция отношений.
- •Теорема о свойствах бинарного отношения.
- •Матрицы конечных бинарных отношений.
- •Свойства матриц конечных бинарных отношений.
- •Матрицы объединения и пересечения двух бинарных отношений.
- •Матрица композиции двух конечных бинарных отношений.
- •Матрица обратного отношения.
- •Матрица рефлексивного бинарного отношения
- •Ядро бинарного отношения.
- •Свойства ядра:
- •Лекция 8. Отношения эквивалентности.
- •Классы эквивалентности.
- •Функции.
- •Инъекции и биекции.
- •Примеры экзаменационных задач.
- •Лекция 9. Композиция функций.
- •Ядро функции).
- •Отношения порядка.
- •Экстремальные элементы в упорядоченном множестве.
- •Лекция 10. Верхняя и нижняя грани частично упорядоченного множества.
- •Решетки.
- •Ограниченные решетки.
- •Решетки с дополнением.
- •Частичный порядок в решетке.
- •Лекция 11. Матроиды.
- •Максимально независимые подмножества.
- •Алгоритм построения базы матроида.
- •Ранг множества.
- •Жадный алгоритм.
Частичный порядок в решетке.
В любой решетке можно ввести нестрогий частичный порядок, если положить, что
-
Рефлексивность:
-
Антисимметричность:
Пусть и и ;
-
Транзитивность:
Пусть и и
.
Часто решетку определяют, начиная с нестрогого частичного порядка.
Пусть М – частично упорядоченное множество с нестрогим порядком . Если во множестве М для любых двух его элементов a, b существуют их точные верхняя и нижняя грани (sup(a,b)) и (inf(a,b)), то элементы множества М образуют решетку, если положить: ab = inf (a,b) и ab = sup (a,b).
Докажем выполнение аксиом 1 – 4:
-
– идемпотентность;
-
и и – коммутативность ;
–ассоциативность;
-
– законы поглощения.
Лекция 11. Матроиды.
Пусть Е – конечное множество |Е| = n, семейство подмножеств множества Е, и каждый элемент x из множества E принадлежит хотя бы одному множеству из . Пара (Е, ) образует матроид, если выполняются три аксиомы матроида:
М.1:
М.2: Если В и А В, то А
М.3: Если |В| = |А| + 1 и А, В , то (e В\А): А{e}
Множества, входящие в семейство называются независимыми, остальные (2n \) множеств, называются зависимыми. Аксиому М.3 можно заменить на эквивалентную ей аксиому М.3: Если А, В и |В| > |А|, то (e В\А): А{e}.
Примеры.
-
Е – конечное множество векторов конечномерного линейного пространства, семейство образуют всевозможные наборы линейно независимых векторов, взятых из Е.
Доказательство.
М.1: ; (пустое множество векторов линейно независимо)
М.2: Любое подмножество линейно независимых векторов линейно независимо;
М.3: Пусть А = , . Из теории конечномерных векторных пространств известно, что существует вектор , который не выражается линейно через векторы множества А - множество линейно независимых векторов. Значит, (Е, ) – матроид.
-
Свободные матроиды. Пара (Е, 2Е) образует матроид, который называется свободным.
-
Матроиды разбиений. Пусть {Ei} – разбиение множества Е, Ei= Е, Ei Еj =, если i ≠ j, Е ≠ . Определим семейство так:
= {A|}.
Другими словами, в любое независимое множество входит не более одного элемента из каждого множества разбиения.
Пример.
E = {1, 2, 3, 4}, E1 = {1}, E2 = {2, 4}, E3 = {3}.
A1 =, A2 = {1}, A3 = {2}, A4 = {3}, A5 = {4}, A6 = {1, 2}, A7 = {1, 3},
A8 = {1, 4}, A9 = {2, 3}, A10 = {4, 3}, A11 = {1, 2, 3}, A12 = {1, 3, 4}.
Докажем, что выполняются аксиомы матроида.
М.1: , так как .
М.2: Если В и А В, А , так как условие очевидным образом выполняется.
М.3: Пусть А, В, |A| = k, |B| = k +1 (Ei):|B Ei | = 1, |AEi | = 0 .
Максимально независимые подмножества.
Пусть X E и Y X. Множество Y называется максимально независимым подмножеством множества X, если Y независимо (Y) и (eX\Y): Y{e}. Это подмножество называется еще базой или базисом множества X. Базы Е называются базами матроида. Множество всех баз данного множества X обозначается .
Рассмотрим матроид разбиения из предыдущего примера.
E = {1, 2, 3, 4}, X = {1, 2, 4}, {1, 2} и {1, 4}.
Е, {1, 2, 3}, {1, 3, 4}.
М.4: Все базы данного множества X равномощны.
Доказательство.
Пусть Y и Z, но |Y||Z|, например |Y|>|Z|. Так как Y и Z Z{e}. Но Z{e}X, и Z – не максимально независимое подмножество множества X. Мы получили противоречие, базы должны быть равномощны. Таким образом, М.4 следует из М.2 и М.3.
Докажем, что М.3 следует из М.2 и М.4, т.е. условия М.3 и М.4 взаимозаменяемы.
Доказательство.
Предположим, что М.2 и М.4 выполняются. Докажем, что выполняется М.3 (от противного). Пусть A, B, |B| = k + 1, |A| = k, но М.3 не выполняется. Тогда (eВ\А): А{e}. Положим С = В А
-
А С, А – база С,
-
B C, B, следовательно, В или база множества С, или B можно
увеличить до базы, добавив в него элементы из А. Нарушено условие М.4, базы должны иметь равные мощности.