Программа дисциплины «теория графов»



Скачать 133.88 Kb.
Дата24.11.2012
Размер133.88 Kb.
ТипПрограмма дисциплины


Министерство образования Республики Беларусь

Белорусский государственный университет

Механико-математический факультет

Кафедра уравнений математической физики


УТВЕРЖДАЮ

Проректор по учебной работе

профессор В.В. Самохвал

________________________

Рег.№ __________________

«____» ____________ 2007 г.
Базовая учебная программа дисциплины

«ТЕОРИЯ ГРАФОВ»


для студентов специальности 1-31 03 01 «Математика»

Минск

2007

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Теория графов является одним из наиболее бурно развивающихся разделов математики. Это вызвано запросами стремительно расширяющейся области приложений. В теоретико-графовых терминах формулируется большое число задач, связанных с дискретными объектами. Такие задачи возникают при проектировании интегральных схем и схем управления, при исследовании автоматов, логических цепей, блок-схем программ, в экономике и статистике, теории расписаний и дискретной оптимизации. Таким образом, теория графов стала существенной частью математического аппарата кибернетики, языком дискретной математики. В значительной степени через теорию графов происходит ныне проникновение математических методов в науку и технику.

Материал курса ставит своей целью дать в руки студентов орудие, применимое как к наукам о поведении (кибернетика, теория информации, теория систем, теория игр), так и к теории множеств, теории матриц, теории групп и другим дисциплинам.

Основной задачей этого учебного курса является обучение студентов основам теории графов. Вместе с тем большое внимание уделяется вопросам применения теории графов к решению прикладных задач и, в связи с этим, — построению эффективных алгоритмов.

В эту программу не включены еще три раздела, обязательных для курса по теории графов: “Планарность”, “Раскраски”, “Ориентированные графы”. Они вынесены в отдельный спецкурс “Избранные главы теории графов”.

"ТЕОРИЯ ГРАФОВ"

Цель курса "Теория графов": обучить студентов основам теории графов и познакомить с ее приложениями.

Тематический план курса "Теория графов"


темы

Количество часов

Содержание курса

Лекции

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

1

2

3

Раздел 1. Введение

10

10

1.1. Исторический обзор. Первоначальные понятия теории графов. Изоморфизм. Подграфы.

2

2

1.2. Маршруты, цепи, циклы. Связные компоненты. Связь между числами вершин, ребер и компонент графа.

2

3

1.3. Способы задания графов. Матрицы, ассоциированные с графом. Метрические инварианты. Минимаксные задачи размещения.

2

2

1.4. Двудольные графы. Теорема Кёнига. Распознавание двудольности. Волновой алгоритм.

4

3

Раздел 2. Деревья

6

6

2.1. Эквивалентные определения дерева. Центр дерева, алгоритм Жордана.

2

3

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

4

3

Раздел 3. Независимость и покрытия

10

10

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

4

4

3.2. Вершинные и реберные покрытия. Паросочетания, их связь с покрытиями. Паросочетания в двудольных графах, теорема Холла. Связь между числами паросочетания и вершинного покрытия в двудольном графе. Теорема Кенига о бинарных матрицах.

6

6

Раздел 4. Обходы графов

8

8

4.1. Эйлеровы циклы. Критерий эйлеровости. Алгоритм Флёри.

4

4

4.2. Гамильтоновы циклы. Достаточные условия гамильтоновости.

4

4

Раздел 5. Связность

6

4

5.1. Числа вершинной и реберной связности. Дерево блоков и точек сочленения. k-Компоненты. Процедура построения произвольного 2-связного графа.

4

3

5.2. Сепараторы. Теорема Менгера.

2

1

Раздел 6. Циклы и разрезы в графе

8

5

6.1. Поле F2 из двух элементов, его особая роль в комбинаторике. Булеан B(X) конечного m-элементного множества X как линейное пространство над F2. Системы линейных однородных уравнений над F2.

2

1

6.2. Особенности матрицы инцидентности I(G) графа G = (VE), рассматриваемой как матрица над F2. Булеан B(E) как линейное пространство над F2, его размерность, базис. Координаты вектора и столбцы матрицы инцидентности.

2

1

6.3. Пространство циклов C(G), его размерность, базис. Связь пространства C(G) с пространством решений однородной системы линейных уравнений I(GX = 0. Фундаментальная система циклов.

2

2

6.4. Пространство разрезов C(G), аналогия с пространством циклов. Фундаментальная система разрезов. Матрица фундаментальных циклов M(G) и разрезов M(G), их одновременное вычисление, исходя из матрицы I(G).

2

1

Раздел 7. Графические последовательности

12

7

7.1. Степенная последовательность графа. Графическая последовательность, ее реализации. Критерий графичности Гавела-Хакими.

2

1

7.2. Алгоритм построения реализации графической последовательности. Реализации с предписанными свойствами.

2

1

7.3. Расщепляемые графы. Критерий расщепляемости.

2

2

7.4. Пороговые графы, их распознавание и структура.

4

2

7.5. Степенное множество графа.

2

1

Раздел 8. Асимптотические свойства графов

4

2

8.1. Асимптотические свойства “Почти все графы имеют свойство P”, “Почти нет графов со свойством P”. Примеры таких свойств.

4

2

Раздел 9. Заключение.

4



9.1. Проблемы теории графов.

4




Всего аудиторных часов

68

52

ИТОГО:

120


Раздел 1. Введение
Исторический обзор. Первоначальные понятия теории графов. Изоморфизм. Подграфы. Маршруты, цепи, циклы. Связные компоненты. Связь между числами вершин, ребер и компонент графа. Способы задания графов. Матрицы, ассоциированные с графом. Метрические инварианты. Минимаксные задачи размещения. Двудольные графы. Теорема Кёнига. Распознавание двудольности. Волновой алгоритм.
Раздел 2. Деревья
Эквивалентные определения дерева. Центр дерева, алгоритм Жордана. Остов графа. Теорема Кирхгофа о числе остовов. Нахождение остова минимального веса, алгоритм Краскала. Остовы и матрица инцидентности.
Раздел 3. Независимость и покрытия
Вершинная независимость. Оценки числа независимости. О сложности алгоритмических задач. Априорные оценки погрешностей алгоритмов. Задача “Независимое множество вершин графа” – формулировка, сложность. Быстрый алгоритм с априорной оценкой погрешности. Клика. Граф клик. Модульное произведение. Связь проблем “Клика”, “Изоморфная вложимость”, “Изоморфизм”. Вершинные и реберные покрытия. Паросочетания, их связь с покрытиями. Паросочетания в двудольных графах, теорема Холла. Связь между числами паросочетания и вершинного покрытия в двудольном графе. Теорема Кенига о бинарных матрицах.
Раздел 4. Обходы графов
Эйлеровы циклы. Критерий эйлеровости. Алгоритм Флёри. Гамильтоновы циклы. Достаточные условия гамильтоновости.
Раздел 5. Связность
Числа вершинной и реберной связности. Дерево блоков и точек сочленения. k-Компоненты. Процедура построения произвольного 2-связного графа. Сепараторы. Теорема Менгера.
Раздел 6. Циклы и разрезы в графе
Поле F2 из двух элементов, его особая роль в комбинаторике. Булеан B(X) конечного m-элементного множества X как линейное пространство над F2. Системы линейных однородных уравнений над F2. Особенности матрицы инцидентности I(G) графа G = (VE), рассматриваемой как матрица над F2. Булеан B(E) как линейное пространство над F2, его размерность, базис. Координаты вектора и столбцы матрицы инцидентности. Пространство циклов C(G), его размерность, базис. Связь пространства C(G) с пространством решений однородной системы линейных уравнений I(GX = 0. Фундаментальная система циклов. Пространство разрезов C(G), аналогия с пространством циклов. Фундаментальная система разрезов. Матрица фундаментальных циклов M(G) и разрезов M(G), их одновременное вычисление, исходя из матрицы I(G).
Раздел 7. Графические последовательности
Степенная последовательность графа. Графическая последовательность, ее реализации. Критерий графичности Гавела-Хакими. Алгоритм построения реализации графической последовательности. Реализации с предписанными свойствами. Расщепляемые графы. Критерий расщепляемости. Пороговые графы, их распознавание и структура. Степенное множество графа.
Раздел 8. Асимптотические свойства графов
Асимптотические свойства “Почти все графы имеют свойство P”, “Почти нет графов со свойством P”. Примеры таких свойств.
Раздел 9. Заключение.
Проблемы теории графов.

ЛИТЕРАТУРА

по курсу "Теория графов"

Основная:

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

  1. Берж К. Теория графов и ее применение. — М.: ИЛ, 1962.

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

  3. Зыков А.А. Основы теории графов. — М.: Наука, 1987.

  4. Оре О. Теория графов. — М.: Наука, 1980.

  5. Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984.

  6. Татт У. Теория графов. — М.: Мир, 1988.



Автор:
Профессор кафедры уравнений математической физики, доктор физ.-мат.наук

Р. И. Тышкевич,

доцент кафедры уравнений математической физики

Ю.М. Метельский

Рецензент:

Зав. кафедрой дискретной математики и алгоритмики факультета прикладной математики

профессор, доктор физ.-мат.наук В. М. Котов
Одобрена на заседании кафедры

уравнений математической физики

протокол № 7 от 06 июня 2007 г.

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

протокол № 7 от 20 июня 2007 г.

Ответственный за выпуск

вед. лаборант кафедры уравнений математической физики Л.Н. Кулибаба







Похожие:

Программа дисциплины «теория графов» iconПрограмма наименование дисциплины: Теория конечных графов
Цели и задачи дисциплины: Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение...
Программа дисциплины «теория графов» iconРабочая программа дисциплины (модуля) Теория графов Направление подготовки
Целями освоения дисциплины (модуля) «Теория графов» являются получение теоретических знаний по основам теории графов
Программа дисциплины «теория графов» iconПрограмма наименование дисциплины: Теория конечных графов
Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение методов теории конечных...
Программа дисциплины «теория графов» iconПрограмма наименование дисциплины: Теория графов Рекомендуется для направления (ий) подготовки (специальности (ей))
Курс «Теория графов» является дисциплиной по выбору в бакалаврской программе направления «Прикладная математика и информатика». Курс...
Программа дисциплины «теория графов» iconПрограмма дисциплины «избранные главы теории графов»
...
Программа дисциплины «теория графов» iconРабочая программа дисциплины "Теория конечных графов и ее приложения" Направление подготовки 010300. 62 «фиит»
Графы ориентированные и неориентированные. Изоморфизм графов. Маршруты, цепи, циклы. Деревья. Помеченные графы. Плоские и планарные...
Программа дисциплины «теория графов» iconПрограмма вступительного экзамена в аспирантуру по специальностям 05. 13. 05 "Элементы и устройства вычислительной техники и систем управления"
Комбинаторика и Комбинаторные объекты. Методы комбинаторного анализа. Теория графов. Основные понятия и определения. Способы задания...
Программа дисциплины «теория графов» iconТеория графов и ее приложения
Основные понятия. Графы неориентированные и ориентированные. Способы задания графов. Матрицы смежности и инцидентности графа. Понятие...
Программа дисциплины «теория графов» iconНаучная работа по теме: 1 глава 1 4 теория графов 4 Эйлеровы графы 7 Задача о мостах, Леонард Эйлер и теория графов 8
Как это сделать? Я стала искать пути решения, и оказалось, что это можно сделать с помощью графов. Раньше понятием «граф» я встречалась...
Программа дисциплины «теория графов» iconДисциплины "Теория конечных графов и ее приложения"
Цели и задачи дисциплины: формирование навыков логического мышления; ознакомление с основами теоретических знаний по графам и их...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org