Теория графов и комбинаторика

01. Теоретико-множественное введение
02. Определение графа. Вершины и ребра. Графическая интерпретация графа. Смежность и инцидентность. Локальная степень. Подграф. Полный граф. Матрицы смежностей и инциденций. Изоморфизм графов
03. Путь в графе и связные компоненты графа. Цепи, простые цепи, циклы, простые циклы. Операции удаления вершины, удаления ребра, подразбиения ребра. Дерево и его особенности
04. Эйлеров цикл и эйлеров граф. Условия существования эйлерова цикла. Задача о разбиении графа на минимальное число цепей
05. Гамильтонов цикл и гамильтонов граф. Условия Дирака, Оре и Поша, гарантирующие существование в графе гамильтонова цикла
06. Формулировка теоремы Менгера (вершинный и реберный варианты), теорема Холла о системах различных представителей и теорема Кёнига о независимых клетках в матрице
07. Определение паросочений в графе и их разновидностей. Двудольные графы и алгоритм выбора наибольшего паросочетания в двудольном графе. Решение задачи о назначениях на узкие места
08. Цепи и антицепи в частично-упорядоченном множестве. Теорема Дилворта. Алгоритм разбиения частично-упорядоченного множества на минимальное число цепей
09. Планарные и плоские графы. Формулировки теоремы Понтрягина-Куратовского и теоремы Эйлера о соотношении чисел граней, ребер и вершин плоского графа
10. Раскраска графа. Формулировка теоремы о пяти красках. Хроматическое число и алгоритм Зыкова вычисления хроматического многочлена графа
11. Взвешенный граф. Кратчайшие пути во взвешенном графе и алгоритм Форда постро-ения кратчайших маршрутов
12. Остов в графе и алгоритм Краскала поиска остова минимального веса во взвешенном графе
13. Ориентированный граф и его графическая интерпретация. Локальные степени. Мат-рица смежностей. Ориентированные пути и связность в ориентированном графе
14. Сети и потоки в сетях. Стационарные потоки. Алгоритм Форда-Фалкерсона поиска максимального стационарного потока
15. Перестановки, размещения и сочетания. Бином Ньютона и иллюстративные примеры
16. Метод включения-исключения перечисления элементов множества, не обладающих заданными свойствами. Задача о беспорядках и задача о встречах
17. Формальные степенные ряды и действия над ними. Производящие функции последова-тельностей
18. Линейные рекуррентные соотношения и их решение с помощью поизводящих функций. Числа Фиббоначчи
© 2011-2024 Контрольные работы по математике и другим предметам!