Пояснительная записка

Цель курса - ввести студентов в круг базовых понятий и методов дискретной математики, подготовить их к изучению смежных базовых и специальных курсов, использующих различные методы дискретной математики. Программа соответствует государственному стандарту специальности "Математические методы в экономике". Для освоения курса достаточно знаний по математике на уровне программы средней школы.

В годовом курсе дискретной математики последовательно излагаются: основы теории графов, деревья, сети, специальные разделы теории графов: взвешенные деревья, остовные деревья, раскраски графов, планарные графы, алгоритмы поиска кратчайшего пути, гамильтоновы и эйлеровы циклы, потоки в сетях, паросочетания и покрытия; комбинаторика, производящие функции, метод включения и исключения, логика высказываний и логика первого порядка. В рамках самостоятельной работы студентов предусмотрено изучение некоторых специальных разделов теории графов. Внимание студентов к данному курсу акцентируется обсуждением прикладных экономико-математических проблем методами дискретной математики. Отличительной чертой программы является демонстрация связей различных разделов курса с позиций теории графов, что способствует развитию общесистемного аналитического мышления студентов.

Список вопросов к зачету в весеннем семестре и к экзамену в осеннем семестре соответствует содержанию лекционного материала.

Контрольные мероприятия

В соответствии с реализацией рейтинговой системы оценивания и рекомендациями Учебно-методического управления ДВГУ в программе курса предусмотрены контрольные мероприятия. Во втором семестре контрольные мероприятия состоят из трех контрольных работ и итогового контрольного мероприятия – зачета. В третьем семестре предусмотрено три контрольных работы с итоговым контрольным мероприятием в виде экзамена.

Самостоятельная работа студентов предполагает решение домашних заданий из типовых сборников задач различной степени сложности (пп. 5, 6 списка рекомендуемой литературы).

Содержание дисциплины

ТЕОРИЯ ГРАФОВ

ТЕМА 1. ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ (6 часа)

Основные предпосылки возникновения теории графов: результаты Гамильтона, Кирхгофа, Кэли и Эйлера. Гипотеза о четырех красках. Теория графов в 21-ом веке. Графы ориентированные и неориентированные, мульти и псевдографы, гиперграфы. Маршруты и связность. Степени. Задача Рамсея. Экстремальные графы. Двудольные графы. Графы пересечений. Операции над графами.

ТЕМА 2. ПОДГРАФЫ. БЛОКИ. МОСТЫ. ДЕРЕВЬЯ. МАТРИЦЫ (10 часов)

Матричные представления графов. Матрица смежности. Матрица инциденций. Матрица циклов. Точки сочленения, мосты и блоки. Графы блоков и графы точек сочленения. Описание деревьев. Теорема о числе всех деревьев. Остовные деревья. Теорема о числе всех остовных деревьев. Центры и центроиды в дереве. Деревья блоков и точек сочленения. Независимые циклы и коциклы. Матроиды.

ТЕМА 3. ЗАДАЧИ СОПОСТАВЛЕНИЯ ГРАФОВ, РАСКРАСКИ, ПЛАНАРНОСТЬ (4 часов)

Изоморфизм, гомоморфизм, автоморфизм графов. Алгоритмы сопоставления графов. Теоремы и оценки, относящиеся к хроматическим числам. Точные алгоритмы раскраски. Планарность графов. Алгоритм проверки планарности.

ТЕМА 4. ЗАДАЧИ ПОИСКА ГАМИЛЬТОНОВЫХ И ЭЙЛЕРОВЫХ ЦИКЛОВ. КРАТЧАЙШИЕ ЦЕПИ И ПУТИ. ОСТОВНЫЕ ДЕРЕВЬЯ. ДЕРЕВЬЯ ШТЕЙНЕРА (8 часов)

Эйлеровы циклы: алгоритм построения. Эйлеровы циклы и задача о китайском почтальоне. Гамильтоновы циклы. Алгебраический метод. Простая задача планирования. Задача поиска наикратчайшего гамильтонова цикла. Задача поиска кратчайшей цепи (пути) между парой заданных вершин. Алгоритм Дейстры. Задача поиска между каждой парой вершин. Алгоритм Флойда. Остовные деревья. Алгоритм построения всех остовных деревьев. Алгоритмы построения наикратчайшего остовного дерева. Задача Штейнера и подходы к ее решению.