Инспектор
Вы можете этот курс.
Введение в теорию графов
: Информация
Опубликована: 05.04.2011 | Уровень: для всех | Стоимость: 490.00 руб. | Длительность: 14 дней
Приводятся начальные сведения о графах, основные понятия и определения, способы представления графов. Рассматриваются основные операции над графами, такие как - объединение, пересечение, кольцевая сумма, удаление вершины, удаление ребра, замыкание и стягивание.
Даются понятия прямых и обратных отображений для орграфов различных порядков, прямого и обратного транзитивного замыкания, приводятся способы нахождения транзитивных замыканий по матрице смежности и обсуждаются вопросы достижимости для орграфов, способы нахождения матриц достижимости и контрдостижимости. Рассматриваются типы графов и подграфов, такие как -полный, симметрический, антисимметрический, двудольный, древовидный, планарный и их возможные комбинации. Дается теорема о двудольности графов. Рассматривается матричный способ нахождения количества путей между любыми вершинами графа, методы разбиения графов на сильно связные подграфы- метод Мальгранжа и матричный метод. Даются понятия веса и длины пути, сведения о орциклах и циклах и их особенностях. Рассматриваются метод Дейкстра нахождения кратчайших путей и методика построения базы для взвешенного графа.
План занятий
| Занятие | Заголовок << | Дата изучения |
|---|---|---|
| - | ||
Лекция 124 минуты | Графы и способы их представления
Приводятся начальные сведения о графах и основные понятия и определения такие как орграф, смешанный граф, дубликат графа дуга, петля, полустепени исхода и захода. Даются возможные способы представления графов. Цель лекции: Дать представление о графах и возможных способах их представления.
Оглавление | - |
Тест 127 минут | - | |
Лекция 219 минут | Операции над графами
Приводятся основные операции над графами такие как объединение, пересечение, кольцевая сумма, удаление вершины, удаление ребра, замыкание и стягивание. Эти операции рассматриваются для представления графов матрицами смежности. Цель лекции: Дать представление об операциях над графами и возможных способах их представления в матричных структурах.
Оглавление | - |
Тест 218 минут | - | |
Лекция 319 минут | Многозначные отображения и транзитивные замыкания
Рассматриваются прямые и обратные отображения для орграфов различных порядков. Даются понятия прямого и обратного транзитивного замыкания и способы нахождения транзитивных замыканий по матрице смежности. Цель лекции: Дать представление о многозначных отображениях и транзитивных замыканиях и способах их нахождения.
Оглавление | - |
Тест 318 минут | - | |
Лекция 424 минуты | Достижимость в графах
Рассматриваются вопросы достижимости для орграфов и способы нахождения матриц достижимости и контрдостижимости. Рассматривается матричный способ нахождения количества путей между любыми вершинами графа, а также нахождение множества вершин, входящих в путь между парой вершин. Цель лекции: Дать представление о достижимости и контрдостижимости и способах их нахождения
Оглавление | - |
Тест 418 минут | - | |
Лекция 523 минуты | Типы графов
Рассматриваются типы графов такие как полный, симметрический, антисимметрический, двудольный, дерево, планарный и их возможные комбинации. Дается теорема о двудольности графов. Цель лекции: Дать представление о типах графов и их свойствах
Оглавление | - |
Тест 521 минута | - | |
Лекция 614 минут | Виды подграфов
Рассматриваются подграфы такие как остовный, порожденный и различные виды подграфов по связности. Цель лекции: Дать представление о видах подграфов и их свойствах.
Оглавление | - |
Тест 624 минуты | - | |
Лекция 730 минут | Методы разбиения графа на максимальные сильно связные подграфы
Рассматриваются методы разбиения графов на сильно связные подграфы: метод Мальгранжа и матричный метод. Цель лекции: Дать представление о методах разбиения графов на сильно связные подграфы.
Оглавление | - |
Тест 79 минут | - | |
Лекция 816 минут | Пути и циклы в графах
Рассматриваются взвешенные пути и маршруты в графах. Дается понятие веса и длины пути. Приводятся сведения о орциклах и циклах и их особенностях. Цель лекции: Дать представление о путях и циклах в графах и весе и длине пути.
Оглавление | - |
Тест 821 минута | - | |
Лекция 924 минуты | Алгоритм Дейкстра поиска кратчайших путей в графе
Рассматриваются метод Дейкстра нахождения кратчайших путей. Приводятся сведения о методике построения базы для взвешенного графа. Цель лекции: Дать представление о методе нахождения кратчайших путей во взвешенном графе.
Оглавление | - |
Тест 915 минут | - | |
5 часов | - |