Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Комплект материалов для подготовки к контрольным мероприятиям для групп МП-21,22,23,24,25 (1-й поток)
и для групп МП-26, 27, 28, 29 (2-й поток)
Модуль 2
1. Подготовка к контрольной работе № 3
Контрольная работа № 3 состоит из 2-х частей: часть 1 включает 6 заданий, часть 2 – два задания. Правильное решение каждого задания части 1 оценивается 1 баллом. Правильное решение каждого задания части 2 оценивается ориентировочно 2 баллами. Максимальное количество баллов, которое можно получить за контрольную работу № 3, составляет 10 баллов. Начисленные баллы учитываются в рамках накопительной балльной системы.
Контрольная работа № 3 рассчитана на 1 час 20 минут. Структура контрольной работы показана в табл. 1, примерные варианты КР № 3 приведены в таблице 2.
|
Таблица 1 |
|
|
№ |
Описание задания |
|
Часть 1 |
|
|
1 |
Неориентированный граф задан множеством вершин и ребер: а) построить диаграмму; б) указать какой-либо путь, не являющийся цепью; какую-либо цепь, не являющуюся простой цепью; цикл, не являющийся простым; простой цикл (в каждом варианте что-нибудь одно). |
|
2 |
Для данного графа найти: а) цикломатическое число; б) хроматическое число. |
|
3 |
а) Построить неориентированный граф по матрице смежности (инцидентности); б) Найти матрицу смежности или инцидентности графа. |
|
4 |
а) Написать код дерева (в одних вариантах бинарный, в других – из натуральных чисел); б) Построить дерево по коду (в одних вариантах по бинарному, в других – из натуральных чисел). |
|
5 |
Ориентированный граф задан множеством вершин и ребер: а) построить диаграмму; б) определить, является ли граф связным, сильно связным. |
|
6 |
а) Построить ориентированный граф по матрице смежности (инцидентности); б) Найти матрицу смежности или инцидентности орграфа. |
|
7 |
Задача из перечня задач повышенной сложности главы 3 учебного пособия Олейник Т.А. Основы дискретной математики: теория и практика. М.:МИЭТ, 2010. |
|
8 |
Задача из перечня задач повышенной сложности главы 3 учебного пособия Олейник Т.А. Основы дискретной математики: теория и практика. М.: МИЭТ, 2010. |
Таблица 2
|
Примерный вариант 1 КР №3 |
|
|
Часть 1 |
|
|
1. |
Пусть - граф с вершинами и ребрами , , , , , , . а) Построить диаграмму графа . б) Указать на графе какой-либо путь, не являющийся цепью, и простой цикл. |
|
2. |
Для графа (задание 1) найти: а) цикломатическое число; б) хроматическое число, указать соответствующую раскраску. |
|
3. |
а) Построить граф по матрице инцидентности . б) Для графа из п. а) выписать матрицу смежности. |
|
4. |
а) Нарисовать какое-нибудь дерево с 8-ю ребрами, занумеровать его вершины и построить его код из натуральных чисел. б) Построить дерево по коду (0000010101011111). |
|
5. |
Пусть - ориентированный граф с вершинами и дугами , , , , . а) Построить диаграмму графа . б) Является ли граф связным? сильно связным? |
|
6. |
а) Построить граф по матрице смежности . б) Выписать матрицу инцидентности графа из п. а). |
|
7 |
Доказать, что в связном графе любые две простые цепи максимальной длины имеют по крайней мере одну общую вершину. |
|
8 |
Доказать, что граф непланарен. |
|
Примерный вариант 2 КР №3 |
|
|
Часть 1 |
|
|
1. |
Пусть - граф с вершинами и множеством ребер , , , , , , , , . а) Построить диаграмму графа . б) Указать на графе какую-либо цепь, не являющуюся простой цепью, и простой цикл. |
|
2. |
Для графа (задание 1) найти: а) цикломатическое число; б) хроматическое число. |
|
3. |
а) Построить граф по матрице инцидентности . б) Для графа из п.а) выписать матрицу смежности. |
|
4. |
а) Нарисовать какое-нибудь корневое дерево с 9-ю ребрами и построить его бинарный код. б) Построить дерево по коду[2 2 5 5 5 9 5 9]. |
|
5. |
Пусть - ориентированный граф с вершинами и дугами , , , , . а) Построить диаграмму графа . б) Является ли граф связным? сильно связным? |
|
6. |
а) Построить граф по матрице инцидентности . б) Выписать матрицу смежности графа из п. а). |
|
Часть 2 |
|
|
7. |
Показать, что граф с вершинами и двумя компонентами связности имеет не более ребер. |
|
8. |
Используя теорему Кирхгофа, показать, что число остовов в полном графе с помеченными вершинами равно . |
Задания 2-й части контрольной работы №3 формулируются на основе и с использованием банка задач, приведенного в учебном пособии Олейник Т.А. «Основы дискретной математики: теория и практика. М.:МИЭТ, 2010»: Л.1. § 3.1 - § 3.8, задачи повышенной сложности 3.1 – 3.42.
Для подготовки к выполнению части 2 контрольной работы № 3 рекомендуется прорешать задачи из этого списка.
2. Индивидуальное домашнее задание № 3»
Максимальное количество баллов, которое можно получить за выполнение БДЗ № 3, составляет 6 баллов (ориентировочно каждое задание оценивается одним баллом).
Начисленные баллы учитываются в рамках накопительной балльной системы.
Образец БДЗ №3 приведен в таблице 3.
Таблица 3
|
№ |
Образец индивидуального домашнего задания № 3 (БДЗ 3) |
|
1 |
Найти число остовов графа , а также изобразить диаграммы 4-х из них, если граф задан матрицей инцидентностей . |
|
2 |
Для взвешенного графа построить минимаьный остов, указать вес этого остова и его код Прюфера. Граф - граф с вершинами 1,2,3,4,5,6,7,8,9 и ребрами , , . Ребро с концами и имеет вес . |
|
3 |
Найти эйлерову цепь на графе, вершинами которого являются натуральные числа 1,2,3,4,5,6,7,8,9, причем вершина 1- вершина смежная с вершинами 3,4,7, 8, вершина 2 – с вершинами 3, 5, 8, 9, вершина 3 – с вершинами 1,2,4,5, вершина 4 – с вершинами 1 и 3, вершина 5 – с вершинами 2,3,7, 9, вершина 6 – с вершинами 7 и 8, вершина 7 – с вершинами 1, 5, 6 , 8, вершина 8 – с вершинами 1,2,6, 7 , 9, вершина 9 – с вершинами 2,5,8 . |
|
4 |
С помощью алгоритма Дейкстры найти расстояния от вершины 3 ориентированного графа до остальных его вершин; указать кратчайший путь от вершины 3 до вершины 9 . Граф - граф с вершинами 1,2,3,4,5,6,7,8,9 и дугами , . Вес дуги, идущий из вершины с номером в вершину с номером , определяется по формуле . |
|
5 |
С помощью алгоритма Форда-Фалкерсона найти максимальный поток и минимальный разрез в сети с вершинами 1,2,3,4,5,6,7,8,9 и дугами , . Вес дуги, идущий из вершины с номером в вершину с номером , определяется по формуле . Вершина 1 – источник, вершина 9 – сток. |
|
6 |
Построить схему из функциональных элементов , реализующую функцию . |
Примеры решения задач, аналогичных заданиям БДЗ №3, разобраны в Л.1, §3.1 – 3.11.
3. Подготовка к экзамену
Билет экзамена состоит из двух частей. Часть 1 содержит 6 теоретико-практических заданий базового уровня сложности. Правильный ответ на каждое задание ориентировочно оценивается 2 баллами. Максимальное количество баллов за ответы на задания 1-й части – 12 баллов, минимальное положительное количество баллов – 8.
Порядок проведения экзамена следующий. Вначале студент готовит в письменной форме ответы к заданиям части 1 экзаменационного билета (время подготовки 30-40 минут), после чего преподаватель проверяет написанное и при необходимости дополнительно устно беседует со студентом по вопросам части 1. В случае положительного ответа студент переходит к подготовке на вопрос части 2. При желании студент может ограничиться ответом только на задания 1-й части.
Часть 2 содержит один вопрос из списка вопросов к экзамену. При ответе на вопрос части 2 билета проверяются знания и умения, соответствующие повышенному уровню сложности. Часть 2 экзамена сдается в форме устной беседы. Максимальное количество баллов, выставляемое за ответ на вопрос 2-й части, равно 8.
Начисленные за ответы баллы учитываются в рамках накопительной балльной системы.
Для подготовки к сдаче 1-й части экзамена рекомендуется изучить материал разделов «Базовые понятия и утверждения» лекций 9-16 (для 1-го потока Л.1, глава 3; для 2-го потока Л.1, §3.1 – 3.11, §4.1, 4.2). Задания 1-й части билетов экзамена составляются на основе и с использованием этих материалов.
Для подготовки к сдаче 2-й части экзамена рекомендуется изучить в полном объеме материал лекций 9-16 (для 1-го потока Л.1, глава 3; для 2-го потока Л.1, §3.1 – 3.11, §4.1, 4.2).
В таблице 4 приведен образец билета экзамена.
Таблица 4
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № «Образец»по курсу «Дискретная математика» МП-П Часть I (базовый уровень) 1. Сформулировать определение полного графа. Сколько ребер имеет полный граф с вершинами? Приведите пример полного графа с пятью вершинами, а также пример графа с тем же количеством вершин, не являющегося полным 2. Что называют компонентой связности вершины графа? Перечислите свойства, которыми обладают компоненты связности. Найдите компоненты связности графа , имеющего вершины , и ребра , , . 3. Какой подграф графа называется остовным? Какой подграф называется остовом? Приведите пример остовного подграфа графа , не являющегося остовом, а также пример остова графа . 4. Что такое плоская укладка графа? Для графа изобразите диаграмму, которая является его плоской укладкой, и диаграмму, которая его плоской укладкой не является. 5. Что такое эйлеров цикл? Сформулируйте критерий существования на графе эйлерового цикла. Определите с помощью этого критерия, есть ли эйлеров цикл на графе . 6. Что такое ориентированный граф? Приведите пример ориентированного графа с пятью вершинами и тремя дугами (граф задайте по определению и с помощью диаграммы). Укажите изолированные вершины графа (если они есть), дуги, инцидентные каждой из вершин, для каждой вершины определите полустепени исхода и захода. Часть II (повышенный уровень) Сформулируйте и докажите критерий бихроматичности графа. |
Вопросы к экзамену
P.S. Объем подготовки по каждому вопросу зависит от того, на каком уровне студент собирается сдавать экзамену: базовом (студент собирается выполнять задания только 1-й части экзамена), или повышенном (студент также собирается отвечать на вопрос части 2). Вопросы, выделенные курсивом, изучаются для ответа на 2-ю часть экзамена.