Файл: С. Д. Данилова С. С. Михайлова УланУдэ 2022дискретнаяматематика.pdf

185 3.2.4 Вершинная и реберная связность графа ................................................................. 105 3.2.5 Контрольные вопросы .............................................................................................. 106
Тема 3.3. Специальные виды графов и раскраска графа ................................................... 108 3.3.1 Эйлеров граф ............................................................................................................. 108 3.3.2 Гамильтонов граф ..................................................................................................... 110 3.3.3 Планарный граф ........................................................................................................ 111 3.3.4 Раскраска графа ......................................................................................................... 114 3.3.5 Контрольные вопросы .............................................................................................. 116
Тема 3.4 Двудольные графы ................................................................................................. 118 3.4.1 Основные определения ............................................................................................ 118 3.4.2 Паросочетания в графе ............................................................................................. 119 3.4.3 Реберное покрытие графа ........................................................................................ 119 3.4.4 Поиск наибольшего паросочетания и задача о назначениях ................................ 120 3.4.5 Контрольные вопросы .............................................................................................. 122
ПРАКТИКУМ ............................................................................................................................ 124 1.
Множества, отношения, функции ................................................................................. 124 1.1 Доказательство теоретико-множественных соотношений ...................................... 124 1.2 Нахождение областей определения, значений, обратного отношения, композиции отношений .......................................................................................................................... 126 1.3 Исследование бинарного отношения на свойства .................................................... 127 1.4 Графическое представление бинарного отношения, исследование его свойств с помощью матрицы ............................................................................................................. 130 1.5 Построение бинарного отношения, обладающего заданными свойствами ........... 134 1.6 Исследование отношения эквивалентности .............................................................. 135 1.7 Достроение бинарного отношения до специальных отношений ............................ 139 1.8 Исследование функций ............................................................................................... 142 2.
Алгебра логики ............................................................................................................... 145 2.1 Представление логической функции различными способами ................................ 145 2.2 Нахождение суперпозиции логических функций ..................................................... 147 2.3 Определение существенных и фиктивных переменных по таблице функции ...... 150 2.4 Определение существенных и фиктивных переменных, преобразование исходной формулы в формулу без фиктивных переменных .......................................................... 152 2.5 Дизъюнктивное разложение функции по переменным, преобразование функции, определение СДНФ и СКНФ ............................................................................................ 154 2.6 Приведение ДНФ к СДНФ, ДНФ к КНФ .................................................................. 157

186 2.7 Доопределение функции до монотонной, линейной и самодвойственной функций
............................................................................................................................................. 159 2.8 Исследование системы функций на полноту ............................................................ 164 3.
Теория графов ................................................................................................................. 169
Исследование графов......................................................................................................... 169
Заключение ................................................................................................................................. 180
Список литературы .................................................................................................................... 181

187
Учебное издание
Соелма Доржигушаевна Данилова
Светлана Сергеевна Михайлова
ДИСКРЕТНАЯ МАТЕМАТИКА
Учебное пособие
Подписано в печать 30.03.2022. Формат 60х84 1/8.
Усл. п. л. 21,85. Тираж 300 экз. Заказ № 66.
Издательство ВСГУТУ.
670013, г. Улан-Удэ, ул. Ключевская, 40 В, строение 1.
Отпечатано в типографии ВСГУТУ.
670013, г. Улан-Удэ, ул. Ключевская, 42 В, строение 9.