|
В лекции 3 часть номер 2 приведён пример нахождения транзитивного замыкания по матрице смежности. Из примера для обратного транзитивного замыкания видно, что путь для достижения вершины х6 в вершину х3 равен 3, а не 2, как показано в табличном примере. Мне кажется, что в лекции ошибка. |
Введение в теорию графов: Информация
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 55 студентам
Уровень:
Специалист
Длительность:
6:04:00
Студентов:
3264
Выпускников:
849
Качество курса:
4.31 | 3.94
Приводятся начальные сведения о графах, основные понятия и определения, способы представления графов. Рассматриваются основные операции над графами, такие как - объединение, пересечение, кольцевая сумма, удаление вершины, удаление ребра, замыкание и стягивание.
Даются понятия прямых и обратных отображений для орграфов различных порядков, прямого и обратного транзитивного замыкания, приводятся способы нахождения транзитивных замыканий по матрице смежности и обсуждаются вопросы достижимости для орграфов, способы нахождения матриц достижимости и контрдостижимости. Рассматриваются типы графов и подграфов, такие как -полный, симметрический, антисимметрический, двудольный, древовидный, планарный и их возможные комбинации. Дается теорема о двудольности графов. Рассматривается матричный способ нахождения количества путей между любыми вершинами графа, методы разбиения графов на сильно связные подграфы- метод Мальгранжа и матричный метод. Даются понятия веса и длины пути, сведения о орциклах и циклах и их особенностях. Рассматриваются метод Дейкстра нахождения кратчайших путей и методика построения базы для взвешенного графа.
Специальности: Программист, Математик
Теги: алгоритмы, игры, компоненты, контрдостижимость, матрица весов, матрица смежности, метка перехода, обратное транзитивное замыкание, орграф, ориентированное дерево, подграф, стягивание, транзитивное замыкание, элементы
Дополнительные курсы
План занятий
Занятие
Заголовок <<
Дата изучения
Лекция 1
24 минуты
Графы и способы их представления
Приводятся начальные сведения о графах и основные понятия и определения такие как орграф, смешанный граф, дубликат графа дуга, петля, полустепени исхода и захода. Даются возможные способы представления графов. Цель лекции: Дать представление о графах и возможных способах их представления.
Оглавление
-
Лекция 2
19 минут
Операции над графами
Приводятся основные операции над графами такие как объединение, пересечение, кольцевая сумма, удаление вершины, удаление ребра, замыкание и стягивание. Эти операции рассматриваются для представления графов матрицами смежности. Цель лекции: Дать представление об операциях над графами и возможных способах их представления в матричных структурах.
Оглавление
-
Лекция 3
19 минут
Многозначные отображения и транзитивные замыкания
Рассматриваются прямые и обратные отображения для орграфов различных порядков. Даются понятия прямого и обратного транзитивного замыкания и способы нахождения транзитивных замыканий по матрице смежности. Цель лекции: Дать представление о многозначных отображениях и транзитивных замыканиях и способах их нахождения.
Оглавление
-
Лекция 4
24 минуты
Достижимость в графах
Рассматриваются вопросы достижимости для орграфов и способы нахождения матриц достижимости и контрдостижимости. Рассматривается матричный способ нахождения количества путей между любыми вершинами графа, а также нахождение множества вершин, входящих в путь между парой вершин. Цель лекции: Дать представление о достижимости и контрдостижимости и способах их нахождения
Оглавление
-
Лекция 5
23 минуты
Типы графов
Рассматриваются типы графов такие как полный, симметрический, антисимметрический, двудольный, дерево, планарный и их возможные комбинации. Дается теорема о двудольности графов. Цель лекции: Дать представление о типах графов и их свойствах
Оглавление
-
Лекция 6
14 минут
Виды подграфов
Рассматриваются подграфы такие как остовный, порожденный и различные виды подграфов по связности. Цель лекции: Дать представление о видах подграфов и их свойствах.
Оглавление
-
Лекция 7
30 минут
Методы разбиения графа на максимальные сильно связные подграфы
Рассматриваются методы разбиения графов на сильно связные подграфы: метод Мальгранжа и матричный метод. Цель лекции: Дать представление о методах разбиения графов на сильно связные подграфы.
Оглавление
-
Лекция 8
16 минут
Пути и циклы в графах
Рассматриваются взвешенные пути и маршруты в графах. Дается понятие веса и длины пути. Приводятся сведения о орциклах и циклах и их особенностях. Цель лекции: Дать представление о путях и циклах в графах и весе и длине пути.
Оглавление
-
Лекция 9
24 минуты
Алгоритм Дейкстра поиска кратчайших путей в графе
Рассматриваются метод Дейкстра нахождения кратчайших путей. Приводятся сведения о методике построения базы для взвешенного графа. Цель лекции: Дать представление о методе нахождения кратчайших путей во взвешенном графе.
Оглавление
-
Dmitry Schelkov
Вячеслав Коваленко
|
В курсе "Введение в теорию графов" в лекции 4 "Достижимость в графарх" дано выражение для нахождения множетсва вершин, входящих в путь из одной вершины графа в другую и по рис.4.2. показан пример нахождения такого множества для пути из вершины х2 в вершину х4 - это множетсво (х2, х3, х4, х5). По рисунку видно что путь не оптимален и для того, чтобы он проходил через все вершины этого множества, через х4 нужно пройти два раза. Правильно ли я понимаю, что данное определение пути дает не всегда оптимальный путь и что определение оптимально (кратчайшего) пути - отдельная задача? Или в примере ошибка? |