Methods and Algorithms of Graph Theory

2020/2021

Academic Year

RUS

Instruction in Russian

3

ECTS credits

Delivered at:

Department of Economics

Course type:

Elective course

When:

2 year, 4 module

Instructor

Litvinova, Viktoria

Программа дисциплины

Аннотация

Настоящая дисциплина относится к блоку дисциплин по выбору. Дисциплина реализуется в формате смешанного обучения и представляет собой on-line курс Методы и Алгоритмы Теории Графов на платформе Coursera от автора МФТИ и читается преподавателями Купавским А. и Райгородским А. Ссылка на курс: https://www.coursera.org/learn/teoriya-grafov. Изучение данной дисциплины базируется на следующих дисциплинах: Математический анализ. Для освоения учебной дисциплины студент должен владеть следующими знаниями и компетенциями: Способен учиться, приобретать новые знания, умения, в том числе в области, отличной от профессиональной; Способен работать с информацией: находить, оценивать и использовать информацию из различных источников, необходимую для решения научных и профессиональных задач (в том числе на основе системного подхода); Способен собрать и проанализировать исходные данные, необходимые для расчета экономических и социально-экономических показателей, характеризующих деятельность хозяйствующих субъектов. Основные положения дисциплины могут быть использованы в дальнейшем при изучении дисциплин: Прикладная эконометрика панельных и качественных данных, Экономическая политика, Подготовка выпускной квалификационной работы.

Цель освоения дисциплины

• Изучение теории графов и разделов теории алгоритмов на графах.
• Ознакомление с математическими моделями явлений в экономике, использующими графы, позволяющие студенту ориентироваться в прикладных вопросах, требующих использования математического аппарата

Планируемые результаты обучения

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

Содержание учебной дисциплины

• Введение. Базовые понятия теории графов
  На первом видео лекции онлайн-курса введено понятие графа, обсуждаются разные виды графов, объяснено, как использовать граф как модель структуры интернета. Обсуждены первые понятия теории графов, такие как маршруты в графах, степень вершины, связность, деревья.
• Эквивалентные определения дерева. Планарные графы
  Даны четыре определения дерева и понятие правильной раскраски графа, сформулиро-вана теорема о четырех красках, а также критерий Куратовского о том, как определить, можно ли нарисовать данный граф на плоскости без пересечений ребер. В последней части лекции обсуждена формула Эйлера для планарных графов и некоторые из её множественных следствий.
• Формула Кэли. Унициклические графы. Эйлеровы циклы
  Дан способперечислить все деревья, леса и унициклические графы. Решена задача о Кёнигсбергских мостах
• Гамильтоновы циклы
  Гамильтоновы циклы Лекция продолжает обсуждать циклы, проходящие через весь граф. На этот раз мы по-говорим про циклы, проходящие через все вершины графа. Даны достаточные условия нали-чия такого цикла. Обсуждены такие характеристики графа, как независимое число и k-связность.
• Паросочетания. Теорема Холла и Кенига.
  На лекции введено понятие паросочетания и сформулирована достаточное и необходимое условие наличия паросочетания. Введены базовые понятия экстремальной теории графов и дана теорема Турана и аналог теоремы Турана для графов на плоскости.
• Теория Рамсея.
  Введены первые понятия теории Рамсея на примере задачи о знакомстве среди шести чело-век. Введены оценки для чисел Рамсея.

Элементы контроля

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

Промежуточная аттестация

• Промежуточная аттестация (4 модуль)
  0.7 * Онлайн-курс + 0.3 * Письменный экзамен

Список литературы

Рекомендуемая основная литература

• Reinhard Diestel, Alexander Schrijver, & Paul D. Seymour. (2007). Graph Theory. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.24E6A4B5

Рекомендуемая дополнительная литература

• Kumar, R., & Pattnaik, P. K. (2018). Graph Theory. Bengaluru: Laxmi Publications Pvt Ltd. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=2228702