Министерство образования и науки РФ

Государственное образовательное учреждение

высшего профессионального образования

«Омский государственный технический университет»

Типовой расчет

ПО

Дискретной математике

Методические указания

Омск

Издательство ОмГТУ

2010

Составитель В. Н. Степанов

Основное назначение данных методических указаний – обеспечение курса "Дискретная математика".

Предназначены для студентов, обучающихся на инженерных специальностях.

Печатается по решению редакционно-издательского совета

Омского государственного технического университета

© ГОУ ВПО «Омский государственный

технический университет», 2010

Содержание

Задача 1.	Операции над множествами………………………………..	4
Задача 2.	Матрицы отношений………………………………………..	5
Задача 3.	Отношения…………………………………………………...	8
Задача 4.	Функции……………………………………………………...	12
Задача 5.	Эквивалентные множества. Мощность……………………	14
Задача 6.	Алгебраические структуры…………………………………	17
Задача 7.	Основные понятия по теории графов……………………...	23
Задача 8.	Изоморфизм графов…………………………………………	26
Задача 9.	Дополнение графа, реберный граф, двойственный граф…	31
Задача 10.	Операции над графами……………………………………...	33
Задача 11.	Фундаментальные циклы…………………………………...	36
Задача 12.	Остовное дерево минимального веса……………………...	39
Задача 13.	Кратчайшие пути в графе. Алгоритм Дейкстры…………..	42
Задача 14.	Задача коммивояжера……………………………………….	46
Задача 15.	Эйлеровы и гамильтоновы графы………………………….	48
Задача 16.	Эйлеровы циклы. Алгоритм Флёри………………………..	50
Задача 17.	Планарность графов………………………………………...	53
Задача 18.	Раскраска графа……………………………………………..	55
Список литературы………………………………………………………..		57

Задача 1. Операции над множествами

Доказать тождества или включения, упростить выражения, используя определения операций над множествами или свойства операций над множествами.

1. а)	б)
2. а)	б)
3. а)	б)
4. а)	б)
5. а)	б)
6. а)	б)
7. а)	б)
8. а)	б)
9. а)	б)
10. а)	б)
11. а)	б)
12. а)	б)
13. а)	б)
14. а)	б) упростить:
15. а)	б)
16. а)	б)
17. а)	б)
18. а)	б)
19. а)	б) упростить:
20. а)	б) упростить:
21. а) , где	б) упростить:
22. а) , где	б) упростить:
23. а)	б) упростить:
24. а)	б) упростить:
25. а)	б)