Инспектор
Вы можете этот курс.
Приёмы доказательств в теории графов
: Информация
Опубликована: 13.05.2016 | Уровень: для всех | Стоимость: 490.00 руб. | Длительность:
Курс рассчитан на заинтересованного теорией графов слушателя. На примере доказательств ряда важных теорем демонстрируются основные методы получения результатов в данной области.
Необходимые определения и выводы будут приведены непосредственно на лекциях, поэтому предварительных требований к уровню математической подготовки нет.
План занятий
| Занятие | Заголовок << | Дата изучения |
|---|---|---|
Лекция 1 | Введение. Приемы доказательств
Описываются основные приёмы математических доказательств, даются определения теории графов.
Оглавление | - |
Лекция 2 | Основные сведения о графахОглавление | - |
Лекция 3 | Теорема о циклах
Конструктивное доказательство наличия циклов в графах степени не ниже 2.
Оглавление | - |
Лекция 4 | Задача Рамсея
Теория экстремальных графов. Классический пример конструктивного доказательства.
Оглавление | - |
Лекция 5 | A1A2...An-теорема
Полные ориентированные графы. Метод бесконечного спуска.
Оглавление | - |
Лекция 6 | Теорема Холла
Паросочетания в двудольных графах. Доказательство методом формализации на множествах.
Оглавление | - |
Лекция 7 | Теорема Эйлера о многогранниках
Планарные графы. Доказательство по индукции.
Оглавление | - |
Лекция 8 | Теорема Хивуда о 5 красках
Планарная раскраска графа. Конструктивный метод доказательства.
Оглавление | - |
Лекция 9 | Теорема Дирака
Пример конструктивного доказательства с использованием рассуждения от противного.
Оглавление | - |
Лекция 10 | Критерий Гавела-Хакими
Понятие графического разбиения. Метод бесконечного спуска.
Оглавление | - |
Лекция 11 | Теорема Кёнига-Эгервари
Применение теории графов к бинарным матрицам.
Оглавление | - |
30 минут | - |