Лекции по дискретке, страница 6
Описание файла
Документ из архива "Лекции по дискретке", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 3 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "дискретная математика" в общих файлах.
Онлайн просмотр документа "Лекции по дискретке"
Текст 6 страницы из документа "Лекции по дискретке"
а) 
; б) 
в) 
; г) 
д) 
е) 
ж) 
з) 
и) 
к) 
л) 
№ 1.13. Пусть I={a,b,c,d,e,f}, A={a,b,c}, B={f,e,c,a}, C={d,e,f}.
Найти множества:
а) 
б) 
в)
г) 
д) 
е) 
ж) 
з) 
и) 
№ 1.14. Даны два произвольных множества А и В такие, что 
Что представляют собой множества 
и 
№ 1.15. Даны два произвольных множества С и D такие, что 
Что можно сказать о множествах 
и 
№ 1.16. Дано произвольное множество Х. Найти множества: 
б) 
в) 
г) 
.
№ 1.17. Какие из следующих утверждений справедливы:
а) 
б) 
в) 
г) 
д) 
№ 1.18. Сформулируйте следующее утверждение на языке множеств: даны множества А, В и С; определить множество, включающее в себя только два из этих множеств.
№ 1.19. Решите предыдущую задачу при условии, что множества А, В и С взаимно не пересекаются.
№ 1.20. Даны множества V, W, Y, X и Z. Определить множество, включающее по крайней мере два из множеств V, W, X и Y и не включающее Z.
№ 1.21. Упростить выражения:
.
№ 1.22. Доказать тождества, используя законы алгебры множеств:
№ 1.23. Для произвольных множеств А, В, С, D I построить диаграммы Эйлера-Венна при условии:
.
№1.24. С помощью диаграмм Эйлера-Венна установить справедливость каждого из следующих утверждений относительно произвольных множеств А, В, С I:
если 
и 
, то 
если 
и 
то 
№ 1.25. показать с помощью диаграмм Эйлера Венна, какое из двух множеств 
и 
является подмножеством другого.
№ 1.26. Как можно представить следующие множества, используя диаграммы Эйлера-Венна:
{A, {A}}, {{a}, {b}}, {X, Y, Z},
где Х={x|х=1 или (х-2)Х},
Y={х|х=3 или (х-3)Y},
Z={x|x=2 или (х-2)Z}?
№ 1.27. Пусть даны множества А, В и С. С ВДоказать, что:
а) 
б) 
в) 
г) 
;
д) 
№ 1.28. Доказать, что если 
то 
.
№ 1.29. Доказать, что 
Решите задачи № 1.30 1.39 с использованием диаграммы Эйлера-Венна.
№ 1.30. В студенческом потоке 37 человек хорошо знают математику, а 25 человек – электронику, и 19 человек хорошо знают и математику и электронику. Если в потоке каждый из студентов знает хотя бы один из этих предметов, то сколько студентов в потоке?
№ 1.31. Из 250 студентов 151 изучают немецкий язык, 136 – французский язык, 27 – итальянский, 63 – французский и немецкий, 7 – итальянский и французский, 11 – немецкий и итальянский, 4 – все три языка.
а) Сколько студентов изучают немецкий или французский язык?
б) Сколько студентов изучают только итальянский язык?
в) Сколько студентов изучают немецкий и французский язык, но не
итальянский?
г) Сколько студентов не изучают ни одного языка?
д) Сколько студентов изусают хотя два иностранных языка?
№ 1.32. В отчете о количестве студентов, изучающих иностранные языки, сообщалось, что из 100 студентов все три языка изучают 5 человек, немецкий и английский – 10 человек, французский и английский – 8 человек, немецкий и французский – 20 человек, английский – 30, немецкий – 23, французский – 50. Инспектор, представивший этот отчет, был отстранен от работы. Почему?
№ 1.33 Каждый из 500 студентов обязан посещать хотя бы один из трех спецкурсов: по математике, физике, астрономии. Три спецкурса посещают 10 студентов, по математике и астрономии –25 студентов, спецкурс только по физике – 80 студентов. Известно также, что спецкурс по математике посещают 345 студентов, по физике – 145, по асирономии – 100 студентов. Сколько студентов посещают спецкурс только по астрономии? Сколько студентов посещают два спецкурса?
№ 1.34. Экзамен по математике содержал три задачи: по алгебре, геометрии и тригонометрии. Из 800 абитурентов задачу по алгебре решили 250 человек; по алгебре или геометрии – 660 человек; по две задачи решили 400 человек, из них две задачи по алгебре и и геометрии решили 150 человек, по алгебре и тригонометрии – 50 человек; ни один абитуриент не решил все задачи; 20 абитуриентов не решили ни одной задачи; только по тригонометрии задачи решили 120 человек. Сколько абитуриентов решили только одну задачу? Сколько абитуриентов решили задачи по тригонометрии?
№ 1.35. На курсах иностранных языков учится 600 человек. Из них французский изучают 220 человек, английский – 270 человек. Слушатели, изучающие английский язык, не изучают немецкий язык; один французский язык изучают 100 человек, один немецкий язык изучают 180 человек. Сколько человек изучает по два иностранных языка? Сколько человек изучает один иностранный язык?
№ 1.36. На кафедре иностранных языков работают 18 преподавателей. Из них 12 преподают английский язык, 11 – немецкий язык, 9 – французский язык. 5 преподавателей преподают английский и немецкий языки, 4 – английский и французский, 3 – немецкий и французский. Сколько преподавателей преподают все три языка? Сколько преподавателей преподают только два языка?
№ 1.37. Группа студентов из 25 человек сдала экзаменационную сессию со следующими результатами: 2 человека получили только “отлично”; 3 человека получили отличные, хорошие и удовлетворительные оценки; 4 человека только “хорошо”; 3 человека только хорошие и удовлетворительные оценки. Число студентов, сдавших сессию только на “удовлетворительно”, равно числу студентов, сдавших сессию только на “хорошо” и “отлично”. Студентов, получивших только отличные и удовлетворительные оценки – нет. Удовлетворительные или хорошие оценки получили только 22 студента. Сколько студентов сдали сессию только на “удовлетворительно”?
№ 1.38. Преподаватели кафедры Прикладной математики преподают на трех факультетах: механическом, технологическом, экономическом. На технологическом факультете работает 22 преподавателя, на механическом – 23 преподавателя, на механическом и экономическом –36 преподавателей. Только на технологическом факультете работают 10 преподавателей. 2 –на трех факультетах. 5 преподавателей работают только на механическом и экономическом факультетах. Число преподавателей, работающих только на механическом и технологическом факультетах, равно числу преподавателей, работающих на экономическом и технологическом факультетах. Сколько преподавателей работает на кафедре? Сколько преподавателей работает только на одном факультете?
№ 1.39. Экзамен по математике содержал три задачи: по алгебре, геометрии и тригонометрии. Из 750 абитуриентов задачу по алгебре решили 400 абитуриентов, по геометрии – 480, по тригонометрии – 420. Задачи по алгебре или геометрии решили 630 абитуриентов; по геометрии или тригонометрии – 600 абитуриентов; по алгебре или тригонометрии – 620 абитуриентов. 100 абитуриентов не решили ни одной задачи. Сколько абитуриентов решили все задачи? Сколько абитуриентов решили только одну задачу?
№ 1.40. Доказать аналитически, что для любых трех множеств А, В и С справедливы равенства:
а) 
б) 
в) 
если 
и 
г) 
если 
д) 
е) 
ж) 
если 
и 
з) 
если 
-
Теория графов.
11.Основные определения теории графов.
Определение.
Граф G — это упорядоченная пара G=(V,E), где V — это множество вершин или узлов, E — это множество пар различных вершин, называемых рёбрами.
Определение.
Ориентированным графом (графом или орграфом) будем называть тройку 
, где 
(
) — множество, называемое множеством вершин графа, 
— множество (возможно и пустое), называемое множеством дуг, 
— отображение, действующее из 
в 
, называемое отображением инцидентности.
Моментом рождения теории графов как математической дисциплины считают появление в 1736 году статьи Эйлера, в которой рассматривалась задача о Кёнигсбергских мостах (см. раздел дополнительные сведения). Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз.
Определение.
Граф называется не ориентированным, если каждое его ребро не ориентировано, и ориентированным, если ориентированы все его рёбра.
Определение.
Графы G и G' изоморфны, если существует такое взаимно однозначное соответствие между множествами их вершин V и V', что вершины соединены рёбрами в одном графе в том и только том случае, когда соответствующие им вершины соединены в другом графе. Если рёбра ориентированы, то их направления так же должны соответствовать друг другу.
Определение.
Вершина, не инцидентная никакому ребру, называется изолированной.
Определение.
Граф, состоящий только из изолированных вершин, называется нуль-графом.
Определение.
Полным графом называется граф 
ребрами, которого являются всевозможные пары для двух различных вершин из V.
Рис. 2.1. Полные графы.
Определение.
Рёбра у которых обе концевые точки совпадают 
называются петлёй. Петля обычно считается не ориентированной.
Определение.
Для каждого графа G существует обратный граф G*, получаемый изменением ориентации каждого из рёбер G на противоположную.
Определение.
Граф называется плоским, если он может быть изображён на плоскости так, что все пересечения рёбер являются вершинами G.
