Методические рекомендации "Дискретная математика"
учебно-методическое пособие по теме
Методические указания составлены для выполнения самостоятельной работы студентов специальности 2203 "Программное обеспечение вычислительной техники и автоматизированных систем". Нижневартовск: Государственное образовательное учреждение среднего профессионального образования «Нижневартовский профессиональный колледж», 2007г.-32с.
Самостоятельная работа студента по предмету «Дискретная математика» выполняется студентами третьего курса в соответствии с учебным планом и программой предмета.
Самостоятельная работа выполняется с целью углубления и закрепления знаний по предмету.
Самостоятельная работа включает в себя контрольные работы по темам.
Скачать:
Вложение | Размер |
---|---|
![]() | 410 КБ |
Предварительный просмотр:
БУ «НИЖНЕВАРТОВСКИЙ ПРОФЕССИОНАЛЬНЫЙ КОЛЛЕДЖ»
Методические указания по выполнению самостоятельных работ
Дисциплина «ДИСКРЕТНАЯ МАТЕМАТИКА»
для специальности 230115 «Программирование в компьютерных системаХ»
(методическое пособие для студентов)
Преподаватель Геталова В.В.
Нижневартовск 2013
Геталова В.В. Дискретная математика
Методические указания составлены для выполнения самостоятельной работы студентов специальности 230115 " Программирование в компьютерных системах ". Нижневартовск: БУ «Нижневартовский профессиональный колледж», 2013г.-32с.
Методические указания рассмотрены на заседании кафедры «Программное обеспечение ВТ и АС»
Протокол №_____ от_____________2013г.
СОДЕРЖАНИЕ
1.ТРЕБОВАНИЯ К ОФОРМЛЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ
Самостоятельная работа студента по предмету «Дискретная математика» выполняется студентами третьего курса в соответствии с учебным планом и программой предмета.
Самостоятельная работа выполняется с целью углубления и закрепления знаний по предмету.
Самостоятельная работа включает в себя контрольные работы по темам.
Номер варианта контрольной работы определяется по следующей таблицы
Перв. буква фам. | Посл. цифра по списку. | Вар. зад. | Перв. буква фам. | Посл. цифра по списку. | Вар. зад. | Перв. буква фам. | Посл. цифра по списку. | Вар. зад. |
А | 0 | 10 | Б | 1 | 4 | В | 2 | 7 |
Г | 1 | 1 | Д | 2 | 5 | Е | 3 | 8 |
Ж | 2 | 2 | 3 | 3 | 6 | И | 4 | 9 |
К | 3 | 3 | Л | 4 | 7 | М | 5 | 10 |
Н | 4 | 4 | О | 5 | 8 | П | 6 | 1 |
Р | 5 | 5 | С | 6 | 9 | Т | 7 | 2 |
У | 6 | б | Ф | 7 | 10 | X | 8 | 3 |
Ц | 7 | 7 | Ч | 8 | 1 | Ш | 9 | 4 |
Щ | 8 | 8 | Э | 9 | 2 | Ю | 0 | 5 |
Я | 9 | 9 | 0 | 3 | 1 | 6 |
Например: Ваша фамилия Петров и по списку № 15, следовательно номер вашего варианта 10
Перечень тем самостоятельных работ студентов
Наименование | Тема СРС | Часы |
Раздел 1. Теория множеств | Контрольная работа № 1 | |
1.1. Множества и операции над ними | Задача 1 | 2 |
1.2. Бинарные отношения | Задача 2 | 3 |
1.3. Реляционная алгебра | Задача 3 | 3 |
1.4. Комбинаторика | Задача 4, 5 | 3 |
Раздел 2. Основы теории множеств | Контрольная работа № 2 | |
2.1. Ориентированные графы | Задача 1 | 2 |
2.2. Неориентированные графы | Задача 2 | 3 |
2.3. Планарные графы | Задача 3 | 2 |
2.4. Связность графов | Задача 4 | 2 |
2.5. Графы без циклов | Задача 5 | 2 |
ИТОГО | 22 |
Контрольная работа должна соответствовать варианту и содержать: титульный лист, содержание, условие задачи и ее решение, список используемой литературы. Сроки сдачи указываются преподавателем.
Размер страницы: размеры полей: верхнее – 2.0 см; нижнее – 2 см; левое – 3,0 см; правое - 1,5 см; переплет – 0 см. Расстояние от края до верхнего колонтитула – 2.5 см; до нижнего – 2 см.
Шрифт—Times New Roman, 14пт;
Интервал —1,5пт
Нумерация страниц — по правому краю, внизу.
В тексте запрещается использовать, выделение жирным шрифтом, курсивом.
Для нумерации списка используется следующий стиль:
- и т.д.
Для маркированного списка используется следующий символ: —
- КОНТРОЛЬНАЯ РАБОТА № 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:
A1 | A2 | A3 |
a | b | c |
a | c | d |
b | d | a |
d | a | b |
S:
B1 | B2 | B3 |
a | d | b |
a | c | d |
b | d | a |
Записать обозначения операций и выполнить их:
- селекция отношения R по условию “ A2 > b”;
- проекция на список (3,1) объединения отношений R и S.
Задача 5
Шесть старушек вышли во двор поболтать. На скамейке помещаются только четыре из них. Сколькими способами их можно рассадить на скамейке?
Задача 6
На веревке сушатся четыре белых полотенца и три желтых. Сколькими способами их можно развесить, если полотенца одного цвета не отличаются друг от друга?
Задача 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:
A1 | A2 | A3 |
a | b | c |
a | c | d |
b | d | a |
d | a | b |
S:
B1 | B2 |
a | d |
a | c |
c | d |
Записать обозначения операций реляционной алгебры и выполнить их:
- проекция отношения R на список (1,3);
- соединение отношений R и S по условию “A2 = B1”.
Задача 5
На подоконнике стоят четыре горшка с цветами. Сколькими способами их можно расставить на подоконнике?
Задача 6
Шесть мячей раскладывают по двум коробкам. Сколькими способами это можно сделать? (Считается, что вместимость коробки достаточна для всех мячей).
- Вариант 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:
A1 | A2 | A3 |
a | b | d |
b | c | d |
b | a | d |
a | b | c |
S:
B1 | B2 |
b | c |
a | c |
a | d |
Записать обозначения операций реляционной алгебры и выполнить их:
- проекция отношения R на список (1,3);
- соединение отношений R и S по условию “A1>B1”.
Задача 5
Пятнадцать студентов пришли на занятия, но в аудитории оказалось только 13 стульев. Сколькими способами они могут выбрать двоих, чтобы отправить их на поиски стульев?
Задача 6
Сколькими способами можно расставить семь катеров у двух причалов, если у каждого причала могут поместиться все семь? Способы различаются лишь количеством катеров у каждого причала.
Задача 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:
A1 | A2 | A3 |
c | e | f |
a | b | d |
d | e | f |
c | d | c |
S:
B1 | B2 |
f | d |
e | c |
Записать обозначения операций реляционной алгебры и выполнить их:
- проекция отношения R на список (2,3);
- соединение отношений R и S по условию “A3=B1”.
Задача 5
Семеро студентов пошли вместо лекции в кино. Но оказалось, что в кассе осталось только три билета. Сколькими способами они могут выбрать этих троих?
Задача 6
Сколькими способами можно рассадить шесть кустов пионов на трех клумбах, если на каждой клумбе могут поместиться все шесть?
Задача 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:
A1 | A2 | A3 |
a | b | c |
b | a | c |
a | c | b |
a | d | b |
S:
B1 | B2 | B3 |
a | c | b |
a | d | e |
a | d | b |
Записать обозначения операций реляционной алгебры и выполнить их:
- селекция отношения R по условию “A2>А3”;
- проекция на список (3,1) объединения отношений R и S.
Задача 5
Семеро рыбаков отправились на остров на двух лодках. Ночью одна из лодок уплыла. Сколькими способами они могут отправить троих в погоню за уплывшей лодкой?
Задача 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:
A1 | A2 |
s | t |
u | v |
x | z |
S:
B1 | B2 | B3 |
s | u | t |
u | v | t |
z | s | x |
Записать обозначения операций реляционной алгебры и выполнить их:
- селекция отношения S по условию “B1>B3”;
- соединение отношений R и S по условию “A1=B2”.
Задача 5
В библиотеку поступило девять новых различных книг. Сколькими способами читатель может выбрать три из них?
Задача 6
В елочной гирлянде восемь лампочек: две желтых, три красных, три синих. Сколькими способами их можно расположить в гирлянде?
Задача 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:
A1 | A2 | A3 |
a | e | d |
a | b | c |
d | a | b |
S:
B1 | B2 | B3 |
a | b | c |
b | e | d |
d | e | c |
Записать обозначения операций реляционной алгебры и выполнить их:
- селекция отношения R по условию “A1>A2”;
- проекция на список (2,3) объединения отношений R и S.
Задача 5
В магазине продается восемь типов шляп. Сколькими способами дама может выбрать себе три разных шляпы?
Задача 6
В библиотеке на полке стоит три одинаковых учебника по математике и четыре разных по программированию. Сколькими способами их можно расставить на полке?
Задача 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:
A1 | A2 |
x | y |
y | z |
x | t |
S:
B1 | B2 | B3 |
u | t | v |
x | z | y |
y | z | v |
Записать обозначения операций реляционной алгебры и выполнить их:
- проекция на список (2,1) отношения S;
- соединение отношений R и S по условию “A1>B2”.
Задача 5
В сессию студент сдает пять экзаменов. Сколько возможных результатов сессии (экзаменационной оценкой может быть 2, 3, 4, 5)?
Задача 6
Сколькими способами 12 книг можно расставить по трем полкам, если на каждой полке могут поместиться все книги? Способы различаются лишь количеством книг на полках.
Задача 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:
A1 | A2 | A3 |
a | d | e |
d | c | b |
b | d | a |
S:
B1 | B2 |
d | e |
d | c |
a | c |
Записать обозначения операций реляционной алгебры и выполнить их:
- проекция на список (2,1) отношения R;
- соединение отношений R и S по условию “A1≥B1”.
Задача 5
На столе лежат восемь яблок. Сколькими способами можно выбрать два из них?
Задача 6
Требуется покрасить шесть гаражей, стоящих в один ряд. На каждый из гаражей расходуется одна банки краски. Сколькими способами можно покрасить гаражи, если есть две банки красной краски, три зеленой и одна синей?
Задача 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:
A1 | A2 | A3 |
a | b | c |
a | c | d |
b | c | d |
S:
B1 | B2 |
b | e |
b | c |
d | c |
Записать обозначения операций реляционной алгебры и выполнить их:
- проекция на список (3,2) отношения R;
- соединение отношений R и S по условию “A1=B1”.
Задача 5
Сколькими способами 8 человек можно рассадить на лавке (всех в один ряд)?
Задача 6
Восемь туристов отправились в путь на двух лодках, в меньшей из которых могли поместиться не более четверых, а в большей – не более шестерых человек. Сколькими различными способами они могут распределиться в разные лодки? (Распределения считаются различными, если хотя бы один турист окажется в другой лодке).
- Вариант 1
- Для орграфа G0 (рис. 1) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
- Занумеруйте вершины графа G1 (рис. 1) и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и матрицу инцидентности графа G1, занумеровав его ребра.
- Покажите, что графы G1и G2 (рис. 1) изоморфны. Планарен ли граф G2?
- Определите цикломатическое число графа G1 (рис. 1). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
- Выясните, сколько ребер нужно удалить из графа G1 (рис. 1) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.
Рисунок 1
- Для орграфа G0 (рис. 2) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
- Занумеруйте вершины графа G1 (рис. 2) и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и инцидентности графа G1, занумеровав его ребра.
- Покажите, что графы G1и G2 (рис. 2) изоморфны. Планарен ли граф G2?
- Определите цикломатическое число графа G1 (рис. 2). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
- Выясните, сколько ребер нужно удалить из графа G1 (рис. 2) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.
Рисунок 2
- Для орграфа G0 (рис. 3) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
- Дан неорграф G1 (рис. 3). Занумеруйте вершины графа и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и матрицу инцидентности графа G1, занумеровав его ребра.
- Покажите, что графы G1и G2 (рис. 3) изоморфны. Является ли граф G2 планарным?
- Определите цикломатическое число графа G1 (рис. 3). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
- Выясните, сколько ребер нужно удалить из графа G1 (рис. 3) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.
Рисунок 3
- Для орграфа G0 (рис. 4) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
- Занумеруйте вершины графа G1 (рис. 4) и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и матрицу инцидентности графа G1, занумеровав его ребра.
- Покажите, что графы G1и G2 (рис. 4) изоморфны. Является ли граф G2 планарным?
- Определите цикломатическое число графа G1 (рис. 4). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
- Выясните, сколько ребер нужно удалить из графа G1 (рис. 4) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.
Рисунок 4
- Для орграфа G0 (рис. 5) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
- Занумеруйте вершины графа G1 (рис. 5) и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и матрицу инцидентности графа G1, занумеровав его ребра.
- Покажите, что графы G1и G2 (рис. 5) изоморфны. Является ли граф G2 планарным?
- Определите цикломатическое число графа G1 (рис. 5). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
- Выясните, сколько ребер нужно удалить из графа G1 (рис. 5) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.
- Вариант 6
- Для орграфа G0 (рис. 6) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
- Занумеруйте вершины графа G1 (рис. 6) и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и матрицу инцидентности графа G1, занумеровав его ребра.
- Покажите, что графы G1и G2 (рис. 6) изоморфны. Является ли граф G2 планарным?
- Определите цикломатическое число графа G1 (рис. 6). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
- Выясните, сколько ребер нужно удалить из графа G1 (рис. 6) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.
Рисунок 6
- Для орграфа G0 (рис. 7) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
- Занумеруйте вершины графа G1 (рис. 7) и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и матрицу инцидентности графа G1, занумеровав его ребра.
- Покажите, что графы G1и G2 (рис. 7) изоморфны. Является ли граф G2 планарным?
- Определите цикломатическое число графа G1 (рис. 7). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
- Выясните, сколько ребер нужно удалить из графа G1 (рис. 7) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.
- Вариант 8
- Для орграфа G0 (рис. 8) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
- Дан неорграф G1 (рис. 8). Занумеруйте вершины графа и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и матрицу инцидентности графа G1, занумеровав его ребра.
- Покажите, что графы G1и G2 (рис. 8) изоморфны. Является ли граф G2 планарным?
- Определите цикломатическое число графа G1 (рис. 8). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
- Выясните, сколько ребер нужно удалить из графа G1 (рис. 8) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.
Рисунок 8
- Для орграфа G0 (рис. 9) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
- Занумеруйте вершины графа G1 (рис. 9) и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и матрицу инцидентности графа G1, занумеровав его ребра.
- Покажите, что графы G1и G2 (рис. 9) изоморфны. Является ли граф G2 планарным?
- Определите цикломатическое число графа G1 (рис. 9). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
- Выясните, сколько ребер нужно удалить из графа G1 (рис. 9) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.
- Вариант 10
- Для орграфа G0 (рис. 10) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
- Занумеруйте вершины графа G1 (рис. 10) и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G1. Запишите матрицу смежности и матрицу инцидентности графа G1, занумеровав его ребра.
- Покажите, что графы G1и G2 (рис. 10) изоморфны. Является ли граф G2 планарным?
- Определите цикломатическое число графа G1 (рис. 10). Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
- Выясните, сколько ребер нужно удалить из графа G1 (рис. 10) при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.
Рисунок 10
- Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. – 533 с.
- Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика: Учебник для втузов. – М.: Наука. Физматлит, 2000. – 544 с.
- Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. – М.: Энергия, 1980. – 814 с.
- Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2000. – 304 с.
- С. Г. Гиндикин. Алгебра логики в задачах. — М.: Наука, 1972.
- Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1979. – 271 с.
По теме: методические разработки, презентации и конспекты
Методические рекомендации по проведению внеклассного занятия по математике по теме: "Считай! Смекай! Угадывай!"
Цели занятия: Развитие интереса к математике. Расширение кругозора учащихся. Развитие логического мышления и речи ...

МЕТОДИЧЕСКАЯ РАЗРАБОТКА ОТКРЫТОГО УРОКА ПО ПРЕДМЕТУ “МАТЕМАТИКА” ПО ТЕМЕ: НАХОЖДЕНИЕ НАИБОЛЬШЕГО И НАИМЕНЬШЕГО ЗНАЧЕНИЯ ФУНКЦИИ Автор-составитель: преподаватель математики Козырева Татьяна Александровна Краснодар, 2014г.
Разработка урока составлена в соответствии с программой по математике ( по учебнику А. Н. Колмогоров и др. „ Алгебра и начало анализа ” 10 – 11кл. Урок по теме: „ Нахождение наибольшего и наимень...

МЕТОДИЧЕСКАЯ РАЗРАБОТКА ОТКРЫТОГО УРОКА ПО ПРЕДМЕТУ “МАТЕМАТИКА” ПО ТЕМЕ: НАХОЖДЕНИЕ НАИБОЛЬШЕГО И НАИМЕНЬШЕГО ЗНАЧЕНИЯ ФУНКЦИИ Автор-составитель: преподаватель математики Козырева Татьяна Александровна Краснодар, 2014г.
Разработка урока составлена в соответствии с программой по математике ( по учебнику А. Н. Колмогоров и др. „ Алгебра и начало анализа ” 10 – 11кл. Урок по теме: „ Нахождение наибольшего и наимень...

Педагогическая периодика как средство культурно-просветительской деятельности советской эпохи. Обзор методического журнала "Математика в школе"
Обзор методического журнала "Математика в школе". Выпуск №1, 1953 г....

Книги для учителя математики. Проблема нехватки качественных учебно-методических материалов для учителей математики.
Описывается проблема нехватки качественных учебно-методических материалов для учителей математики и ее содержание....

Методическая разработка внеклассного мероприятия по математике "Вкусная математика"
разработка внеклассного мероприятия...

Методическая разработка внеклассного мероприятия по математике "Занимательная математика" для обучающихся первого курса колледжа
Данная методическая разработка составлена для проведения внеклассного мероприятия по математике на 1-2 курсе в среднем профессиональном учебном заведении. Мероприятие проводится в форме игры, состоит ...