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

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

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

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

УТВЕРЖДАЮ

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

                                                               профессор

________________________

          Рег.№ __________________

  «____» ____________ 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.

Дополнительная:

Handbook of Combinatorics (ed. Graham R. L., Groetschel M., Lovasz L.). Amsterdam: Elsevier, 1995. Зыков теории графов. М.: Наука, 1987. рафы, сети и алгоритмы. М.:Мир, 1984. еория графов. М.:Мир, 1988.

Автор:

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

Рецензент:

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

,

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

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

протокол № 7 от 01.01.01 г.

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

протокол № 7 от 01.01.01 г.

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

доцент ,

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