|
произведение графов К(2)*О(4) фактически 4 отдельных графа К(2)? |
Графы и алгоритмы: Информация
Авторы: Владимир Алексеев, Владимир Таланов | Нижегородский государственный университет им. Н.И.Лобачевского
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 36 студентам
Уровень:
Специалист
Длительность:
13:45:00
Студентов:
3521
Выпускников:
119
Качество курса:
4.44 | 4.11
Курс посвящен алгоритмам на графах. Приводятся базовые понятия и факты из теории графов и излагаются некоторые алгоритмы для решения задач на графах.
Основной принцип отбора и организации материала состоял в том, что каждый рассматриваемый пример должен нести определенную идейную нагрузку, знакомить слушателя с одним из важных изобретений или открытий в алгоритмической области. При этом предпочтение отдавалось не самым последним или рекордным алгоритмам, а более простым для понимания и убедительно демонстрирующим ту или иную идею. Для большинства рассматриваемых алгоритмов даются доказательства их правильности (т.е. того, что алгоритм действительно решает поставленную задачу) и оценок трудоемкости. Умение достаточно строго обосновывать алгоритмы и оценивать их трудоемкость является существенной частью квалификации алгоритмиста. Материал первой части может быть использован и в общем курсе дискретной математики.
Специальности: Программист, Математик
Теги: beta, dfs-дерево, алгоритм прима, алгоритмы, двудольный граф, исследования, квазицикл, компонента связности, компоненты, матроид, паросочетание, поиск, поиск в глубину, поиск в ширину, процедуры, сжатие, теория, цвета, шарниров, элементы
Дополнительные курсы
План занятий
Занятие
Заголовок <<
Дата изучения
Лекция 1
1 час 17 минут
Начальные понятия теории графов
Начальные понятия теории графов. Определение графа.
Графы и бинарные отношения. Откуда берутся графы.
Число графов. Смежность, инцидентность, степени.
Некоторые специальные графы. Графы и матрицы.
Взвешенные графы. Изоморфизм. Инварианты. Операции над графами.
Локальные операции. Подграфы. Алгебраические операции.
Оглавление
- Начальные понятия теории графов
- Определение графа
- Графы и бинарные отношения
- Откуда берутся графы
- Число графов
- Смежность, инцидентность, степени
- Некоторые специальные графы
- Графы и матрицы
- Взвешенные графы
- Изоморфизм
- Инварианты
- Операции над графами
- Локальные операции
- Подграфы
- Алгебраические операции
-
Лекция 2
43 минуты
Маршруты, связность, расстояния
Маршруты, пути, циклы. Связность и компоненты. Метрические характеристики
графов. Маршруты и связность в орграфах. Эйлеровы пути и циклы.
-
Лекция 3
1 час 5 минут
Важнейшие классы графов
Деревья. Центр дерева. Корневые деревья. Каркасы. Двудольные графы.
Планарные графы.
-
Лекция 4
38 минут
Поиск в ширину
Поиск в ширину. Процедура поиска в ширину. BFS-дерево и вычисление
расстояний.
-
Лекция 5
43 минуты
Поиск в глубину
Процедура поиска в глубину. DFS-дерево. Глубинная нумерация.
Построение каркаса. Шарниры.
-
Лекция 7
44 минуты
Пространство циклов графа
Пространство подграфов. Квазициклы. Фундаментальные циклы.
Построение базы циклов. Рационализация.
-
Лекция 8
38 минут
Эйлеровы и гамильтоновы циклы
Построение эйлерова цикла. Гамильтоновы пути и циклы.
-
Лекция 9
49 минут
Независимые множества, клики, вершинные покрытия.
Независимые множества, клики, вершинные покрытия . Три задачи.
Стратегия перебора для задачи о независимом множестве.
Эвристики для задачи о независимом множестве. Приближенный
алгоритм для задачи о вершинном покрытии. Перебор максимальных
независимых множеств.
-
Лекция 11
35 минут
Рационализация переборных алгоритмов
Рационализация поиска наибольшего независимого множества. Хордальные
графы. Рационализация алгоритма для задачи о раскраске вершин.
-
Лекция 12
57 минут
Паросочетания
Паросочетания и реберные покрытия. Метод увеличивающих путей.
Паросочетания в двудольных графах. Паросочетания в произвольных графах
(алгоритм Эдмондса).
-
Лекция 13
28 минут
Оптимальные каркасы
Задача об оптимальном каркасе. Алгоритм Прима. Алгоритм
Крускала.
-
Лекция 14
40 минут
Жадные алгоритмы и матроиды
Матроиды. Теорема Радо-Эдмондса. Взвешенные паросочетания.
-
Лекция 15
21 минута
Кратчайшие пути
В этой лекции рассматриваются связные графы с неотрицательными весами
ребер. А также кратчайшие пути, геодезическое дерево и алгоритм Дейкстры.
Оглавление
-
Александр Лаврентьев
|
много инструкций вида if - then - else Например Procedure DFS(a) опишите каким образом следует понимать вложенность инструкций. Как в языке С ? т.е. следующее if (...) then (...) if (...) then (...) else(...)
раскрывается как if (...) then (...) if (...) then (...) else(...) или так : if (...) then { (...) if (...) then (...) else(...) } обьясните пожалуйста.
|