Дискретная математика, 1 семестр

Description

Лекции Костенко К. И. ФКТиПМ, КубГУ. 146 стр. отсканированные тетрадные страницы с хорошим почерком.Лекции по вопросам за 1 семестр:Мощность множеств.Отображения. Обратные отображения.Отношения. Представление и операции над отношениями.Свойства отношений на множестве.Отношения эквивалентности.Отношения порядка.Основные комбинаторные правила.Размещения.Сочетания без повторенийСочетания с повторениями.Разбиения множеств на части.Формула включений – исключений.Ф. А. Л. Существенность переменных.Формулы. Эквивалентность формул.Теорема о замене равных. Соотношения эквивалентности.Разложение ф. а. л. по переменным.Минимальные ДНФ.Геометрическая интерпретация минимальных ДНФ.Максимальные конъюнкции и их свойства.Полные системы функций. Теорема редукции.Полиномы Жегалкина.Классы Т0 и Т1.Двойственные функции.Класс S. Лемма о несамодвойственной функции.Класс M.Лемма о немонотонной функции.Класс L. Лемма о нелинейной функции.Критерий полноты в P2.Предполные классы и их свойства.Способы задания графов.Пути и циклы в графах.Транзитивное замыкание графов.Изоморфизм и планарность графов.Непланарность графов K33 и A5.Критерий планарности графов.Деревья и их свойства.Циклы Эйлера. Теорема Эйлера (необходимость).Циклы Эйлера (достаточность).Циклы Гамильтона. Переборный алгоритм.Достаточное условие существования циклов Гамильтона.Суммы графов.Фундаментальное семейство циклов (построение).Фундаментальное семейство циклов (доказательство фундаментальности)Хроматическое число графов. Критерий 2-хроматичности.Оценка значения хроматического числа графа. Критические графы.Ядра графов.Минимальные основные деревья в графах