Автор: Нина Костюкова | Новосибирский Государственный Университет
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
 
Уровень:
Для всех
Длительность:
11:03:00
Студентов:
2767
Выпускников:
431
Качество курса:
4.21 | 3.83
В курсе излагаются основные понятия теории графов. Описаны методы решения задач.
Материал организован так, что знакомство с графами происходит в процессе решения самых разнообразных задач, в формулировках условий которых не упоминаются графы. Для решения их требуется увидеть возможность перевести условие на язык графов, решить задачу внутри теории графов, интерпретировать получение решение в исходных терминах. Если в начале курса рассматриваются приложения частного характера, иллюстрирующие теорию графов и ее связь с жизнью, то вторая половина книги посвящена прикладным разделам теории графов, имеющим практическое значение в экономике и управлении.
Специальности: Программист, Математик
ISBN: 978-5-9556-0069-7
 

План занятий

Занятие
Заголовок <<
Дата изучения
Лекция 1
37 минут
Основные понятия теории графов
Определение графа. Определение орграфа. Полный граф. Полный ориентированный граф. Двудольный граф. Степень вершины. Связность графа. Задачи, приводящие к графам
-
Лекция 2
33 минуты
Некоторые определения теории графов
Определения и примеры. Удаление ребер, мосты. Деревья. Перечисление деревьев.
-
Лекция 3
27 минут
Представления о планарном графе
Плоский граф. Гомеоморфные графы. Формула Эйлера. Триангулированный граф. Задачи.
-
Лекция 4
36 минут
Эйлеровы графы
Эйлеровы графы. Лабиринты. Геометрическая постановка задачи о лабиринтах. Решение задачи о лабиринтах.
-
Лекция 5
24 минуты
Гамильтоновы графы
Гамильтоновы графы. Теорема Дирака.
-
Лекция 6
28 минут
Бесконечные графы
Бесконечные графы. Краткий обзор свойств бесконечных эйлеровых графов.
-
Лекция 7
39 минут
Графы с цветными ребрами
Реберная раскраска. Задачи на графы с цветными ребрами и вытекающие из них свойства. Задача о несцепленных треугольниках с одноцветными сторонами.
-
Лекция 8
25 минут
Раскрашивание графов
Хроматическое число. Гипотеза о четырех красках. Раскрашивание карт.
-
Лекция 9
39 минут
Орграфы
Определения. Эйлеровы и гамильтоновы орграфы. Турниры.
-
Лекция 10
40 минут
Цепи Маркова
Еще раз об ориентированных графах. Задачи на круговые бескомпромиссные турниры. Цепи Маркова.
-
Лекция 11
31 минута
О деревьях
Представления деревьев. Представление с помощью матрицы смежности. Представление с помощью списков смежности. Представление с помощью списка ребер и кода Прюфера. Алгоритм построения кода Прюфера. Алгоритм раскодирования. Уровневые коды корневых деревьев. Перечисление и подсчет деревьев. Непомеченные деревья. Ориентированные деревья. Каркасы в неориентированном графе. Каркасы в ориентированных графах.
-
Лекция 12
20 минут
Каркасы и изоморфизм деревьев
Каркас неориентированного графа. Нахождение каркасов в графе. Алгоритм Краскала. Изоморфизм деревьев.
-
Лекция 13
10 минут
Деревья, вероятность и генетика
Поиск кратчайшего пути. Вероятность и генетика.
-
Лекция 14
40 минут
Сетевое планирование и управление
Введение. Сетевой график. Правила построения сетевого графика. Анализ сетевой модели. Определение критического пути. Определение полного резерва времени ненапряженного пути. Формирование временных оценок работ.
-
Лекция 15
22 минуты
Паросочетания и свадьбы
Паросочетания и свадьбы. Теорема Холла о свадьбах. Приложение теоремы Холла. Латинские квадраты.
-
Лекция 16
33 минуты
Теория трансверсалей
Теория трансверсалей. Приложение теории трансверсалей.
-
1 час 40 минут
-
Владислав Нагорный
Владислав Нагорный

Подскажите, пожалуйста, планируете ли вы возобновление программ высшего образования? Если да, есть ли какие-то примерные сроки?

Спасибо!

Лариса Парфенова
Лариса Парфенова

1) Можно ли экстерном получить второе высшее образование "Программная инженерия" ?

2) Трудоустраиваете ли Вы выпускников?

3) Можно ли с Вашим дипломом поступить в аспирантуру?

 

Петр Гончар-Зайкин
Петр Гончар-Зайкин
Россия
Светлана Ведяева
Светлана Ведяева
Россия, Саратов