Индивидуальное домашнее задание № 3»

Максимальное количество баллов, которое можно получить за выполнение БДЗ № 3, составляет 6 баллов (ориентировочно каждое задание оценивается одним баллом).

Начисленные баллы учитываются в рамках накопительной балльной системы.

Образец БДЗ №3 приведен в таблице 3.

Таблица 3

№	Образец индивидуального домашнего задания № 3 (БДЗ 3)
	Найти число остовов графа , а также изобразить диаграммы 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. Обходы графов. Эйлеров цикл и эйлерова цепь на графе. Критерии существования эйлерового цикла и эйлеровой цепи на графе (теорема об эйлеровых циклах, теорема об эйлеровых цепях). Алгоритм построения эйлерового цикла и эйлеровой цепи на графе. Понятие о гамильтоновом цикле и гамильтоновой цепи.

12. Раскраска графов. Хроматическое число. Утверждения о хроматических числах графа. Критерий бихроматичности графа.

13. Фундаментальная система циклов: пространство циклов графа, базис пространства циклов. Алгоритм построения фундаментальной системы циклов.

14. Ориентированные графы: определение, элементы. Изоморфные орграфы. Матрицы смежности и инцидентности ориентированных графов. Ориентированные пути, цепи, циклы на орграфе. Связные и сильно связные орграфы. Ориентированные деревья.

15. Задача о поиске кратчайших путей в сети. Алгоритм Дейкстры.

16. Потоки в сетях. Постановка задачи о поиске максимального потока. Алгоритм Форда-Флакерсона. Его обоснование: три леммы и теорема Форда-Фалкерсона.

17. Схемы из функциональных элементов . Реализация булевых функций с помощью схем из функциональных элементов.

18. 18-й вопрос для 1-го потока: Упорядоченные бинарные диаграммы решений (УБДР). Реализация булевых функций с помощью УБДР. 18-й вопрос для 2-го потока: Элементы теории автоматов: ограниченно-детерминированные функции, реализация ограниченно-детерминированных функций конечными автоматами.

P.S. Объем подготовки по каждому вопросу зависит от того, на каком уровне студент собирается сдавать экзамену: базовом (студент собирается выполнять задания только 1-й части экзамена), или повышенном (студент также собирается отвечать на вопрос части 2). Вопросы, выделенные курсивом, изучаются для ответа на 2-ю часть экзамена.

Поиск по сайту: