РАБОЧАЯ  ПРОГРАММА

дисциплины

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

 

Направление подготовки дипломированного специалиста

 

Направление:     657100 – Прикладная математика

 Специальность:  073000 – Прикладная математика

 

1. Цели и задачи дисциплины.

 

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

Задачи курса заключаются в том, чтобы студент привык к понятию «графа» в самом общем математическом смысле и соответственно умел применять это понятие в самых разных прикладных областях.

 

2. Требования к уровню освоения содержания дисциплины.

 

            Студенты должны усвоить:

·        абстрактные определения графов и взаимодействие методики теории графов с различными абстрактными понятиями (такими, как «бинарные отношения» и др.);

·        основные результаты, полученные в теории графов для конечных графов;

·        уметь решать конкретные прикладные задачи с помощью теории графов.

 

3. Объем дисциплины и виды учебной работы.

 

Вид учебной работы

Всего часов

Семестры

Общая трудоемкость дисциплины

98

 

 

5

 

Аудиторные занятия

68

 

 

5

 

Лекции

34

 

 

5

 

Практические занятия (ПЗ)

34

 

 

5

 

Семинары (С)

 

 

 

 

 

Лабораторные работы (ЛР)

 

 

 

 

 

и (или) другие виды аудиторных занятий

 

 

 

 

 

Самостоятельная работа

30

 

 

5

 

Курсовой проект (работа)

 

 

 

 

 

Расчетно-графические работы

 

 

 

 

 

Реферат

 

 

 

 

 

и (или) другие виды самостоятельной работы

 

 

 

 

 

Вид итогового контроля (зачет, экзамен)

экзамен

 

 

экзамен

 

 


 

4. Содержание дисциплины.

4.1. Разделы дисциплины и виды занятий

 

№ п/п

Раздел дисциплины

Лекции

ИЗ

(или С)

ЛР

1

Абстрактное понятие графа

2

2

 

2

Взаимодействие теории графов с другими разделами математики

2

2

 

3

Основные теоремы конечных графов

10

10

 

4

Применение теории графов

3

3

 

 

4.2. Содержание разделов дисциплины

 

·        Абстрактное понятие графа.

Историческое развитие понятия графа. Бинарные отношения. Сведения из теории групп. Аксиоматическое задание объектов и ситуаций.

 

·        Взаимодействие с другими разделами математики.

Интерпретация в виде графов бинарных отношений. Связь понятий теории графов с элементами теории групп. Примеры использования аксиоматики в теории графов.

 

·        Основные теоремы теории конечных графов.

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

 

·        Применение теории графов.

Графы в задачах принятия решений. Графы в экспертных системах. Графы в математических моделях.

 

5. Лабораторный практикум не предусмотрен.


6. Учебно-методическое обеспечение дисциплины.

6.1. Рекомендуемая литература:

1.      Е.В. Гливенко, Б.М. Наймарк. Дискретная математика. Курс лекций. Москва, Нефть и газ, 2001, с.20.

2.      О.Оре. Теория графов. Москва, Мир.

 

6.2. Средства обеспечения освоения дисциплины. Не предусмотрено

 

7. Материально-техническое обеспечение дисциплины. Не предусмотрено

 

            Программа составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования по направлению подготовки 657100 – прикладная математика, специальность: 073000 –прикладная математика

 

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

 

Программу составил д.т.н., профессор кафедры ПМ и КМ Гливенко Е.В.