ДМ

• 1. Графы. Основные понятия и определения. Матрицы смежностей вершин графов. Матрицы инциденций графов и орграфов. Степени вершин и полустепени исхода и захода. Основные типы графов.
• 2. Теорема о реализуемости графов в трехмерном Евклидовом пространстве. Планарные графы. Связть между количеством вершин, ребер и граней в планарном графе (формула Эйлера)
• 3. Операции на графах (объединение, пересечение, декартово произведение, произведение, композиция графов).
• 4. Изоморфные графы. Алгоритм распознования изоморфизма графов.
• 5. Связные графы. Основные понятия и определения. Компонента связности. Определение компонент связности.
• 6. Графы – деревья. Свойства. Теорема А. Кэли. Построение минимального остовного дерева.
• 7. Транспортная сеть. Основные понятия и определения. Поток в транспортной сети.
• 8. Понятия: маршрут, путь, цепь, простая цепь, цикл, контур, достижимость, радиус, эксцентриситет, диаметр, матрица расстояний. Теорема о числе различных цепей (путей) длины n в графах и орграфах: следствия.
• 9. Теорема о максимальном числе ребер в графе с p вершинами и q компонентами связности.
• 10. Эйлеровы графы. Условия существования цепи и цикла. Гамильтоновы цепи и циклы.
• 11. Нахождение кратчайших путей в графе.
• 12. Множество внутренней устойчивости графа. Число внутренней устойчивости графа. Алгоритмы определения множества внутренней устойчивости.
• 13. Множество внешней устойчивости графа. Число внешней устойчивости графа. Алгоритмы определения множества внешней устойчивости.
• 14. Построение минимальной раскраски вершин.
• 15. Поток минимальной стоимости.
• 16. Комбинаторные конфигурации и их свойства. Перестановки, размещения, сочетания с повторениями и без повторений.
• 17. Принцип Дирихле
• 18. Бином Ньютона. Треугольник Паскаля. Полиномиальная формула.
• 19. Метод включения и исключений. Задача о встречах. Задача о беспорядках.
• 20. Упорядоченное и неупорядоченное разбиения множеств. Числа Стирлинга.
• 21. Разбиение чисел с учетом и без учета порядка.
• 22. Распределение различных предметов по контейнерам.
• 23. Рекуррентные соотношения. Решение рекуррентных соотношений.
• 24. Полиномиальные производящие функции, экспоненциальные производящие функции.
• 25. Полиномиальные производящие функции. Производящие функции числа сочетаний.
• 26. Экспоненциальные производящие функции. Производящие функции числа размещений.
• 27. Производящие функции числа разбиений.
• 28. Метод ветвей и границ. Задача коммивояжера.
• 29. Задача о назначениях.
• 30. Задача о рюкзаке.