Магистратура МИСИС (личная):
Графы и их применение
: Информация
Опубликован: 25.07.2006 | Уровень: для всех | Доступ: свободно | ВУЗ: Новосибирский Государственный Университет
В курсе излагаются основные понятия теории графов. Описаны методы решения задач.
Материал организован так, что знакомство с графами происходит в процессе решения самых разнообразных задач, в формулировках условий которых не упоминаются графы. Для решения их требуется увидеть возможность перевести условие на язык графов, решить задачу внутри теории графов, интерпретировать получение решение в исходных терминах. Если в начале курса рассматриваются приложения частного характера, иллюстрирующие теорию графов и ее связь с жизнью, то вторая половина книги посвящена прикладным разделам теории графов, имеющим практическое значение в экономике и управлении.
Цель: Курс предназначен для лиц, желающих расширить свои знания и умения в области программирования.
Дополнительные курсы |
План занятий
| Занятие | Заголовок << | Дата изучения |
|---|---|---|
| - | ||
Лекция 137 минут | Основные понятия теории графов
Определение графа. Определение орграфа. Полный граф. Полный
ориентированный граф. Двудольный граф. Степень вершины. Связность графа.
Задачи, приводящие к графам
Оглавление | - |
Тест 19 минут | - | |
Лекция 233 минуты | Некоторые определения теории графов
Определения и примеры. Удаление ребер, мосты. Деревья.
Перечисление деревьев.
Оглавление | - |
Тест 29 минут | - | |
Лекция 327 минут | Представления о планарном графе
Плоский граф. Гомеоморфные графы. Формула Эйлера.
Триангулированный граф. Задачи.
Оглавление | - |
Тест 39 минут | - | |
Лекция 436 минут | Эйлеровы графы
Эйлеровы графы. Лабиринты. Геометрическая постановка
задачи о лабиринтах. Решение задачи о лабиринтах.
Оглавление | - |
Тест 49 минут | - | |
Лекция 524 минуты | Гамильтоновы графы
Гамильтоновы графы. Теорема Дирака.
Оглавление | - |
Тест 59 минут | - | |
Лекция 628 минут | Бесконечные графы
Бесконечные графы. Краткий обзор свойств бесконечных эйлеровых
графов.
Оглавление | - |
Тест 69 минут | - | |
Лекция 739 минут | Графы с цветными ребрами
Реберная раскраска. Задачи на графы с цветными ребрами и вытекающие
из них свойства. Задача о несцепленных треугольниках с одноцветными
сторонами.
Оглавление | - |
Тест 79 минут | - | |
Лекция 825 минут | Раскрашивание графов
Хроматическое число. Гипотеза о четырех красках. Раскрашивание
карт.
Оглавление | - |
Тест 89 минут | - | |
Лекция 939 минут | Орграфы
Определения. Эйлеровы и гамильтоновы орграфы. Турниры.
Оглавление | - |
Тест 99 минут | - | |
Лекция 1040 минут | Цепи Маркова
Еще раз об ориентированных графах. Задачи на круговые
бескомпромиссные турниры. Цепи Маркова.
Оглавление | - |
Тест 109 минут | - | |
Лекция 1131 минута | О деревьях
Представления деревьев. Представление с помощью матрицы смежности.
Представление с помощью списков смежности. Представление с помощью списка
ребер и кода Прюфера. Алгоритм построения кода Прюфера. Алгоритм
раскодирования. Уровневые коды корневых деревьев. Перечисление и подсчет
деревьев. Непомеченные деревья. Ориентированные деревья. Каркасы
в неориентированном графе. Каркасы в ориентированных графах.
Оглавление | - |
Тест 119 минут | - | |
Лекция 1220 минут | Каркасы и изоморфизм деревьев
Каркас неориентированного графа. Нахождение каркасов в графе.
Алгоритм Краскала. Изоморфизм деревьев.
Оглавление | - |
Тест 129 минут | - | |
Лекция 1310 минут | Деревья, вероятность и генетика
Поиск кратчайшего пути. Вероятность и генетика.
Оглавление | - |
Тест 139 минут | - | |
Лекция 1440 минут | Сетевое планирование и управление
Введение. Сетевой график. Правила построения сетевого графика.
Анализ сетевой модели. Определение критического пути. Определение полного резерва
времени ненапряженного пути. Формирование временных оценок работ.
Оглавление | - |
Тест 149 минут | - | |
Лекция 1522 минуты | Паросочетания и свадьбы
Паросочетания и свадьбы. Теорема Холла о свадьбах. Приложение
теоремы Холла. Латинские
квадраты.
Оглавление | - |
Тест 159 минут | - | |
Лекция 1633 минуты | Теория трансверсалей
Теория трансверсалей. Приложение теории трансверсалей.
Оглавление | - |
Тест 169 минут | - | |
Лекция 1726 минут | Потоки в сетяхОглавление | - |
Тест 179 минут | - | |
5 часов | - |
