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