- •Содержание дисциплины "Дискретная математика" введение
- •Входная контрольная работа
- •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 Уточнения понятия алгоритм.
- •Итоговая (выходная) контрольная работа.
Лабораторная работа № 3.
Полный граф, его свойства. Теорема о сумме степеней вершин графа
Цель работы:
Рассмотреть такую характеристику графа как вершина.
Изучить понятия полный граф.
Дать определение степени вершины.
Научиться определять четность вершины.
Литература:
"Графы и их применение", Березина Л.Ю., М: Просвещение, 1979г.
"Теория графов. Алгоритмический подход", Кристофидес П.
"Применение теории графов в программировании", Евстигнеев В.А. - М.: Наука, 1985г.
Порядок выполнения работы:
I Разработать схему алгоритмов основной программы и подпрограмм.
II Написать и отладить программу на языке Turbo Pascal.
Задание:
Граф задан матрицей смежности
М =
Для графа, заданного своей матрицей смежности, определить степени всех его вершин.
Краткие теоретические сведения:
Граф называется полным, если каждые две его вершины соединены одним и только одним ребром.
Степенью вершины называется число ребер графа, которым принадлежит эта вершина.
Е
Степ. А=1
Степ. В=2
Степ. С=2
Степ. D=l
Стен. Е=0
Вершина называется нечетной, если её степень - число нечетное. Вершима называется четной, если её степень - число четное.
Степень каждой вершины полного графа на единицу меньше числа его вершин.
Теорема о сумме степеней графа
В графе Г - сумма степеней всех его вершин, есть число четное, равное
удвоенному числу его ребер, т.е.
где р - число ребер графа, n- число вершин.
Содержание отчета:
Составление алгоритмов.
Написание программы на языке Turbo Pascal.
Отладка программы.
Контрольные вопросы:
Что такое полный граф?
Дайте понятие степени вершины графа?
Какая вершина графа называется четной?
Какая вершина графа называется нечетной?
Сформулируйте теорему о сумме степеней вершин графа?
Тема 7.4 Двудольные и изоморфные графы.
Графы, которые отличаются только нумерацией вершин, называются изоморфными.
У изоморфных графов матрицы совпадают при применении к ним элементарных алгебраических операций.
На графах изоморфизм возможно представить как функцию: пусть G1(V1 E1 ) и G2(V2 E2) изоморфные графы, тогда существует функция Н-биекция, сохраняющая смежность
H: V1V2 и e1=(vi vj)E1 e2=(h(vi ) h(vj))E2
e2=(vi vj)E2 e1=(h-1 (vi ) h-1(vj))E1
Теорема: изоморфизм графов есть отношение эквивалентности.
Доказательство: 1. рефлексивность- h тождественная функция
2. симметричность- т.к. h: V1V2-биекция, то h-1 :V2V1 тоже биекция
3. транзитивность- h: G1G2 & f: G2G3hf: G1G3
Числовая характеристика, сохраняющаяся при изоморфизме, называется инвариат.
У изоморфных графов все инварианты совпадают, но это не является признаком изоморфизма графов, т.е. при совпадении всех инвариантов мы не можем утверждать об изоморфности данных графов.
Для определения изоморфизма между орграфами G и G можно предложить следующий алгоритм.
Шаг 1. Если число вершин и число дуг, соответственно, совпадают для орграфов, то переходим к шагу 2. Иначе орграфы не изоморфны.
Шаг 2. Для каждой вершины орграфов определяем пары чисел, равные полустепеням захода и исхода. Если каждой такой паре орграфа G найдется аналогичная пара орграфа G , то переходим к шагу 3. Иначе орграфы не изоморфны.
Шаг 3. Если каждой рассмотренной паре чисел для орграфа G соответствует единственная аналогичная пара орграфа G , то есть единственное соответствие между вершинами орграфов из которого можно легко установить соответствие между дугами орграфов, т.е. они будут изоморфными.
Если некоторой паре орграфа G соответствует не одна аналогичная пара орграфа G , то этой вершине орграфа G ставим в соответствие поочередно вершины орграфа G с аналогичной парой чисел.
Из этих сопоставлений находим подстановки для дуг, инцидентным этим вершинам. Для вершин G имеющих только одну аналогичную пару чисел для G , так же находим подстановку для дуг, инцидентным им.
Если из всех, не противоречащих друг другу, полученных подстановок удастся получить полную подстановку для всех дуг орграфов, то они будут изоморфными. Иначе нет.
По подстановкам дуг, вошедшим в полную подстановку дуг, получим подстановку для вершин орграфов.
Двудольным графом называется граф, у которого множество вершин можно разбить на два непересекающихся подмножества так, что ребра соединяют вершины из разных подмножеств.
Паросочетанием в двудольном графе называется любое множество попарно несмежных ребер (у них нет общих вершин).
Паросочетание называется максимальным для данного графа, если оно содержит наибольшее число ребер для всех возможных паросочетаний.
Паросочетание называется совершенным (из множества v в множество w), если число ребер в нем совпадает с числом вершин в подмножестве c.
Для любого подмножества S через ф(S) обозначим те вершины из множества w, которые соединяются ребрами с вершинами подмножества S.
Теорема Холла. Для того, чтобы в двудольном графе существовало совершенное паросочетание, необходимо и достаточно, чтобы для любого подмножества S из множества V выполнялось условие [S] <= [ф(S)].
Венгерский алгоритм нахождения максимального паросочетания.
Дан двудольный граф. Все определения для графа справедливы.
Полным паросочетанием называется паросочетание (ПС), к которому нельзя добавить ни одного ребра графа, не нарушив условие несмежности ребер.
Перебираем все ребра в любом порядке. Все несмежные ребра включаем в паросочетание.
Ребра, входящие в полное паросочетание, будем называть толстыми. Остальные ребра считаем тонкими.
Вершины, которые соединены толстыми ребрами – насыщенные. Остальные – ненасыщенные.
Чередующейся цепью называется цепь, в которой тонкие и толстые ребра чередуются.
Тонкой чередующейся цепью называется чередующаяся цепь, соединяющая 2 ненасыщенные вершины (В ней тонких ребер на 1 больше, чем толстых).
Находим полное паросочетание.
Для этого паросочетания ищем тонкую цепь. Если ее нет, то данное паросочетание максимально и алгоритм закончен.
Если же она существует, то проводим перекраску ребер.
Толстые ребра тонкой цепи делаем тонкими, а тонкие – толстыми.
Получаем новое паросочетание, т.е. из исходного паросочетания удаляем те толстые ребра, которые входили в тонкую цепь и вместо них добавляем тонкие ребра из этой цепи.
Переходим на шаг 2.
Количество ребер в новом паросочетании увеличится на 1.
Максимальное паросочетание (МПС) найдено.
Совершенное ПС – МПС обязательно.
Матрицы смежности двудольных графов.
A(M,N)
[V] = M
[W] = N
Aij = 1, если есть ребро ViWj
Если его нет, то Aij = 0.
Чтобы найти полное паросочетание, нужно найти единицы, которые находятся в разных строках и разных столбцах.
Алгоритм – тот же самый.
При поисках мы можем двигаться по строкам и на углы в 90 градусов.