- •Содержание дисциплины "Дискретная математика" введение
- •Входная контрольная работа
- •1Вариант
- •2 Вариант
- •Раздел 1. Основы теории множеств
- •Тема 1.1 Основные понятия теории множеств.
- •Тема 1.2 Операции над множествами.
- •Самостоятельная работа № 1
- •Тема 1.3 Свойства операций.
- •Контрольная работа
- •1 Вариант
- •2 Вариант
- •Раздел 2. Формулы логики.
- •Тема 2.1 Основные логические операции.
- •Тема 2.2 Формулы логики.
- •Самостоятельная работа №2.
- •Тема 2.3 Дизъюнктивная нормальная форма.
- •Различны все члены дизъюнкции;
- •Тема 2.4 Конъюнктивная нормальная форма.
- •Тема 2.5 Равносильные формулы. Свойства.
- •Раздел 3. Булевы функции.
- •Тема 3.1 Понятие булевой функции.
- •Тема 3.2 Совершенная днф. Совершенная кнф. Совершенной дизъюнктивной формой формулы алгебры высказываний (сднф) называется днф, в которой:
- •Различны все члены дизъюнкции;
- •Самостоятельная работа №5.
- •Тема 3.3 Минимальная днф.
- •Тема 3.4 Представление булевой функции в виде минимальной днф.
- •Самостоятельная работа №6. Самостоятельная работа №7
- •Тема 3.5 Полнота множества функций.
- •Тема 3.6 Важнейшие замкнутые классы.
- •Важнейшие замкнутые классы в р2
- •Тема 3.7 Теорема Поста.
- •Примеры использования теоремы Поста.
- •3. Составим критериальную таблицу для другой полной системы функций из р2: {0, 1, x1x2, x1x2}.
- •Контрольная работа
- •Раздел 4. Предикаты и бинарные отношения.
- •Тема 4.1 Понятие предиката. Область определения и область истинности предиката.
- •Тема 4.2 Логические операции над предикатами.
- •Самостоятельная работа №8.
- •Тема 4.3 Кванторные операции над предикатами.
- •2. Квантор существования
- •- «Все люди любят всех людей».
- •- «Существует человек, который кого-то любит» .
- •- «Существует человек, который любит всех людей».
- •Тема 4.4 Понятие предикатной формулы.
- •Тема 4.5 Равносильность предикатов. Исчисление предикатов.
- •Самостоятельная работа №9.
- •Тема 4.6 Бинарные отношения и их свойства.
- •Самостоятельная работа №10. Контрольная работа
- •Раздел 5. Отображения. Подстановки.
- •Тема 5.1 Отображения и их свойства.
- •Самостоятельная работа №11.
- •Тема 5.2 Композиция отображений и обратное отображение.
- •Тема 5.3 Подстановки. Обратные подстановки. Формула количества подстановок.
- •Самостоятельная работа №12. Контрольная работа
- •1 Вариант
- •2 Вариант
- •3 Вариант
- •4 Вариант
- •5 Вариант
- •Раздел 6. Метод математической индукции.
- •Тема 6.1 Принцип метода математической индукции.
- •Раздел 7. Основы теории графов.
- •Тема 7.1 Понятие неориентированный граф. Основные определения.
- •Лабораторная работа № 1.
- •Тема 7.2 Теорема о сумме степеней вершин графа. Полный граф, его свойства.
- •Лабораторная работа № 2.
- •Тема 7.3 Метрические характеристики графа.
- •Лабораторная работа № 3.
- •Тема 7.4 Двудольные и изоморфные графы.
- •Лабораторная работа № 4.
- •Тема 7.5 Эйлеровы и гамильтоновы графы.
- •Лабораторная работа № 5
- •Тема 7.6 Плоские графы.
- •Тема 7.7 Деревья. Код Пруфера.
- •Тема 7.8 Понятие ориентированный граф (орграф).
- •Тема 7.9 Достижимость вершин в орграфе.
- •Раздел 8. Элементы теории алгоритмов.
- •Тема 8.1 Определение класса финитно-поставленных задач.
- •Тема 8.2 Машины Тьюринга.
- •Тема 8.3 Уточнения понятия алгоритм.
- •Итоговая (выходная) контрольная работа.
Тема 7.2 Теорема о сумме степеней вершин графа. Полный граф, его свойства.
Граф Г называется полным, если каждые две его вершины соединены одним и только одним ребром.
А В
С Д - не полный граф
А В
С Д - полный граф
Только для неориентированного графа существует дополнение:
Г
– дополнение
Дополнением графа Г называется новый граф , состоящий из всех тех же вершин, что и граф Г и тех и только тех ребер, которые надо добавить, чтобы граф Г стал полным.
Степенью вершины называется количество ребер ей принадлежащих
В Д
Е
А С
Степень А=1, степень В=2, степень С=2, степень Д=1, степень Е=0
Степень каждой вершины полного графа на единицу меньше числа вершин.
Теорема: Сумма степеней всех вершин графа есть число четное и равное удвоенному количеству ребер
При большом количестве вершин схема теряет свою наглядность и поэтому используют другой способ задания графов в виде матрицы смежностей.
где каждое
М – симметричная на главной диагонали – 0
М (Г)=
Лабораторная работа № 2.
Задание графа матрицей смежности
Цель работы:
Изучить понятия полный граф, дополнение графа.
Рассмотреть способ задания графа с помощью матрицы смежности.
Литература:
"'Графы и их применение". Березина Л.Ю.. М: Просвещение. 1979г.
"Теория графов. Алгоритмический подход", Кристофидес Н.
"Применение теории графов в программировании". Евстигнеев В.А. - М.: Наука. 1985г.
Порядок выполнения работы:
I
Разработать схему алгоритмов основной программы и подпрограмм.
II
Написать и отладить программу на языке Turbo Pascal.
Задача
Граф задан матрицей смежности
М=
Изобразить граф, исходя из внешнего вида данной матрицы.
Краткие теоретические сведения:
Матричный эквивалент графа широко используется в работе с графами на ЭВМ.
Граф называется полным, если каждые две его вершины соединены одним и только одним ребром.
от граф не является
полным
Граф, не являющийся полным, можно преобразовать в полный граф с теми же вершинами, добавив недостающие ребра.
Вершины графа Г и ребра, которые добавлены, также образуют граф, такой граф называется дополнением и обозначается .
Каждой вершине графа можно поставить в соответствие строку и столбец с номером i, причем
{ 1, если
{ 0, если
Тогда матрица называется матрицей смежностей графа Г и обозначается М(Г).
Содержание отчета:
Составление алгоритмов.
Написание программы на языке Turbo Pascal
Отладка программы.
Контрольные вопросы:
Что такое полный граф?
Дайте понятие дополнение графа?
Что такое матрица смежностей графа?
Как составить матрицу смежностей?
Тема 7.3 Метрические характеристики графа.
П усть дан граф:
А3
Как от вершины А1 дойти до А5?
Существуют следующие пути:
<A1,A4>,<A4, A5>
<A1, A2>,<A2, A4>,<A4, A5>
<A1, A3>,<A3, A4>,<A4, A5>
<A1, A4>,<A4, A2>,<A2, A1>,<A1, A3>,<A3, A4>,<A4, A5>
<A1, A4>,<A4,A2>,<A2, A1>,<A1, A4>,<A4, A5> - не является путем, т.к. ребро <A1, A4> встречается дважды.
Путем от вершина А1 до вершины Аn называется такая последовательность ребер, ведущая от А1 до Аn, что любые два соседних ребра имеют общую вершину и ни одного ребра не встречается дважды.
Путь, в котором начальные и конечные вершины совпадают называют циклом.
Путь от вершины А1 до Аn называется простым, если он не проходит ни через одну из вершин графа более одного раза.
Цикл называется простым, если он не проходит ни через одну из вершин графа более одного раза.
Длиной пути (цикла) называется количество ребер его составляющих.
Дан граф. Найти пути от А1 до А6 и определить их длину
<A1,A6>, d=1
<A1, A2>,<A2, A6>, d=2
<A1, A2>,<A2, A5>,<A5, A4>,<A4, A3>,<A3, A2>,<A2, A6>, d=6
< A1, A2>,<A2, A3>,<A3, A4>,<A4, A5>,<A5, A2>,<A2, A6>, d=6
Р асстоянием от вершины А до вершины В называется длина наименьшего пути, если не существует пути от А до В, то считают что расстояние равно бесконечности.
S(A1,A6)=1
S(A1, A7)=∞
В ершины А и В называются связными, если не существует пути связывающего их.
Вершины:
A и D – несвязные
A и Е – несвязные
А и В – связные
А и С – связные