Контрольная работа. Раздел Множества
 Скачать 267.44 Kb.
|
1 2 Контрольная работа. 1. Раздел «Множества» 1. Фирма имеет 100 предприятий, причем каждое предприятие выпускает хотя бы одну продукцию вида А, В, С. Продукцию всех трех видов выпускают 10 предприятий, продукцию А и В – 18 предприятий, продукцию А и С – 15 предприятий, продукцию В и С – 21 предприятие. Число предприятий, выпускающих продукцию А равно числу предприятий, выпускающих продукцию В и равно числу предприятий, выпускающих продукцию С. Найти число всех предприятий. Обозначим:  – число элементов множества  . Обозначим множества:    По условию задачи:  – число всех предприятий (так как каждое предприятие выпускает хотя бы одну продукцию вида А, В, С, то объединение множеств  представляет множество всех предприятий фирмы);  – число предприятий, выпускающих продукцию 3-х видов;  – число предприятий, выпускающих продукцию видов  ;  – число предприятий, выпускающих продукцию видов  ;  – число предприятий, выпускающих продукцию видов  .Кроме того, дано:  , обозначим это число  .Используем формулу включений и исключений для трёх множеств:   Получаем:  .Число предприятий, выпускающих хотя бы один из трёх видов продукции равно 48. 2. Упростить:  По закону де Моргана,  Получаем:   Таким образом,  3. Является ли множество  подмножеством множества  ?Множество  являлось бы подмножеством множества  , если бы каждый элемент множества являлся бы элементом множества . Возьмём, например, элемент 1 множества . Этот элемент не принадлежит множеству как элемент (множество содержит подмножество  как элемент, но не 1). Следовательно, множество не является подмножеством множества .4. Придумать пример множеств  , каждое из которых имеет мощность континуума, так, чтобы выполнялось равенство:  .Мощность континуума имеет множество, эквивалентное отрезку  . В качестве множества возьмём множество равное этому отрезку:  . Возьмём  . Тогда взаимно-однозначное соответствие между точками отрезка  и точками устанавливается линейной функцией  . Значит, множество имеет мощность континуума. Возьмём  . Тогда взаимно-однозначное соответствие между точками отрезка  и точками устанавливается линейной функцией  . Значит, множество  имеет мощность континуума. Все три множества имеют мощность континуума. Равенство выполняется, очевидно: 5. Эквивалентны ли множества  и  ?Определим множество – множество корней квадратного уравнения  Значит,  Множества – конечные и содержат одно и то же число элементов (по два элемента). Значит, они эквивалентны – между ними можно установить взаимно-однозначное соответствие. Например,  .2. Раздел «Отношения. Функции» 1. Задано бинарное отношение  Найти  ,  ,  ,  . Проверить, будет ли отношение  рефлексивным, симметричным, антисимметричным, транзитивным?Область определения – множество всех первых компонент, фигурирующих в парах отношения : Область значений – множество всех вторых компонент, фигурирующих в парах отношения : Композиция – множество пар  – таких, что существует  такое, что  и  .         Учитывая каждую пару один раз, определяем композицию:  Обратное отношение, по определению:  Тогда:  Видим, что обратное отношение совпадает с заданным:  .Проверить, будет ли отношение рефлексивным, симметричным, антисимметричным, транзитивным.Не для любого элемента выполняется  : например,  . Значит, отношение не является рефлексивным.Видим, что для любой пары отношения пара  также принадлежит отношению. Значит, отношение является симметричным.Отношение не является антисимметричным: из одновременного выполнения  и  не следует:  . Например,  и  , но  .Транзитивность отношения: из и  должно следовать . Это не выполняется, например  и  , но . Значит, отношение не является транзитивным.2. Привести пример отношения не рефлексивного, не симметричного и транзитивного. Рассмотрим бинарное отношение, заданное на множестве  : Не для любого элемента  выполняется : например,  . Значит, отношение не является рефлексивным. В нашем случае, отношение является антирефлексивным: не выполняется ни для какого .Видим, что не выполняется: из следует . Например,  , но  . Значит, отношение не является симметричным.Транзитивность: из и должно следовать . Это выполняется:  , и (другие пары отношения “не стыкуются”). Значит, отношение является транзитивным.Другой пример – отношение “быть старше”, заданное на множестве людей. Ясно, что это отношение не рефлексивно, не симметрично и транзитивно. 3. Дана функция  , отображающая множество действительных чисел  во множество действительных чисел:  . Является ли эта функция сюръективной, инъективной, биективной? Почему?Поскольку  , то функция  является положительной:  для всех  . Тогда не для всех  существует – такое, что  (для  не существует). Значит, функция не является сюрьективной.Проверим, является ли функция инъективной. Производная функции:  Производная равна нулю при  . Это уравнение имеет 1 действительный корень:  . При  производная положительна и функция монотонно возрастает, при  производная отрицательна и функция монотонно убывает:  – точка минимума.График функции:  Значит, для любого значения  существует два значения  – такие, что  . Значит, функция не является инъективной (инъективная функция переводит любые два разных значения аргумента в разные значения).Функция не является биективной (биективная функция является сюръективной и инъективной).3. Раздел «Графы» 1. Описать граф, заданный матрицей смежности, используя как можно больше характеристик. Составить матрицу инцидентности и связности (сильной связности).  Поскольку матрица смежности является симметричной (элементы симметричны относительно главной диагонали), то заданный граф является неориентированным. Построим граф по заданной матрице смежности. Так как матрица смежности – квадратная матрица порядка 6, то граф имеет 6 вершин. Единице, стоящей на пересечении  той строки и  го столбца соответствует ребро, соединяющее вершины  . Граф:               Видим, что заданный граф является связным: между любыми двумя вершинами графа существует путь, связывающий рёбрами эти вершины. Заданный граф не имеет петель (это соответствует тому, что в матрице смежности все элементы по главной диагонали равны нулю). Подсчитаем степени вершин графа (для каждой вершины – число смежных с ней вершин):  Эйлеров цикл (цикл, проходящий через каждое ребро графа ровно один раз) в графе существует тогда и только тогда, когда выполняются два условия: 1) граф связный; 2) степень каждой вершины чётна. В заданном графе оба эти условия выполняются. Значит, заданный граф является эйлеровым. Эйлеров цикл, например такой:  Заданный граф является планарным – мы его построили на плоскости таким образом, что никакие два ребра не пересекаются. Найдём оптимальную раскраску графа. Граф содержит цикл из 3 вершин (треугольник)  , поэтому наименьшее число цветов, которыми можно раскрасить граф (хроматическое число  ), должно быть не меньше 3:  . С другой стороны, раскраску в три цвета в нашем случае можно осуществить. Задаём три цвета вершин треугольника : Для остальных трёх вершин задаём цвета:  Убеждаемся, что тремя цветами граф раскрашен (любые смежные вершины окрашены в разные цвета). Хроматическое число равно 3:  . Перечислим рёбра графа:    Матрица инцидентности графа содержит имеет  строк (по числу вершин) и  столбцов (по числу рёбер); для ребра  проставляем единицы в том столбце в строках, соответствующих вершинам ребра (остальные элементы – нули в этом столбце): Поскольку заданный граф – неориентированный, то матрица связности совпадает с матрицей сильной связности. Поскольку задан связный неориентированный граф, то из любой вершины можно попасть в любую вершину, значит матрица связности (сильной связности) в нашем случае состоит из всех единиц:  2. Пользуясь алгоритмом Форда-Беллмана, найти минимальный путь из  в  в ориентированном графе, заданном матрицей весов. Обозначим:  – величина минимального пути, содержащего не более  дуг из начальной вершины (в нашем случае ) в вершину  . Считаем:  .Алгоритм Беллмана – Форда выражается формулой:  Здесь  – длина дуги  .Последовательно заполняем таблицу из 7 строк (по строкам - вершины) и 7 столбцов (  ):  , двигаясь по столбцам.Если в нашем случае  , то пути из  нет; если  , то это значение даёт величину минимального пути из . Определяя изменение  по 7-й строке, последовательно определяем и сам путь (от конца к началу).Таблица :
В первой строке таблицы все значения – нули ( – стартовая вершина). В первом столбце все значения (за исключением первого) равны  . Второй столбец (за исключением 1-го значения) соответствует первой строке матрице дуг, так как все пути длины 1 из стартовой вершины соответствуют дугам из неё. Поскольку в вершины  можно попасть только из вершины (путь из одной дуги), то значения из 2-го столбца для этих вершин переносим во все остальные столбцы.Заполняем 3-й столбец – минимальные пути не более чем из 2 дуг. Для  : в эту вершину можно попасть (смотрим на матрицу весов) из вершин (кроме ) и длина пути  (равная 11) меньше  , тогда устанавливаем  . Для  : смотрим на матрицу весов – в эту вершину можно попасть вершин  ; из второго столбца таблицы видим, что 4+7 < 12+10 – присваиваем  значение 11 (путь  ). Для  : смотрим на матрицу весов – в эту вершину можно попасть вершин  ; из второго столбца таблицы видим, что 6+3 < 12+9 – присваиваем  значение 9 (путь  ). Значение  остаётся таким же как и  , так как в можно попасть только из вершин  , а для строк 5-й и 6-й во втором столбце стоит .Заполняем 4-й столбец – минимальные пути не более чем из 3 дуг. Для : в эту вершину можно попасть только из вершин  , но для этих вершин значения уже не могут поменяться, поэтому значения из 3-го столбца для переносим во все остальные столбцы. Для : смотрим на матрицу весов – в эту вершину можно попасть вершин ; из 3-го столбца таблицы видим, что 4+7 < 11+10, поэтому значение  переносится из  . Для : смотрим на матрицу весов – в эту вершину можно попасть вершин ; из 3-го столбца таблицы видим, что 6+3 < 11+9, поэтому значение  переносится из  . Для : смотрим на матрицу весов – в эту вершину можно попасть вершин ; из 3-го столбца таблицы видим, что 11+8 < 9+11, поэтому значение  устанавливаем:  (путь  ).Теперь все значения в 4-м столбце заполнены (конечными числами). Поскольку в конечную вершину можно попасть только из вершин , а значения для этих вершин уже были перенесены из 3-го столбца, то дальнейшее обновление значений (уменьшение) для следующих столбцов уже невозможно, поэтому можно продублировать значения 4-го столбца для следующих столбцов.Таблица заполнена. Минимальный путь из вершины в вершину длиной 19: .3. Пользуясь алгоритмом Краскала, найти минимальное остовное дерево для графа, заданного матрицей длин ребер.  Задан полный неориентированный граф (каждая вершина связана ребром с каждой другой вершиной, как видим по матрице). Построим граф:                Для построения остовного дерева минимального веса используем алгоритм Краскала. Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса. У нас  - ребро с минимальным весом 2 – включаем его в остовное дерево: Из оставшихся рёбер минимальный вес равный 4 имеет ребро  – включаем его в остовное дерево: Из оставшихся рёбер минимальный вес равный 6 имеют ребра  ,  и  . Если включить все эти три ребра, то образуется цикл  , поэтому сразу три ребра включить нельзя. Если включить ребра и , то циклов не образуются, кроме того добавляются новые вершины  – поэтому можно включить оба этих ребра в остовное дерево: Видим, что все вершины включены в связный граф - остовное дерево минимального веса построено, его вес равен  . 1 2 |
