- •Содержание
- •Введение
- •Часть 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
- •Тест по теории множеств и отношений
- •Тест по теории графов
- •Библиографический список
- •Любовь Васильевна Архипова Елена Сергеевна Дернович
- •Дискретная математика
Упражнения
10.1. Найти хроматические числа для графов:
а) К6
б) К3,5
в) Е2
г) Е3
10.2. Найти независимые множества вершин, вершинное число независимости и хроматическое число графа G:
а) б) в)
10.3. Найти хроматическое число графа, заданного матрицей смежности:
10.4. Используя точный алгоритм раскрашивания, раскрасить вершины графов из задач 10.2, 10.3.
10.5. Построить граф с хроматическим числом, равным:
а) 4
б) 5
в) 3.
10.6. Найти толщину графа:
Варианты контрольных работ Часть 1. Элементы теории множеств и отношений Вариант № 1.
1. Упростить запись множества, используя основные равенства множеств:
.
2. Доказать тождество: A(BC)=(AB) (AC).
3. Найти область определения, область значений бинарного отношения , инверсию бинарного отношения и композиции ◦, ◦-1, -1◦, если ={(x,y) | x,y R и y<3x+8}.
4. Проверить, какими свойствами обладает бинарное отношение
={((a,b),(c,d)) | a+d=b+c}, заданное на множестве NN.
5. Задать некоторое разбиение множества А={1,3,5,7,9}. Записать отношение эквивалентности, соответствующее данному разбиению. Найти фактор-множество множества А.
Вариант № 2.
1. Упростить запись множества, используя основные равенства множеств:
.
2. Доказать тождество: (AB)C=(AC) (BC).
3. Найти область определения, область значений бинарного отношения , инверсию бинарного отношения и композиции ◦, ◦-1, -1◦, если ={(x,y) | x,y R и y=x3}.
4. Проверить, какими свойствами обладает бинарное отношение
={(А, В) / точки А и В лежат по одну сторону от заданной прямой}, заданное на множестве всех точек плоскости.
5. На множестве А={1,3,5,7,9} задано отношение эквивалентности
={(1, 1), (3, 3), (5, 5), (7, 7), (9, 9), (1, 3), (3, 1)}. Найти классы эквивалентности, порожденные элементами данного множества.
Вариант № 3.
1.Упростить запись множества, используя основные равенства множеств:
.
2. Доказать тождество: A(B\C)=(AB)\(AC).
3. Найти область определения, область значений бинарного отношения , инверсию бинарного отношения и композиции ◦, ◦-1, -1◦, если ={(x,y) | x,y R и 2x+y<7}.
4. Проверить, какими свойствами обладает бинарное отношение
={((a,b),(c,d)) | ad=bc} заданное на множестве NN.
5. На множестве А={1,3,5,7,9} задано отношение эквивалентности
={(1, 1), (3, 3), (5, 5), (7, 7), (9, 9), (1, 3), (3, 1)}. Найти фактор-множество множества А.
Вариант № 4.
1. Упростить запись множества, используя основные равенства множеств:
.
2. Доказать тождество: A(BC)=(AB)(AC).
3. Найти область определения, область значений бинарного отношения , инверсию бинарного отношения и композиции ◦, ◦-1, -1◦, если ={(x,y) | x,y R и x2+y2>8}.
4. Проверить, какими свойствами обладает бинарное отношение
={(x,y)| окружность y пересекает окружность x или совпадает с ней}, заданное на множестве всех окружностей плоскости.
5. На множестве А={1,3,5,7,9} задать минимальное отношение эквивалентности. Найти классы эквивалентности и фактор-множество множества А.