Дискретная математика, 1 курс ИС
Весенний семестр
Типовой расчет №3
Темы: Суперпозиция, матрицы, связность и компоненты.
Типовой расчет №4
Темы: Комбинаторика, деревья, остовные деревья, эйлеровы и гамильтоновы пути и циклы.
План курса (каждая лекция может занимать 1-2 пары)
- Лекция 1. Теория графов: Определения.
- Граф, смежность, инцидентность. Петли и кратные ребра. Псевдографы и мультиграфы. Изоморфизм графов. Ориентированные графы. Степень вершины ориентированных и неориентированных графов. Лемма о рукопожатиях.Матрица смежности со свойствами. матрица инцидентности со свойствами. Подграф. Надграф. Частичный граф. Дополнение графа. Объединение и пересечение графов.
- Лекция 2. Теория графов: Связность в графах.
- Связность и компоненты связности. Слабая и сильная связность. Компоненты сильной связности. Путь и цепи. Реберно и вершинно простые пути. Лемма о существовании простой цепи при существовании пути в графе. Отношение реберной двусвязности. Мосты. Эквивалентные определения. Лемма о числе компонент после удаления моста. Лемма о цикле и мосте. Отношение вершинной двусвязности. Блоки и точки сочленения. Эквивалентность определений точки сочленения. Леммы про точку сочленения(4шт). Теорема эквивалентных определений блока. Гамильтоновы графы. Поиск гамильтонова цикла. Теоремы Оре, Дирака, Гуйя-Ури.
- Лекция 3. Теория графов: Дерево.
- Дерево. Эквивалентные определения с доказательствами. Граф блоков-точек сочленения. Док-во что он дерево. Граф компонент реберной двусвязности. Док-во что он дерево. Остов графа. Цикломатическое число. Фундаментальная система циклов. Минимальное остовное дерево (MST). Лемма о безопасном ребре. Расстояния в графе.
- Лекция 4. Теория графов: Обходы графов.
- Эйлеровы циклы. Теорема об эквивалентности определений. Теорема о покрытии ребер графа путями. Критерий эйлеровости. Поиск эйлерова пути или цикла. Произвольно вычерчиваемые графы. Теорема о поиске числа путей заданной длины в ориентированном графе через матрицу смежности. Лемма о белых путях.
- Лекция 5. Комбинаторика.
- Основные комбинаторные объекты. Принципы умножения и сложения (принцип включения исключений). Перестановки. Размещения. Сочетания. Основные формулы комбинаторики. Основные теоремы комбинаторики. Лексикографический порядок. Генерация следующего в лексикографическом порядке объекта (сочетания и перестановки). Принцип Дирихле.
Источники