Индивидуальное домашнее задание № 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, разобраны в учебном пособии Олейник Т.А. «Основы дискретной математики: теория и практика», - М.:МИЭТ, 2010, §3.1 – 3.11.

Подготовка к экзамену

Билет экзамена состоит из трех частей. Порядок проведения экзамена следующий. Вначале студент готовит в письменной форме ответы к заданиям части 1 экзаменационного билета (время подготовки 30-40 минут), после чего преподаватель проверяет написанное и при необходимости дополнительно устно беседует со студентом по вопросам части 1. В случае положительного ответа студент переходит к подготовке на вопрос частей 2 и 3. При желании студент может ограничиться ответом только на задания 1-й части.

Часть 1 содержит 8 заданий базового уровня сложности. Из них шесть теоретико-практических заданий по материалу модулю 2 «Теория графов», два другие - практические задания, при решении которых используется как материал модуля 1 (темы: бинарные отношения на множестве и представление булевых функций формулами), так и материал модуля 2. Правильный ответ на каждое задание ориентировочно оценивается 2 баллами. Максимальное число баллов за ответы на задания 1-й части – 16 баллов, минимальное положительное количество баллов – 10.

Часть 2 содержит один теоретический вопрос из списка вопросов к экзамену. При ответе на вопрос 2-й части билета проверяются знания и умения, соответствующие освоению дисциплины на повышенном уровне. Часть 2 экзамена сдается в форме устной беседы. Максимальное число баллов, выставляемое за ответ на вопрос 2-й части, равно восьми.

Часть 3 содержит две задачи повышенного уровня сложности: одна по модулю 1, вторая по модулю 2. Обе задачи взяты из открытого банка задач повышенной сложности (см. Олейник Т.А. «Основы дискретной математики: теория и практика. М.:МИЭТ, 2010», Задачи повышенной сложности 1.1 – 1.25, 2.1 – 2.43, 3.1 – 3.42). Максимальное число баллов, которое можно получить за решение задач 3-й части равно шести.

Для подготовки к сдаче 1-й части экзамена рекомендуется изучить материал разделов «Базовые понятия и утверждения» лекций 9-16 (в печатном варианте лекций - Олейник Т.А. «Основы дискретной математики: теория и практика», - М.:МИЭТ, 2010 - для 1-го потока глава 3; для 2-го потока §3.1 – 3.11, §4.1, 4.2), а также вспомнить о бинарных отношениях на множестве и о представлении булевых функций дизъюнктивными нормальными формами. Задания 1-й части билетов экзамена составляются на основе и с использованием этих материалов.

Для подготовки к сдаче 2-й части экзамена рекомендуется изучить в полном объеме материал лекций 9-16 (в печатном варианте лекций - Олейник Т.А. «Основы дискретной математики: теория и практика», - М.:МИЭТ, 2010 - для 1-го потока глава 3; для 2-го потока §3.1 – 3.11, §4.1, 4.2).

Для подготовки к третьей части экзамена рекомендуется прорешать задачи повышенной сложности №№ 1.1 – 1.25, 2.1 – 2.43, 3.1 – 3.42 из пособия Олейник Т.А. «Основы дискретной математики: теория и практика». М.:МИЭТ, 2010.

В таблице 4 приведен образец билета экзамена.

Таблица 4

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № «Образец» по курсу«Дискретная математика» МП-П Часть I 1. Сформулировать определение полного графа. Сколько ребер имеет полный граф с вершинами? Приведите пример полного графа с пятью вершинами, а также пример графа с тем же количеством вершин, не являющегося полным 2. Что называют компонентой связности вершины графа? Перечислите свойства, которыми обладают компоненты связности. Найдите компоненты связности графа , имеющего вершины , и ребра , , . 3. Какой подграф графа называется остовным? Какой подграф называется остовом? Приведите пример остовного подграфа графа , не являющегося остовом, а также пример остова графа . 4. Что такое плоская укладка графа? Для графа изобразите диаграмму, которая является его плоской укладкой, и диаграмму, которая его плоской укладкой не является. 5. Что такое эйлеров цикл? Сформулируйте критерий существования на графе эйлерового цикла. Определите с помощью этого критерия, есть ли эйлеров цикл на графе . 6. Что такое ориентированный граф? Приведите пример ориентированного графа с пятью вершинами и тремя дугами (граф задайте по определению и с помощью диаграммы). Укажите изолированные вершины графа (если они есть), дуги, инцидентные каждой из вершин, для каждой вершины определите полустепени исхода и захода. 7. Пусть . Задать с помощью графа бинарное отношение , заданное на множестве условием . Является ли отношение рефлексивным, симметричным, антисимметричным, транзитивным, отношением эквивалентности, отношением порядка? 8. Построить схему из функциональных элементов , реализующую функцию . Часть II Сформулируйте и докажите критерий бихроматичности графа. Часть III Задача 1. Показать, что если функция существенно зависит от переменной ( ), то двойственная к ней функция также существенно зависит от переменной . Задача 2. Показать, что граф с вершинами и двумя компонентами связности имеет не более ребер.

Вопросы к экзамену

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 и 3). Вопросы, выделенные курсивом, изучаются для ответа исключительно на 2-ю и 3-ю части экзамена.

Приложение 1

Календарный график

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