Максимальное количество баллов, которое можно получить за выполнение БДЗ № 3, составляет 6 баллов (ориентировочно каждое задание оценивается одним баллом).
Начисленные баллы учитываются в рамках накопительной балльной системы.
Найти число остовов графа , а также изобразить диаграммы 4-х из них, если граф задан матрицей инцидентностей
.
Для взвешенного графа построить минимаьный остов, указать вес этого остова и его код Прюфера. Граф - граф с вершинами 1,2,3,4,5,6,7,8,9 и ребрами , , . Ребро с концами и имеет вес .
Найти эйлерову цепь на графе, вершинами которого являются натуральные числа 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 .
С помощью алгоритма Дейкстры найти расстояния от вершины 3 ориентированного графа до остальных его вершин; указать кратчайший путь от вершины 3 до вершины 9 . Граф - граф с вершинами 1,2,3,4,5,6,7,8,9 и дугами , . Вес дуги, идущий из вершины с номером в вершину с номером , определяется по формуле .
С помощью алгоритма Форда-Фалкерсона найти максимальный поток и минимальный разрез в сети с вершинами 1,2,3,4,5,6,7,8,9 и дугами , . Вес дуги, идущий из вершины с номером в вершину с номером , определяется по формуле . Вершина 1 – источник, вершина 9 – сток.
Построить схему из функциональных элементов , реализующую функцию .
Примеры решения задач, аналогичных заданиям БДЗ №3, разобраны в Л.1, §3.1 – 3.11.
Подготовка к экзамену
Билет экзамена состоит из двух частей. Часть 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 (повышенный уровень)
Сформулируйте и докажите критерий бихроматичности графа.
Вопросы к экзамену
1. Неориентированный граф: определение, элементы, локальные характеристики. Диаграмма графа. Лемма о рукопожатиях. Изоморфные графы. Обыкновенные, полные, двудольные графы. Матрицы смежности и инцидентности неориентированного графа. Подграфы, виды подграфов. Операции над графами: пересечение, объединение, удаление вершины, удаление ребра. Дизъюнктное разбиение графа.
2. Пути, цепи и циклы на графе. Лемма о простой цепи. Отношение достижимости. Компоненты связности. Число связности графа.
3. Мосты и циклы графа. Теорема о мостах. Теорема о мостах и циклах.
4. Цикломатическое число графа. Теорема о знаке цикломатического числа.
5. Определение и основные свойства деревьев. Теорема о характеристических свойствах деревьев. Следствие их нее. Понятие о лесе.
6. Остовы графа. Число остовов обыкновенного графа. Отыскание числа остовов с помощью матрицы Кирхгофа.
7. Минимальный остов. Задача о построении минимального остова. Алгоритм Краскала (без доказательства).
8. Кодирование деревьев. Бинарный код и код из натуральных чисел (кодирование и декодирование).
9. Укладки графов в трехмерном пространстве и на плоскости. Планарные графы. Формула Эйлера для плоских графов. Теорема о плоских графах.
10. Доказательство непланарности графов и . Критерии планарности (без доказательства).
11. Обходы графов. Эйлеров цикл и эйлерова цепь на графе. Критерии существования эйлерового цикла и эйлеровой цепи на графе (теорема об эйлеровых циклах, теорема об эйлеровых цепях). Алгоритм построения эйлерового цикла и эйлеровой цепи на графе. Понятие о гамильтоновом цикле и гамильтоновой цепи.
13. Фундаментальная система циклов: пространство циклов графа, базис пространства циклов. Алгоритм построения фундаментальной системы циклов.
14. Ориентированные графы: определение, элементы. Изоморфные орграфы. Матрицы смежности и инцидентности ориентированных графов. Ориентированные пути, цепи, циклы на орграфе. Связные и сильно связные орграфы. Ориентированные деревья.
15. Задача о поиске кратчайших путей в сети. Алгоритм Дейкстры.
16. Потоки в сетях. Постановка задачи о поиске максимального потока. Алгоритм Форда-Флакерсона. Его обоснование: три леммы и теорема Форда-Фалкерсона.
17. Схемы из функциональных элементов . Реализация булевых функций с помощью схем из функциональных элементов.
18. 18-й вопрос для 1-го потока: Упорядоченные бинарные диаграммы решений (УБДР). Реализация булевых функций с помощью УБДР. 18-й вопрос для 2-го потока: Элементы теории автоматов: ограниченно-детерминированные функции, реализация ограниченно-детерминированных функций конечными автоматами.
P.S. Объем подготовки по каждому вопросу зависит от того, на каком уровне студент собирается сдавать экзамену: базовом (студент собирается выполнять задания только 1-й части экзамена), или повышенном (студент также собирается отвечать на вопрос части 2). Вопросы, выделенные курсивом, изучаются для ответа на 2-ю часть экзамена.