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

Вид материала

Программа дисциплины

Подобный материал:

• Задача является np-полной для кубических планарных графов, реберных графов, ориентированных, 39.45kb.
• Программа вступительного экзамена в аспирантуру по специальностям 05. 13. 05 - "Элементы, 88.59kb.
• Рабочая программа дисциплины «теория графов и прикладная комбинаторика», 70.21kb.
• 1. Элементы теории графов Введение в теорию графов: основные понятия и определения., 32.17kb.
• Программа дисциплины Комбинаторные алгоритмы Семестры, 18.74kb.
• Билеты по Дискретной математике «Теория Графов», 12.79kb.
• «Теория графов», 114.81kb.
• Учебной дисциплины «Теория графов» для направления 010100. 62 «Математика», 34.23kb.
• Спецкурс «Теория графов» пм 4 курс История возникновения и развития теории графов., 13.97kb.
• Задание графов соответствием 9 > Матричное представление графов 10 Вопросы применения, 230.14kb.

Направление 010100 Математика


Профиль Дискретная математика и приложения


Степень бакалавр


Программа

дисциплины Теория графов


Семестр 5


Цель дисциплины:

Изучение основ теории графов.


Задачи дисциплины:

• ознакомить студентов с базовыми понятиями, методами и результатами теории графов;
  
• ознакомить студентов с теоретико-графовыми алгоритмами решения различных комбинаторных задач и приложениями теории графов.
  

Разделы курса, темы, их краткое содержание

1. Маршруты, связность, циклы и разрезы. Матрицы, ассоциированные с графом.
   
2. Деревья, деревья в графах, остовы, теорема Кирхгофа.
   
3. Обходы графов, эйлеровы и гамильтоновы графы.
   
4. Матроиды и решетки, различные характеризации матроидов. Жадный алгоритм. Двойственный матроид.
   
5. Пространство циклов бинарного матроида. Пространства циклов и разрезов графа, их ортогональность.
   
6. Монотонные полумодулярные функции, индуцированный матроид. Трансверсальные матроиды и их приложения.
   
7. Дизъюнктное объединение и сумма матроидов, покрытия матроидов базами, покрытия графов остовами, число древовидности.
   
8. Блоки и точки сочленения, дерево блоков и точек сочленения связного графа.
   
9. Формула Эйлера для плоских графов и ее следствие для многогранников. Планарные графы, теоремы Понтрягина-Куратовского и Вагнера-Харари-Татта.
   
10. Двойственные графы, матроидная характеризация планарных графов, теорема Уитни.
    
11. Раскраски графов, теоремы Брукса и Хивуда. Приложения раскрасок графов в радиоэлектронике.
    
12. Хроматические многочлены и их свойства, теоремы Зыкова и Уитни.