- •Содержание
- •Введение
- •Часть 1. Элементы теории множеств и отношений § 1. Понятие множества. Операции над множествами
- •Примеры
- •Операции над множествами
- •Основные тождества алгебры множеств
- •Упражнения
- •§ 2. Декартово произведение двух или нескольких множеств. Понятие отношения. Бинарные отношения
- •Упражнения
- •§ 3. Специальные бинарные отношения. Отношения эквивалентности
- •Упражнения
- •§ 4. Отношения порядка
- •Упражнения
- •§ 5. Функциональные отношения (отображения). Виды отображений
- •Виды отображений:
- •Упражнения
- •Часть 2. Теория графов
- •§ 1. Основные понятия теории графов
- •Способы задания графов. Матричное задание графов.
- •Свойства матриц смежности и инцидентности
- •Упражнения
- •§ Б 2. Булевы матрицы
- •Дизъюнкция (конъюкция)
- •§ 3. Связность графа. Компоненты связности. Матрица связности
- •Выделение компонент связности
- •Алгоритм выделения компонент сильной связности
- •Упражнения
- •§ 4. Полные графы. Двудольные графы. Однородные и реберные графы
- •Упражнения
- •§ 5. Поиск путей (маршрутов) с минимальным числом дуг (ребер)
- •Упражнения
- •§ 6. Расстояние в графах
- •Упражнения
- •§ 7. Нагруженные графы. Расстояния в нагруженном графе
- •Нахождение минимального пути в нагруженном орграфе
- •Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном орграфе из v1 в vi1 (i1≠1)
- •Упражнения
- •§ 8. Эйлеровы цепи и циклы в графах. Эйлеровы графы. Гамильтоновы цепи и циклы в графах. Гамильтоновы графы
- •Упражнения
- •§ 9. Деревья. Остов графа. Цикловой базис графа
- •Алгоритм нахождения кратчайшего остова в нагруженном графе
- •Упражнения
- •§ 10. Раскраска графов. Планарные графы Раскраска вершин графа
- •Одноцветные классы образуют независимые множества вершин.
- •Существуют и приближенные алгоритмы раскрашивания:
- •Упражнения
- •Варианты контрольных работ Часть 1. Элементы теории множеств и отношений Вариант № 1.
- •Вариант № 2.
- •Вариант № 3.
- •Вариант № 4.
- •Вариант № 5.
- •Вариант № 6.
- •Часть 2. Теория графов Вариант № 1.
- •Вариант № 2.
- •Вариант № 3.
- •Вариант № 4.
- •Вариант № 5.
- •Вариант № 6.
- •Ответы Часть 1
- •Часть 2
- •Тест по теории множеств и отношений
- •Тест по теории графов
- •Библиографический список
- •Любовь Васильевна Архипова Елена Сергеевна Дернович
- •Дискретная математика
Упражнения
3.1. Выяснить, какими свойствами обладают следующие бинарные отношения:
а) ρ={(1, 30), (5, 6), (6, 5), (30, 2), (1, 2), (5, 5)} на А={1, 2, 5, 6, 30};
б) ρ={(1, 1)} на А={1};
в) ρ={(1, 1), (2, 2), (3, 3)} на А={1, 2, 3};
г) ρ={(х, у) | х, уR и xy};
д) ρ={(х, у) | х, уZ+ и x, y – четные};
е) ρ={(х, у) | х, уR и х делится на у};
ж) отношение подобия на множестве всех многоугольников плоскости;
з) ρ={(х, у) | х и у имеют одинаковое имя} на множестве всех жителей г.Абакана.
3.2. Множество Х={4, 6, -2, 0, 3} разбито следующим образом:
а) {4, 6}, {–2, 0}, {3};
б) {4}, {6, –2, 0}, {3};
в) {4, 6, –2, 0}, {3};
г) задать какое-нибудь другое разбиение.
Записать отношение эквивалентности, соответствующее каждому разбиению.
3.3. На множестве Х={2, 4, 6, 8} заданы отношения эквивалентности:
а) ρ1={(2, 2), (4, 4), (6, 6), (8, 8)};
б) ρ2={(2, 2), (2, 4), (4, 2), (4.4), (6, 6), (8, 8)};
в) ρ3={(2, 2), (2, 4), (4, 2), (4, 4), (6, 6), (8, 8), (6, 8), (8, 6)}.
Записать для каждого отношения классы эквивалентности, порожденные элементами множества Х, и соответствующее отношению фактор-множество множества Х.
3.4. Доказать, что объединение ρ1ρ2 двух отношений эквивалентности ρ1 и ρ2, заданных на множестве Х, является отношением эквивалентности тогда и только тогда, когда ρ1ρ2=ρ1◦ρ2.
3.5. Доказать, что если ρ – есть транзитивное и симметричное отношение на множестве А и ДρRρ=А, то ρ – есть отношение эквивалентности на множестве А.
§ 4. Отношения порядка
Определение: Бинарное отношение называется предпорядком (квазипорядком) на множестве А, если оно рефлексивно и транзитивно на множестве А.
Определение: Бинарное отношение называется отношением частичного порядка на множестве А, если оно рефлексивно, транзитивно и антисимметрично на множестве А. Обозначение: .
Определение: Бинарное отношение называется отношением строгого порядка на множестве А, если антирефлексивно, антисимметрично и транзитивно на множестве А. Обозначение: .
Определение: Отношение порядка на множестве А, для которого любые два элемента сравнимы, т.е. : или , называется отношением линейного порядка.
Определение: Множество А с заданным на нём частичным порядком называется частично упорядоченным множеством. Обозначение: .
Определение: Множество А с заданным на нём строгим порядком называется строго упорядоченным множеством. Обозначение: .
Определение: Элемент частично упорядоченного множества называется максимальным, если .
Определение: Элемент частично упорядоченного множества называется наибольшим, если . Обозначение: .
Определение: Элемент частично упорядоченного множества называется минимальным, если .
Определение: Элемент частично упорядоченного множества называется наименьшим, если . Обозначение: .
Всякое конечное частично упорядоченное множество содержит как максимальные, так и минимальные элементы (причём может не единственные). Наибольший и наименьший элементы частично упорядоченного множества (если они существуют) единственны.
Заметим, что всякий наибольший элемент является максимальным, а всякий наименьший элемент является минимальным. Обратные утверждения, вообще говоря, неверны.
Рассмотрим упорядоченное множество А с введённым на нём отношением порядка . Говорят, что элемент y покрывает элемент x, если и не существует такого элемента , что и .
Если множество А конечно, то упорядоченное множество можно представить в виде схемы, в которой каждый элемент изображается точкой на плоскости, и если y покрывает x, то точки x и y соединяют отрезком, причём точку, соответствующую x, располагают ниже. Такие схемы называют диаграммами Хассе.