|
Здравствуйте! Записалась на курс "Практикум по теории графов", не могу просмотреть лекции, пишут, что устарел Адоб Флеш Плеер. Что мне делать? |
Практикум по теории графов: Информация
Автор: Борис Бояршинов | Московский государственный гуманитарный университет имени М.А. Шолохова
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 14 студентам
Уровень:
Для всех
Длительность:
0:03:00
Студентов:
682
Выпускников:
1
Практикум по решению задач по теории графов и связанным с ними алгоритмам.
Даются основные понятия теории графов, решаются оптимизационные задачи на графах, рассказывается об алгоритмах поиска и матричных методах анализа графов.
Специальности: Программист, Математик
Предварительные курсы
Дополнительные курсы
План занятий
Занятие
Заголовок <<
Дата изучения
Логика предикатов. Графы, общие определения
Кванторы всеобщности и существования. Связанные переменные. Область действия квантора. Эквивалентные соотношения в логике предикатов. Чистая логика предикатов и прикладные логики предикатов. Понятия графа. Классификация графов: по наличию ориентирования ребер (неориентированный и ориентированный графы), по наличию кратности ребер (простой граф и мультиграф). Отношение смежности между вершинами, матрица смежности.
Отношение инцидентности между вершинами и ребрами. Степень вершины. Изолированные вершины, висячие вершины. Пустой граф, полный граф.
Оглавление
-
Теория графов. Основные понятия
Матрица смежности, степень вершины.
Подграф и часть графа. Звезда вершины графа. Полный граф. Клика. Максимальный и минимальный (относительно некторого свойства) подграф. Изоморфизм графов.
Неориентированные графы. Путь, цепь, простая цепь, цикл. Связанные вершины. Связный граф. Компоненты связности. Длина пути. Расстояние между вершинами в связном графе. Аксиомы метрики (расстояния).
Оглавление
-
Теория графов. Основные понятия (продолжение)
Радиус графа, центры графа. Эйлеров обход. Задача о кенигсбергских мостах.
Алгоритм построения эйлерова цикла. Задача о гамильтоновом обходе (задача коммивояжера).
Ориентированные графы (орграфы). Ориентированный путь, ориентированный цикл. Достижимость. Виды связности: сильная связность, односторонняя связность, слабая связность.
Компонента сильной связности. Конденсация, граф конденсации.
Ациклический граф. Источники и стоки. Топологическая сортировка.
Оглавление
-
Деревья. Оптимизационные задачи на графах. Задача о кратчайшем пути
Неориентированные деревья. Ориентированные деревья.
Применение деревьев: классификация, представление формул, бинарное дерево поиска.
Оптимизационные задачи на графах. Взвешенные (нагруженные) графы. Задача о кратчайшем пути в неориентированном графе без весов. Ранжирование вершин. Задача о кратчайшем пути в взвешенном графе. Алгоритм Дейкстры.
Оглавление
-
Оптимизационные задачи на графах. Сетевое планирование. Потоки в сетях
Сетевой график. Задача поиска максимальных путей в графе.
Понятия раннего срока и позднего срока. Критический путь. Виды резерва: полный резерв, свободный резерв, независимый резерв. Потоки в сетях. Понятие потока, величина потока. Закон Кирхгофа. Увеличивающаяся цепь.
Оглавление
-
Оптимизационные задачи на графах. Алгоритм поиска увеличивающей цепи
Алгоритм поиска увеличивающей цепи. Разрезы. Пропускная способность разреза.
Оглавление
-
Матричные методы анализа графов. Графы и бинарные отношения
Матричные методы анализа графов. Степень матрицы смежности графа. Сумма степеней матрицы смежности, достижимость и связность. Транзитивное замыкание. Графы и бинарные отношения. Отношения эквивалентности и отношения порядка в терминах графов. Матричные методы анализа мультиграфов. Двудольные графы. Задача о раскраске графа.
Оглавление
-
-
Зарема Батчаева
Борис Никитин
|
Записался на курс "Практикум по теории графов". А лекции по "Дискретной математике" И читает не Бояршинов, а Кузнецов. Почему ? |