Электронный учебно-методический комплекс по дисциплине "Теория графов" БГУИР, 2011
Целью изучения дисциплины является изложение основных понятий теории графов, демонстрация их возможностей в части постановки многих важных прикладных задач, описание способов их решения, развитие «структурного» подхода к описанию сложных систем.
Дисциплина входит в число дисциплин по выбору студентов и читается по часам Совета вуза. Её роль – дополнить базовые дисциплины специальности в части более основательного и детального изучения математических и прикладных основ теории графов.
Задачи изучения дисциплины
Задачами изучения дисциплины являются: изложение понятийного аппарата теории графов; изучение структурных характеристик графов; классификация и перечисления графов; постановки прикладных задач на графах и изучение методов их решения.
В результате изучения дисциплины студенты должны:
– знать:
1) базовые понятия и характеристики теории графов;
2) классификации, перечисления и представления графов;
3) основные прикладные задачи теории графов;
4) способы описания систем и исследования их структурных свойств с помощью средств теории графов;
– уметь:
1) описывать структуры систем средствами теории графов и исследовать их инвариантные топологические свойства;
2) формулировать и решать многие важные задачи на языке теории графов;
3) использовать характеристические свойства графов;
– иметь представление о деревьях, остовных графах, цепях, компонентах связности.
СОДЕРЖАНИЕ
ОБЩИЕ СВЕДЕНИЯ
Сведения об ЭУМКД
Методические рекомендации по изучению дисциплины
Рабочая учебная программа
ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ
1 БАЗОВЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ
1.1 Классификация и характеристики графов
1.2 Независимые множества, покрытия, клика
1.3 Проблемы клики, изоморфной вложимости и изоморфного подграфа
2 ОБХОДЫ, ПЛАНАРНОСТЬ И ПЕРЕСЧЁТ ГРАФОВ
2.1 Эйлеровы циклы и эйлеровы графы. Формула Эйлера
2.2 Плоские и планарные графы. Критерии планарности
2.3 Перечисление графов
3 ПРИКЛАДНЫЕ ЗАДАЧИ НА ГРАФАХ
3.1 Минимальный остов и кратчайший путь
3.2 Задача о максимальном потоке
Вопросы к зачёту по курсу «Теория графов»
ПРАКТИЧЕСКИЙ РАЗДЕЛ
Выбор варианта задания
КОНТРОЛЬНАЯ РАБОТА «ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ»
