Лекций : 34 Практических : 0 Лабораторных : 34 tg. 6 Теория графов I ects: 4


Скачать 21.96 Kb.
НазваниеЛекций : 34 Практических : 0 Лабораторных : 34 tg. 6 Теория графов I ects: 4
Дата публикации14.04.2014
Размер21.96 Kb.
ТипЛитература
referatdb.ru > Математика > Литература

Лекций: 34

Практических: 0

Лабораторных: 34

TG.6

Теория графов I


ECTS: 4

Лектор

Доктор физико-математических наук, профессор кафедры уравнений математической физики Тышкевич Р.И.

Цель курса

Обучение студентов основам теории графов и ознакомление с ее приложениями.

Образовательная цель: Изложение ряда базовых разделов теории графов и их приложений, обучение решению задач из соответствующих разделов.

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

^ Базовые курсы

Необходимо иметь понятие об общей теории отображений, начальных сведениях теории множеств и линейной алгебры.

Содержание

Исторический обзор. Первоначальные понятия теории графов. Изоморфизм. Подграфы. Маршруты, цепи, циклы. Связные компоненты. Связь между числами вершин, ребер и компонент графа. Способы задания графов. Матрицы, ассоциированные с графом. Метрические инварианты. Минимаксные задачи размещения. Двудольные графы. Теорема Кёнига. Распознавание двудольности. Волновой алгоритм.

Эквивалентные определения дерева. Центр дерева, алгоритм Жордана. Остов графа. Теорема Кирхгофа о числе остовов. Нахождение остова минимального веса, алгоритм Краскала. Остовы и матрица инцидентности.

Вершинная независимость. Оценки числа независимости. О сложности алгоритмических задач. Априорные оценки погрешностей алгоритмов. Задача “Независимое множество вершин графа” – формулировка, сложность. Быстрый алгоритм с априорной оценкой погрешности. Клика. Граф клик. Модульное произведение. Связь проблем “Клика”, “Изоморфная вложимость”, “Изоморфизм”. Вершинные и реберные покрытия. Паросочетания, их связь с покрытиями. Паросочетания в двудольных графах, теорема Холла. Связь между числами паросочетания и вершинного покрытия в двудольном графе. Теорема Кенига о бинарных матрицах.

Эйлеровы циклы. Критерий эйлеровости. Алгоритм Флёри. Гамильтоновы циклы. Достаточные условия гамильтоновости.

^ Методика преподавания

Лекции и лабораторные занятия

Литература

1.  Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука. 1990.

2.  Дистель Р. Теория графов. Новосибирск: Изд-во Института математики. 2002.

Экзаменационная методика

Зачёт и экзамен

Рекомендуется

для студентов третьего курса механико-математического факультета

Примечания




Похожие рефераты:

Лекций : 34 Практических : 0 Лабораторных : 17 tg. 7 Теория графов II ects: 3
Доктор физико-математических наук, профессор кафедры уравнений математической физики Тышкевич Р. И
Лекций: 34 Практических: 34 Лабораторных: 0 tfkv. 5 Теория функций комплексного переменного ects
Кандидат физико-математических наук, доцент кафедры теории функций Жаровина Т. Н
Лекций: 34 Практических: 18 Лабораторных: 0 tu. 9 Теория автоматического управления ects
Кандидат физико-математических наук, cтарший преподаватель кафедры математических методов теории управления Зеленяк Д. М
Лекций: 34 Практических: 18 Лабораторных: 0 taс. 9 Теория автоматического управления ects
Кандидат физико-математических наук, cтарший преподаватель кафедры математических методов теории управления Зеленяк Д. М
Лекций: 18 Практических: 16 Лабораторных: 0 end. 9 Модели плоскости Лобачевского ects: 2 Лектор
Повышение уровня профессиональной компетентности в решении проблем, возникающих в процессе преподавания математики
Лекций: 20 Практических: 14 Лабораторных: 0 tfkv. 5 Теория функций комплексного переменного ects
Изучение свойств аналитических функций комплексного переменного, теории вычетов и ее приложений; теории аналитического продолжения;...
Лекций: 20 Практических: 16 Лабораторных 0 7 семестр Механика контактного взаимодействия ects
Кравчук А. С. доктор физико-математических наук, профессор кафедры теоретической и прикладной механики механико-математического факультета...
Лекций: 34 Практических: 34 Лабораторных : 0 przi. 8 Практикум по...
Практикум по информатике. А. В. Могилев, Н. И. Пак, Е. К. Хеннер. М, «Ауадемия», 2001
Лекций: 20 Практических: 14 Лабораторных 0 Основы математического...
Журавков М. А. доктор физико-математических наук, профессор кафедры теоретической и прикладной механики механико-математического...
Программа вступительного экзамена для поступающих в магистратуру...
К окончанию курса магистрантов должны иметь набор учебно-практических материалов (конспекты лекций, практических и лабораторных занятий,...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
referatdb.ru
referatdb.ru
Рефераты ДатаБаза