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



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


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

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

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

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


УТВЕРЖДАЮ

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

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

________________________

Рег.№ __________________

«____» ____________ 2007 г.
Базовая учебная программа дисциплины
«ИЗБРАННЫЕ ГЛАВЫ ТЕОРИИ ГРАФОВ»

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

Минск

2007

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

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

Основной задачей этой дисциплины является ознакомление студентов с теми разделами теории графов, которые либо недостаточно полно представлены в основном курсе по теории графов, либо вообще не вошли в этот курс. К числу таких разделов относятся “Раскраски графов”, “Планарные графы” и “Ориентированные графы”.
"ИЗБРАННЫЕ ГЛАВЫ ТЕОРИИ ГРАФОВ"

Цель спецкурса "Избранные главы теории графов": обучить студентов основам из трех избранных разделов теории графов (не вошедших в основной курс) и ознакомить с их приложениями.
Тематический план спецкурса "Избранные главы теории графов"


темы

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

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

Лекции

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

1

2

3

Раздел 1.
Раскраски графов


10

9

1.1. Определение вершинной раскраски, хроматического числа графа. Применение вершинной раскраски. Алгоритм последовательной раскраски.

2

2

1.2. Оценки хроматического числа через плотность и число независимости графа. Теорема Зыкова. Оценки хроматического числа через максимальную степень вершин графа, а также через минимальные степени его порожденных подграфов. Теорема Брукса.

3

2

1.3. Оценки хроматического числа через число вершин, ребер графа. Хроматический полином графа. Общий вид хроматического полинома. Хроматический полином дерева.

2

2

1.4. Определение реберной раскраски, хроматический индекс. Теорема Визинга. Хроматический индекс полного графа и двудольного графа.

3

3

Раздел 2. Планарные графы

4

4

2.1. Плоский граф, его элементы. Теорема Эйлера. Свойства планарных графов.

2

2

2.2. Критерий планарности Понтрягина-Куратовского (без доказательства). Свойства плоской триангуляции.

2

2

Раздел 3. Ориентированные графы

3

4

3.1. Элементы ориентированного графа. Сильносвязный, одностороннесвязный и слабосвязный орграфы. Сильносвязная компонента. Конденсация орграфа и ее свойство.

1

2

3.2. База и ядро орграфа.

2

2

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

17

17

ИТОГО:

34

Раздел 1. Раскраски графов
Определение вершинной раскраски, хроматического числа графа. Применение вершинной раскраски. Алгоритм последовательной раскраски. Оценки хроматического числа через плотность и число независимости графа. Теорема Зыкова. Оценки хроматического числа через максимальную степень вершин графа, а также через минимальные степени его порожденных подграфов. Теорема Брукса. Оценки хроматического числа через число вершин, ребер графа. Хроматический полином графа. Общий вид хроматического полинома. Хроматический полином дерева. Определение реберной раскраски, хроматический индекс. Теорема Визинга. Хроматический индекс полного графа и двудольного графа.
Раздел 2. Планарные графы
Плоский граф, его элементы. Теорема Эйлера. Свойства планарных графов. Критерий планарности Понтрягина-Куратовского (без доказательства). Плоская триангуляция, ее свойства.
Раздел 3. Ориентированные графы
Элементы ориентированного графа. Сильносвязный, одностороннесвязный и слабосвязный орграфы. Сильносвязная компонента. Конденсация орграфа и ее свойство. База и ядро орграфа.

ЛИТЕРАТУРА

по курсу "Избранные главы теории графов"

Основная:

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

  1. Handbook of Combinatorics (ed. Graham R.L., Groetschel M., Lovasz L.). Amsterdam: Elsevier, 1995.

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

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

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


Автор:

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

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


Рецензент:

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

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


Одобрена на заседании кафедры

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

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

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

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

Ответственный за выпуск:
доцент Метельский Ю.М.,

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








Похожие:

Программа дисциплины «избранные главы теории графов» iconПрограмма наименование дисциплины: Теория конечных графов
Цели и задачи дисциплины: Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение...
Программа дисциплины «избранные главы теории графов» iconПрограмма наименование дисциплины: Теория конечных графов
Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение методов теории конечных...
Программа дисциплины «избранные главы теории графов» iconРабочая учебная программа По дисциплине: Избранные главы теории вероятностей По направлению: 010900 «Прикладные математика и физика»
Цель дисциплины – освоение студентами избранных глав теории вероятностей, в частности, теории массового обслуживания и теории случайных...
Программа дисциплины «избранные главы теории графов» iconРабочая учебная программа По дисциплине: Избранные главы теории кодирования По направлению: 010900 «Прикладные математика и физика»
Цель дисциплины – освоение студентами избранных глав современной теории информации и современной теории кодирования
Программа дисциплины «избранные главы теории графов» iconРабочая программа дисциплины (модуля) Теория графов Направление подготовки
Целями освоения дисциплины (модуля) «Теория графов» являются получение теоретических знаний по основам теории графов
Программа дисциплины «избранные главы теории графов» iconПрограмма по дисциплине Избранные главы алгебры и теории чисел для специальности
Рабочая программа составлена на основании
Программа дисциплины «избранные главы теории графов» iconМетодические указания к самостоятельным и семинарским занятиям по теории графов Москва 2006
Предназначены для решения задач по теории графов как при самостоятельном изучении теории графов, так и при решении задач на семинарах...
Программа дисциплины «избранные главы теории графов» iconПрограмма элективного курса Элементы теории графов и комбинаторики Учитель
Курс “Элементы теории графов и комбинаторики” является дополнительным к стандартному курсу математики 5 класса для образовательных...
Программа дисциплины «избранные главы теории графов» iconПрограмма дисциплины «теория графов»
Таким образом, теория графов стала существенной частью математического аппарата кибернетики, языком дискретной математики. В значительной...
Программа дисциплины «избранные главы теории графов» iconЛекции по теории графов читаются либо в виде отдельного курса например, в юургу он читается как «Комбинаторика и теория графов»
Потребности программирования определяют развитие «стыка» информатики и математики (алгебры, математической логики, теории игр, общей...
Разместите кнопку на своём сайте:
ru.convdocs.org


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