- •Богданов а.Е. Курс лекций
- •Содержание
- •§ 1. Основные понятия теории множеств
- •Основные понятия теории множеств
- •Способы задания множеств
- •Операции над множествами
- •§ 2. Соответствия. Функции. Отображения
- •§ 3. Понятие алгебры. Алгебра множеств кантора
- •Диаграмма Эйлера-Венна
- •§ 4. Бинарные отношения
- •Способы задания бинарных отношений
- •Свойства бинарных отношений
- •§ 5. Бинарное отношение эквивалентности
- •§ 6. Бинарное отношение порядка. Упорядоченные
- •§ 7. Решетки (структуры). Изоморфизм
- •Изоморфизм множеств
- •Дедекиндовые решетки
- •Дистрибутивные решетки
- •§ 8. Отношения (обобщение). Алгебраические
- •Операции над отношениями
- •Алгебраические системы
- •Глава ιι. Комбинаторный анализ
- •§ 1. Основные определения
- •Правила суммы и произведения
- •§ 2. Формулы расчета перестановок и сочетаний
- •§ 3. Бином и полином
- •§ 4. Подстановки
- •§ 5. Метод включений и исключений
- •§ 6. Метод производящих функций
- •§ 7. Комбинаторная мера информации. Вероятность искажения информации
- •Глава ιіі. Теория графов
- •§ 1. Первоначальные понятия теории графов
- •§ 2. Операции над графами. Способы задания графов Операции над графами
- •Способы задания графов
- •§ 3. Маршруты, цепи, циклы и другие характеристики графа
- •§ 4. Алгебраическая форма представления графа
- •Глава іv. Некоторые приложения графов
- •§ 1. Эйлеровы графы. Алгоритм флери. Гамильтоновы
- •Эйлеровы графы
- •Алгоритм Флери.
- •Метод построения эйлерового обхода двоичного куба
- •Гамильтоновы графы. Метод Робертса – Флореса
- •Метод перебора Робертса – Флореса
- •§ 2. Пространство циклов графа
- •§ 3. Независимое множество вершин графа
- •Алгоритм выделения пустых подграфов
- •§ 4. Вершинное число внешней устойчивости графа
- •§ 5. Плотность графа
- •Алгоритм выделения полных подграфов
- •§ 6. Раскраска графа
- •Оценки хроматического числа
- •Алгоритм минимальной раскраски вершин графа
- •§ 7. Планарность графа
- •Глава V. Оптимизационные алгоритмы теории графов
- •§ 1. Определение кратчайших путей. Алгоритм дейкстры
- •§ 2. Максимальный поток через сеть. Алгоритм
- •Алгоритм Форда – Фалкерсона
- •§ 3. Построение остова экстремального веса. Алгоритм краскала
- •§ 4. Метод ветвей и границ: задача коммивояжера. Общая модель задачи поиска
- •Дерево поиска частичных решений
- •§ 5. Применение ориентированных деревьев в задачах теории кодирования и диагностирования
- •§ 6. Построение оптимального дерева бинарного поиска. Алгоритм гильберта – мура
- •Алгоритм Гильберта – Мура построения оптимального дерева бинарного поиска Суть алгоритма
- •Алгоритм
- •§ 7. Сложность задач теории графов. Задача синтеза управляющих систем
- •Задача синтеза управляющих систем
- •Задача о выполнимости
- •Литература
- •Электронное пособие курс лекций
- •«Дискретная математика».
Операции над множествами
1. Объединением двух множеств М1 и М2 является множество М , состоящее из элементов, которые принадлежат хотя бы одному из множеств М1, М2 :
М =
2. Пересечением двух множеств М1 и М2 является множество М , состоящее из элементов, которые принадлежат как множеству М1 , так и множеству М2 :
3. Разностью множеств М1 и М2 является множество М , состоящее из элементов, принадлежащих множеству М1 и не принадлежащих множеству М2 :
4. Дополнением множества М (до универсума U ) называют множество, определяемое из соотношения . Другими словами
Операции объединения и пересечения множеств можно обобщить на конечное и бесконечное число множеств. Используя указанные операции, можно выражать одни множества через другие, при этом сначала выполняется операция дополнения, затем пересечения и только потом операция объединения (разности). Для изменения этого порядка в выражении используют скобки. Например,
Для наглядности на рис. 1.2 изображены с помощью кругов Эйлера непересекающиеся множества и включение множества :
Ø
Рис. 1.2
Кортежем (упорядоченным множеством) называют совокупность элементов, в которой каждый элемент занимает определенное место.
Число элементов кортежа называют его длиной.
Например, является кортежем длины n с элемента-ми
Если элементы кортежа есть действительные числа, то такие кортежи называют векторами.
Например, кортеж можно рассматривать, как вектор в трехмерном пространстве. Тогда проекции вектора на оси координат определятся следующим образом:
i=1, 2, 3.
Можно определить проекции сразу на две оси, например, 1 и 2 :
Если кортеж имеет вид , то
и
- номера осей, причем
Прямым (декартовым) произведением множеств М1 и М2 называют множество М вида
,
где (mi, mj) – двухэлементные кортежи.
Отметим, что в общем случае
Операцию прямого произведения можно распространить на большее число множеств.
Пример. □ Пусть , . Тогда
■
Если некоторое множество М состоит из кортежей одинаковой длины, то проекцией этого множества на некоторую ось называют множество проекций кортежей из множества М на эту ось.
Пример. Определить проекции и , i=1, 2, 3 , если
М1={(1,2,3,4,5),(2,1,3,5,5),(3,3,3,3,3),(3,2,3,4,3)},
M2={(1,2,3,4),(2,1,3,5)},
M3=
□ Сначала определим проекции множеств М1 и М2. Согласно определению проекции множества имеем:
, ,
,
Для определения и необходимо найти
:
Так как в множестве М3 кортежи имеют разные длины, то проекций и не существует. ■
Легко проверить, что если , то
а если то