Графы и топология

Читается: 3-4 модуль 3 курса
Пререквизиты: Основные понятия математики; Вычислимость и сложность; Логика
Трудоемкость: 5 кредитов

80 аудиторных часов:

40 часов лекций;

40 часов семинаров.

Формы контроля:

2 контрольных работы,

4 домашних задания.

Формула окончательной оценки: min (10+ 0.3ПК + 0.7ЗК + 0.175 ×Σ ДЗi ),
где ПК – оценка за контрольную в середине курса,
ЗК – оценка за контрольную в конце курса,
ДЗi (i=1, 2, 3, 4) – оценки за зачетные домашние задания.

Преподаватели:

Васильев Виктор Анатольевич
Базовая кафедра Математического института им. В.А. Стеклова РАН: профессор

О курсе:

Освоение геометрических и топологических концепций, используемых в естествознании и в математических моделях социальных процессов.

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

Содержание курса:

Определение графов, их типы, приложения и простейшие свойства. Примеры из практики. Таблицы смежности и таблицы инцидентности.
Связные графы. Порождающее дерево. Эйлеровы пути и гамильтоновы циклы. Мосты Кенигсберга.
Классификация, инварианты и перечисление графов.
Плоские графы, препятствия к планарности, инварианты пространственных графов.
Двудольные графы. Теорема Холла.
Большие и бесконечные графы, их асимптотические свойства.
Метрические пространства: примеры и свойства. Гомеоморфизм. Теоремы об экстремальных и промежуточных значениях.
Фундаментальная группа, классификация двумерных поверхностей, гомологии. Эйлерова характеристика.
Индекс зацепления замкнутых кривых.
Теоремы о неподвижных точках. Теорема о причесывании ежа. Основная теорема алгебры.

Литература:

Оре О. Теория графов. — 2-е изд. — М.: Наука, 1980.
Виро О. Я., Иванов О. А., Харламов В. М., Нецветаев Н. Ю. Элементарная топология. — М: МЦНМО, 2007
С.К.Ландо Графы и топология 2018

4. У.Татт, Теория графов, М., Мир, 1988

5. Ф.Харари, Теория графов, М., Мир, 1973

Материалы курса:

Домашнее задание 1

Домашнее задание 2

Домашнее задание 3

Результаты контрольной 04 апреля 2019

Домашнее задание 4