Методические рекомендации "Дискретная математика"
учебно-методическое пособие по теме

БУ «НИЖНЕВАРТОВСКИЙ ПРОФЕССИОНАЛЬНЫЙ КОЛЛЕДЖ»

Методические указания по выполнению самостоятельных работ

Дисциплина «ДИСКРЕТНАЯ МАТЕМАТИКА»

для специальности 230115 «Программирование в компьютерных системаХ»

(методическое пособие для студентов)

Преподаватель Геталова В.В.

Нижневартовск 2013

Геталова В.В. Дискретная математика

Методические указания составлены для выполнения самостоятельной работы студентов специальности 230115 " Программирование в компьютерных системах ". Нижневартовск: БУ «Нижневартовский профессиональный колледж», 2013г.-32с.

Методические указания рассмотрены на заседании кафедры «Программное обеспечение ВТ и АС»

Протокол  №_____ от_____________2013г.

СОДЕРЖАНИЕ

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА        

1.ТРЕБОВАНИЯ К ОФОРМЛЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ        

2.КОНТРОЛЬНАЯ РАБОТА № 1        

2.1.        Вариант 1                

2.2.        Вариант 2        

2.3.        Вариант 3        

2.4.        Вариант 4        

2.5.        Вариант 5        

2.6.        Вариант 6        

2.7.        Вариант 7        

2.8.        Вариант 8        

2.9.        Вариант 9        

2.10.        Вариант 10        

3.КОНТРОЛЬНАЯ РАБОТА № 2        

3.1.        Вариант 1        

3.2.        Вариант 2        

3.3.        Вариант 3        

3.4.        Вариант 4        

3.5.        Вариант 5        

3.6.        Вариант 6        

3.7.        Вариант 7        

3.8.        Вариант 8        

3.9.        Вариант 9        

3.10.        Вариант 10        

Рекомендуемая литература        

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Самостоятельная работа студента по предмету «Дискретная математика» выполняется студентами третьего курса в соответствии с учебным планом и программой предмета.

Самостоятельная работа выполняется с целью углубления и закрепления знаний по предмету.

Самостоятельная работа включает в себя контрольные работы по темам.

Номер варианта контрольной работы определяется по следующей таблицы

Например: Ваша фамилия Петров и по списку № 15, следовательно номер вашего варианта 10

Перечень тем самостоятельных работ студентов

1. ТРЕБОВАНИЯ К ОФОРМЛЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ

Контрольная работа должна соответствовать варианту и содержать: титульный лист, содержание, условие задачи и ее решение, список используемой литературы. Сроки сдачи указываются преподавателем.

Размер страницы: размеры полей: верхнее – 2.0 см; нижнее – 2 см; левое – 3,0 см; правое - 1,5 см; переплет – 0 см. Расстояние от края до верхнего колонтитула – 2.5 см; до нижнего – 2 см.

Шрифт—Times New Roman, 14пт;

Интервал —1,5пт

Нумерация страниц — по правому краю, внизу.

В тексте запрещается использовать, выделение жирным шрифтом, курсивом.

Для нумерации списка используется следующий стиль:

2. и т.д.

Для маркированного списка используется следующий символ: —

2. КОНТРОЛЬНАЯ РАБОТА № 1

1.  Вариант 1

Задача 1

Решить задачу, используя диаграмму Эйлера-Венна.

Четырнадцать спортсменов участвовали в кроссе, 16 – в соревнованиях по плаванью, 10 – в велосипедных гонках. Восемь участников участвовали в кроссе и заплыве, 4 – в кроссе и велосипедных гонках, 9 – в плавании и велосипедных гонках. Во всех трех соревнованиях участвовали три человека. Сколько всего было спортсменов?

Задача 2

Задано универсальное множество U ={1, 2, 3, 4, 5, 6, 7, 8} и множества  X={1, 3, 6, 7}, Y = {3, 4, 7, 8}, Z = {3, 4, 7, 8}. Построить булеан множества Х и любое разбиение множества Z. Выполнить действие .

Задача 3

Пусть X={1,2,3,4}. Бинарное отношение  задано характеристическим свойством:

.

Представить отношение различными способами. Выяснить, какими свойствами оно обладает.

Задача 4

Заданы отношения:

R:        

S:

Записать обозначения операций и выполнить их:

1. селекция отношения R по условию “ A2 > b”;
2. проекция на список (3,1) объединения отношений R и S.

Задача 5

Шесть старушек вышли во двор поболтать. На скамейке помещаются только четыре из них. Сколькими способами их можно рассадить на скамейке?

Задача 6

На веревке сушатся четыре белых полотенца и три желтых. Сколькими способами их можно развесить, если полотенца одного цвета не отличаются друг от друга?

2.  Вариант 2

Задача 1

Решить задачу, используя диаграмму Эйлера-Венна.

В туристском клубе несколько раз за лето организуются походы, причем все члены клуба хотя бы раз в них участвуют. Сорок человек побывали в пеших походах, 28 – в конных, 25 – в лодочных. И в пеших, и в конных походах побывало 20 человек, в пеших и лодочных – 15, в конных и лодочных – 8, во всех видах походов побывало 6 человек. Сколько туристов в клубе?

Задача 2

Задано универсальной множество U = {1, 2, 3, 4, 5, 6, 7, 8} и множества X = {3, 5, 6, 7, 8}, Y = {1, 2, 4, 6}, Z = {1, 2, 7, 8}. Построить булеан множества Y и любое разбиение множества X. Выполнить действие .

Задача 3

Пусть X = {1, 2, 3, 4, 5}. Отношение  задано характеристическим свойством:

Задать отношение другими возможными способами. Выяснить, какими свойствами оно обладает.

Задача 4

Заданы отношения: R:

        S:

Записать обозначения операций реляционной алгебры и выполнить их:

1. проекция отношения R на список (1,3);
2. соединение отношений R и S по условию “A2 = B1”.

Задача 5

На подоконнике стоят четыре горшка с цветами. Сколькими способами их можно расставить на подоконнике?

Задача 6

Шесть мячей раскладывают по двум коробкам. Сколькими способами это можно сделать? (Считается, что вместимость коробки достаточна для всех мячей).

3. Вариант 3

Задача 1

Решить задачу, используя диаграмму Эйлера-Венна.

В отделе НИИ работают несколько человек, причем каждый из них знает хотя бы один иностранный язык. Английский язык знают шесть человек, немецкий – шесть человек, французский – семь. Четыре человека знают английский и немецкий языки, три человека – немецкий и французский, два – французский и английский, один знает все три языка. Сколько человек работает в отделе?

Задача 2

Задано универсальной множество U = {1, 2, 3, 4, 5, 6, 7, 8} и множества X = {5, 6, 7, 8}, Y = {1, 3, 5, 6, 8}, Z = {1, 2, 5, 7}. Построить булеан множества Х и любое разбиение множества Y. Выполнить действие .

Задача 3

Пусть X = {-2, -1, 0, 1, 2, 3}. Отношение  задано характеристическим свойством:

Представить отношение R другими возможными способами. Выяснить, какими свойствами оно обладает.

Задача 4

Заданы отношения: R:

S:

Записать обозначения операций реляционной алгебры и выполнить их:

1. проекция отношения R на список (1,3);
2. соединение отношений R и S по условию “A1>B1”.

Задача 5

Пятнадцать студентов пришли на занятия, но в аудитории оказалось только 13 стульев. Сколькими способами они могут выбрать двоих, чтобы отправить их на поиски стульев?

Задача 6

Сколькими способами можно расставить семь катеров у двух причалов, если у каждого причала могут поместиться  все семь? Способы различаются лишь количеством катеров у каждого причала.

4.  Вариант 4

Задача 1

Решить задачу, используя диаграмму Эйлера-Венна.

Из 80 студентов занимаются баскетболом 30 человек, легкой атлетикой 25 человек, шахматами – 40 человек. Баскетболом и легкой атлетикой занимается 8 человек, шахматами и легкой атлетикой – 10 человек, шахматами и баскетболом – 5 человек. Тремя видами спорта занимаются три человека. Сколько человек занимаются спортом?

Задача 2

Задано универсальное множество U = {1, 2, 3, 4, 5, 6, 7, 8} и множества X = {1, 5, 6, 7, 8}, Y = {2, 3, 6, 7, 8}, Z = {1, 3, 5, 8}. Найти булеан множества Z и какое-любое разбиение множества X. Выполнить действие .

Задача 3

Отношение R на множестве X задано перечислением своих элементов: R = {(1,2), (1,1), (2,2), (2,1), (3,1), (3,3)}. Нарисуйте график, схему и граф отношения. Запишите его матрицу. Какими свойствами обладает отношение? Является ли оно отношением эквивалентности? Объясните ответ.

Задача 4

Заданы отношения:

R:

S:

Записать обозначения операций реляционной алгебры и выполнить их:

1. проекция отношения R на список (2,3);
2. соединение отношений R и S по условию “A3=B1”.

Задача 5

Семеро студентов пошли вместо лекции в кино. Но оказалось, что в кассе осталось только три билета. Сколькими способами они могут выбрать этих троих?

Задача 6

Сколькими способами можно рассадить шесть кустов пионов на трех клумбах, если на каждой клумбе могут поместиться все шесть?

5.  Вариант 5

Задача 1

Решить задачу, используя диаграмму Эйлера-Венна.

Десять читателей взяли в библиотеку фантастику, 11 – детективы, 8 – приключения. Фантастику и приключения взяли 4 человека, фантастику и детективы – 6, приключения и детективы – 3, двое взяли три вида книг. Сколько читателей побывало в библиотеке?

Задача 2

Задано универсальное множество U = {1, 2, 3, 4, 5, 6, 7, 8} и множества X = {2, 4, 5, 7, 8}, Y = {1, 2, 3, 4, 6}, Z = {1, 5, 6, 8}. Найти булеан множества Z и какое-любое разбиение множества Y. Выполнить действие .

Задача 3

Пусть X = {0, 1, 2, 3, 4}. Бинарное отношение  задано характеристическим свойством:

.

Представить отношение R другими возможными способами. Какими свойствами оно обладает?

Задача 4

Заданы отношения: R:

S:

Записать обозначения операций реляционной алгебры и выполнить их:

1. селекция отношения R по условию “A2>А3”;
2. проекция на список (3,1) объединения отношений R и S.

Задача 5

Семеро рыбаков отправились на остров на двух лодках. Ночью одна из лодок уплыла. Сколькими способами они могут отправить троих в погоню за уплывшей лодкой?

Задача 6

Сколькими различными способами можно разложить восемь монет различного достоинства в два кармана?

6.  Вариант 6

Задача 1

Решить задачу, используя диаграмму Эйлера-Венна.

Из 10 участников ансамбля шестеро умеют играть на гитаре, пятеро на ударных инструментах, пятеро на духовых. Двумя инструментами владеют: гитарой и ударными – трое, ударными и духовыми – двое, гитарой и духовыми – четверо. Остальные участники ансамбля только поют. Сколько певцов в ансамбле?

Задача 2

Задано универсальное множество U = {1, 2, 3, 4, 5, 6, 7, 8} и множества X = {2, 5, 6, 7, 8}, Y = {2, 4, 6, 8}, Z = {1, 2, 3, 4}. Найти булеан множества Y и какое-любое разбиение множества Z. Выполнить действие .

Задача 3

Пусть X = {1, 2, 3, 4, 5}. Бинарное отношение  задано характеристическим свойством:

.

Представить отношение R другими возможными способами. Какими свойствами обладает это отношение? Является ли оно отношением эквивалентности?

Задача 4

Заданы отношения:

R:

S:

Записать обозначения операций реляционной алгебры и выполнить их:

1. селекция отношения S по условию “B1>B3”;
2. соединение отношений R и S по условию “A1=B2”.

Задача 5

В библиотеку поступило девять новых различных книг. Сколькими способами читатель может выбрать три из них?

Задача 6

В елочной гирлянде восемь лампочек: две желтых, три красных, три синих. Сколькими способами их можно расположить в гирлянде?

7.  Вариант 7

Задача 1

Решить задачу, используя диаграмму Эйлера-Венна.

Каждый из студентов группы занимается хотя бы одним видом спорта. Пятеро занимаются альпинизмом, шестеро – волейболом, 10 человек – борьбой. Известно, что двое занимаются и альпинизмом, и волейболом; трое – волейболом и борьбой; четверо – альпинизмом и борьбой; а один занимается всеми тремя видами спорта. Сколько студентов занимается только борьбой?

Задача 2

Задано универсальное множество U = {1, 2, 3, 4, 5, 6, 7, 8} и множества X = {2, 4, 5, 7, 8}, Y = {1, 2, 3, 4, 6}, Z = {4, 5, 6, 8}. Найти булеан множества Z и какое-любое разбиение множества Y. Выполнить действие .

Задача 3

Пусть X = {0, 1, 2, 3, 4}. Бинарное отношение  задано характеристическим свойством:

.

Представить отношение R другими возможными способами. Какими свойствами обладает это отношение? Является ли оно отношением эквивалентности?

Задача 4

Заданы отношения: R:

S:

Записать обозначения операций реляционной алгебры и выполнить их:

1. селекция отношения R по условию “A1>A2”;
2. проекция на список (2,3) объединения отношений R и S.

Задача 5

В магазине продается восемь типов шляп. Сколькими способами дама может выбрать себе три разных шляпы?

Задача 6

В библиотеке на полке стоит три одинаковых учебника по математике и четыре разных по программированию. Сколькими способами их можно расставить на полке?

8.  Вариант 8

Задача 1

Решить задачу, используя диаграмму Эйлера-Венна.

В одной из студенческих групп все студенты умеют программировать. Десять человек умеют работать на Бейсике, 10 – на Паскале, 6 – на Си. Два языка знают: 6 человек Бейсик и Паскаль, 4 – Паскаль и Си, 3 – Бейсик и Си. Один человек знает все три языка. Сколько студентов в группе?

Задача 2

Задано универсальное множество U = {1, 2, 3, 4, 5, 6, 7, 8} и множества X = {1, 2, 4, 6, 7}, Y = {2, 3, 5, 7, 8}, Z = {1, 4, 7, 8}. Найти булеан множества Z и какое-любое разбиение множества Y. Выполнить действие .

Задача 3

Пусть X = {1, 2, 3, 4}. Бинарное отношение  задано характеристическим свойством:

.

Представить отношение R другими возможными способами. Выяснить, какими свойствами оно обладает.

Задача 4

Заданы отношения:

 R:

S:

Записать обозначения операций реляционной алгебры и выполнить их:

1. проекция на список (2,1)  отношения S;
2. соединение отношений R и S по условию “A1>B2”.

Задача 5

В сессию студент сдает пять экзаменов. Сколько возможных результатов сессии (экзаменационной оценкой может быть 2, 3, 4, 5)?

Задача 6

Сколькими способами 12 книг можно расставить по трем полкам, если на каждой полке могут поместиться все книги? Способы различаются лишь количеством книг на полках.

9.  Вариант 9

Задача 1

Решить задачу, используя диаграмму Эйлера-Венна.

При изучении читательского спроса оказалось, что 60% опрошенных читает журнал «Огонек», 50% - журнал «Юность», 50% - журнал «Аврора». Журналы «Огонек» и «Юность» читают 30% опрошенных, «Юность» и «Аврора» - 20%, «Огонек» и «Аврора» - 40%, все три журнала – 10%. Сколько процентов опрошенных не читают ни один журнал?

Задача 2

Задано универсальное множество U = {1, 2, 3, 4, 5, 6, 7, 8} и множества X = {2, 3, 4, 5, 7}, Y = {1, 2, 4, 8}, Z = {2, 5, 7, 8}. Найти булеан множества Y и какое-любое разбиение множества X. Выполнить действие .

Задача 3

Пусть X = {1, 2, 3, 4, 5}. Бинарное отношение  задано характеристическим свойством:

.

Представить отношение R другими возможными способами. Выяснить, какими свойствами оно обладает. Является ли R отношением эквивалентности?

Задача 4

Заданы отношения: R:

S:

Записать обозначения операций реляционной алгебры и выполнить их:

1. проекция на список (2,1)  отношения R;
2. соединение отношений R и S по условию “A1≥B1”.

Задача 5

На столе лежат восемь яблок. Сколькими способами можно выбрать два из них?

Задача 6

Требуется покрасить шесть гаражей, стоящих в один ряд. На каждый из гаражей расходуется одна банки краски. Сколькими способами можно покрасить гаражи, если есть две банки красной краски, три зеленой и одна синей?

10.  Вариант 10

Задача 1

Решить задачу, используя диаграмму Эйлера-Венна.

В день авиации всех желающих катали на самолете, планере, дельтаплане. На самолете прокатилось 30 человек, на планере – 20, на дельтаплане – 15. И на самолете, и на планере каталось 10 человек, на самолете и дельтаплане – 12, на планере и дельтаплане – 5, два человека прокатились и на самолете, и на планере, и на дельтаплане. Сколько было желающих прокатиться?

Задача 2

Задано универсальное множество U = {1, 2, 3, 4, 5, 6, 7, 8} и множества X = {1, 3, 5, 7, 8}, Y = {2, 5, 6, 8}, Z = {1, 3, 5, 6}. Найти булеан множества Z и какое-любое разбиение множества Y. Выполнить действие .

Задача 3

Пусть X = {1, 2, 3, 4, 5}. Бинарное отношение  задано характеристическим свойством:

.

Представить отношение R другими возможными способами. Выяснить, какими свойствами оно обладает.

Задача 4

Заданы отношения: R:

S:

Записать обозначения операций реляционной алгебры и выполнить их:

1. проекция на список (3,2)  отношения R;
2. соединение отношений R и S по условию “A1=B1”.

Задача 5

Сколькими способами 8 человек можно рассадить на лавке (всех в один ряд)?

Задача 6

Восемь туристов отправились в путь на двух лодках, в меньшей из которых могли поместиться не более четверых, а в большей – не более шестерых человек. Сколькими различными способами они могут распределиться в разные лодки? (Распределения считаются различными, если хотя бы один турист окажется в другой лодке).

3. КОНТРОЛЬНАЯ РАБОТА № 2

1. Вариант 1

1. Для орграфа G0 (рис. 1) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
2. Занумеруйте вершины графа G1 (рис. 1) и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и матрицу инцидентности графа G1, занумеровав его ребра.
3. Покажите, что графы G1и G2 (рис. 1) изоморфны. Планарен ли граф G2?
4. Определите цикломатическое число графа G1 (рис. 1). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
5. Выясните, сколько ребер нужно удалить из графа G1 (рис. 1) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.

Рисунок 1

2.  Вариант 2

1. Для орграфа G0 (рис. 2) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
2. Занумеруйте вершины графа G1 (рис. 2) и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и инцидентности графа G1, занумеровав его ребра.
3. Покажите, что графы G1и G2 (рис. 2) изоморфны. Планарен ли граф G2?
4. Определите цикломатическое число графа G1 (рис. 2). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
5. Выясните, сколько ребер нужно удалить из графа G1 (рис. 2) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.

        Рисунок 2

3.  Вариант 3

1. Для орграфа G0 (рис. 3) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
2. Дан неорграф G1 (рис. 3). Занумеруйте вершины графа и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и матрицу инцидентности графа G1, занумеровав его ребра.
3. Покажите, что графы G1и G2 (рис. 3) изоморфны. Является ли граф G2 планарным?
4. Определите цикломатическое число графа G1 (рис. 3). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
5. Выясните, сколько ребер нужно удалить из графа G1 (рис. 3) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.

Рисунок 3

4.  Вариант 4

1. Для орграфа G0 (рис. 4) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
2. Занумеруйте вершины графа G1 (рис. 4) и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и матрицу инцидентности графа G1, занумеровав его ребра.
3. Покажите, что графы G1и G2 (рис. 4) изоморфны. Является ли граф G2 планарным?
4. Определите цикломатическое число графа G1 (рис. 4). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
5. Выясните, сколько ребер нужно удалить из графа G1 (рис. 4) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.

Рисунок 4

5.  Вариант 5

1. Для орграфа G0 (рис. 5) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
2. Занумеруйте вершины графа G1 (рис. 5) и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и матрицу инцидентности графа G1, занумеровав его ребра.
3. Покажите, что графы G1и G2 (рис. 5) изоморфны. Является ли граф G2 планарным?
4. Определите цикломатическое число графа G1 (рис. 5). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
5. Выясните, сколько ребер нужно удалить из графа G1 (рис. 5) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.

Рисунок 5

6. Вариант 6

1. Для орграфа G0 (рис. 6) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
2. Занумеруйте вершины графа G1 (рис. 6) и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и матрицу инцидентности графа G1, занумеровав его ребра.
3. Покажите, что графы G1и G2 (рис. 6) изоморфны. Является ли граф G2 планарным?
4. Определите цикломатическое число графа G1 (рис. 6). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
5. Выясните, сколько ребер нужно удалить из графа G1 (рис. 6) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.

Рисунок 6

7.  Вариант 7

1. Для орграфа G0 (рис. 7) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
2. Занумеруйте вершины графа G1 (рис. 7) и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и матрицу инцидентности графа G1, занумеровав его ребра.
3. Покажите, что графы G1и G2 (рис. 7) изоморфны. Является ли граф G2 планарным?
4. Определите цикломатическое число графа G1 (рис. 7). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
5. Выясните, сколько ребер нужно удалить из графа G1 (рис. 7) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.

Рисунок 7

8. Вариант 8

1. Для орграфа G0 (рис. 8) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
2. Дан неорграф G1 (рис. 8). Занумеруйте вершины графа и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и матрицу инцидентности графа G1, занумеровав его ребра.
3. Покажите, что графы G1и G2 (рис. 8) изоморфны. Является ли граф G2 планарным?
4. Определите цикломатическое число графа G1 (рис. 8). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
5. Выясните, сколько ребер нужно удалить из графа G1 (рис. 8) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.

        Рисунок 8

9.  Вариант 9

1. Для орграфа G0 (рис. 9) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
2. Занумеруйте вершины графа G1 (рис. 9) и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и матрицу инцидентности графа G1, занумеровав его ребра.
3. Покажите, что графы G1и G2 (рис. 9) изоморфны. Является ли граф G2 планарным?
4. Определите цикломатическое число графа G1 (рис. 9). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
5. Выясните, сколько ребер нужно удалить из графа G1 (рис. 9) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.

Рисунок 9

10. Вариант 10

1. Для орграфа G0 (рис. 10) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
2. Занумеруйте вершины графа G1 (рис. 10) и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и матрицу инцидентности графа G1, занумеровав его ребра.
3. Покажите, что графы G1и G2 (рис. 10) изоморфны. Является ли граф G2 планарным?
4. Определите цикломатическое число графа G1 (рис. 10). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
5. Выясните, сколько ребер нужно удалить из графа G1 (рис. 10) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.

Рисунок 10

Рекомендуемая литература

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. – 533 с.
2. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика: Учебник для втузов. – М.: Наука. Физматлит, 2000. – 544 с.
3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. – М.: Энергия, 1980. – 814 с.
4. Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2000. – 304 с.
5. С. Г. Гиндикин. Алгебра логики в задачах. — М.: Наука, 1972.
6. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1979. – 271 с.