INTUIT.ru: Учебный курс - Введение в теорию графов

поддержка курса Введение в теорию графов
Авторы: В.С. Князьков, Т.В. Волченская

?	Уровень: для специалистов \|\| Статус: бесплатный \|\| Опубликован: 07.04.2008 Рейтинг: 4.41 \|\| Популярность: 34 \|\| Студентов: 1209/160

Информация о курсе
Приводятся начальные сведения о графах, основные понятия и определения, способы представления графов. Рассматриваются основные операции над графами, такие как - объединение, пересечение, кольцевая сумма, удаление вершины, удаление ребра, замыкание и стягивание.
Даются понятия прямых и обратных отображений для орграфов различных порядков, прямого и обратного транзитивного замыкания, приводятся способы нахождения транзитивных замыканий по матрице смежности и обсуждаются вопросы достижимости для орграфов, способы нахождения матриц достижимости и контрдостижимости. Рассматриваются типы графов и подграфов, такие как -полный, симметрический, антисимметрический, двудольный, древовидный, планарный и их возможные комбинации. Дается теорема о двудольности графов. Рассматривается матричный способ нахождения количества путей между любыми вершинами графа, методы разбиения графов на сильно связные подграфы- метод Мальгранжа и матричный метод. Даются понятия веса и длины пути, сведения о орциклах и циклах и их особенностях. Рассматриваются метод Дейкстра нахождения кратчайших путей и методика построения базы для взвешенного графа.

Дополнительные курсы

Записаться на обучение

Варианты обучения	Цена	Документы
Вы можете оформить официальные документы по программе повышения квалификации.
Самостоятельно	Бесплатно	сертификат	Курс пройден.
ИДО "ИНТУИТ"	2000 руб.	сертификат + официальное удостоверение о повышении квалификации	Программа пройдена.
ВШБИ НИУ ВШЭ	8000 руб.	удостоверение о повышении квалификации государственного образца	Программа пройдена.
Телефон: +7(499) 253-9312, факс: +7(499) 253-9310, e-mail: dpo@intuit.ru, ICQ: Intuit.Ru (632-332-736), Skype: Intuit.Ru

экзамен | экстернат | диплом Лекции

Графы и способы их представления

Приводятся начальные сведения о графах и основные понятия и определения такие как орграф, смешанный граф, дубликат графа дуга, петля, полустепени исхода и захода. Даются возможные способы представления графов. Цель лекции: Дать представление о графах и возможных способах их представления.

Операции над графами

Приводятся основные операции над графами такие как объединение, пересечение, кольцевая сумма, удаление вершины, удаление ребра, замыкание и стягивание. Эти операции рассматриваются для представления графов матрицами смежности. Цель лекции: Дать представление об операциях над графами и возможных способах их представления в матричных структурах.

Многозначные отображения и транзитивные замыкания

Рассматриваются прямые и обратные отображения для орграфов различных порядков. Даются понятия прямого и обратного транзитивного замыкания и способы нахождения транзитивных замыканий по матрице смежности. Цель лекции: Дать представление о многозначных отображениях и транзитивных замыканиях и способах их нахождения.

Достижимость в графах

Рассматриваются вопросы достижимости для орграфов и способы нахождения матриц достижимости и контрдостижимости. Рассматривается матричный способ нахождения количества путей между любыми вершинами графа, а также нахождение множества вершин, входящих в путь между парой вершин. Цель лекции: Дать представление о достижимости и контрдостижимости и способах их нахождения

Типы графов

Рассматриваются типы графов такие как полный, симметрический, антисимметрический, двудольный, дерево, планарный и их возможные комбинации. Дается теорема о двудольности графов. Цель лекции: Дать представление о типах графов и их свойствах

Виды подграфов

Рассматриваются подграфы такие как остовный, порожденный и различные виды подграфов по связности. Цель лекции: Дать представление о видах подграфов и их свойствах.

Методы разбиения графа на максимальные сильно связные подграфы

Рассматриваются методы разбиения графов на сильно связные под-графы: метод Мальгранжа и матричный метод. Цель лекции: Дать представление о методах разбиения графов на сильно связные подграфы.

Пути и циклы в графах

Рассматриваются взвешенные пути и маршруты в графах. Дается понятие веса и длины пути. Приводятся сведения о орциклах и циклах и их особенностях. Цель лекции: Дать представление о путях и циклах в графах и весе и длине пути.

Алгоритм Дейкстра поиска кратчайших путей в графе

Рассматриваются метод Дейкстра нахождения кратчайших путей. Приводятся сведения о методике построения базы для взвешенного графа. Цель лекции: Дать представление о методе нахождения кратчайших путей во взвешенном графе.

Вопросы и Ответы