Программа дисциплины «избранные главы теории графов»
|
Скачать 68.26 Kb.
|
Министерство образования Республики Беларусь Белорусский государственный университет Механико-математический факультет Кафедра уравнений математической физики УТВЕРЖДАЮ Проректор по учебной работе профессор В.В. Самохвал ________________________ Рег.№ __________________ «____» ____________ 2007 г. Базовая учебная программа дисциплины «ИЗБРАННЫЕ ГЛАВЫ ТЕОРИИ ГРАФОВ» для студентов специальности 1-31 03 01 «Математика» Минск 2007 ПОЯСНИТЕЛЬНАЯ ЗАПИСКА В настоящее время теория графов представляет собой один из наиболее бурно развивающихся разделов математики. Это вызвано как запросами стремительно расширяющейся области приложений, так и внутренней логикой развития самой математики. В теоретико-графовых терминах формулируется большое число задач, связанных с дискретными объектами. Такие задачи возникают при проектировании интегральных схем и схем управления, при исследовании автоматов, логических цепей, блок-схем программ, в экономике и статистике, социологии и психологии, химии и биологии, теории расписаний и дискретной оптимизации. Таким образом, теория графов становится одной из существенных частей математического аппарата кибернетики, языком дискретной математики. Основной задачей этой дисциплины является ознакомление студентов с теми разделами теории графов, которые либо недостаточно полно представлены в основном курсе по теории графов, либо вообще не вошли в этот курс. К числу таких разделов относятся “Раскраски графов”, “Планарные графы” и “Ориентированные графы”. "ИЗБРАННЫЕ ГЛАВЫ ТЕОРИИ ГРАФОВ" Цель спецкурса "Избранные главы теории графов": обучить студентов основам из трех избранных разделов теории графов (не вошедших в основной курс) и ознакомить с их приложениями. Тематический план спецкурса "Избранные главы теории графов"
Раздел 1. Раскраски графов Определение вершинной раскраски, хроматического числа графа. Применение вершинной раскраски. Алгоритм последовательной раскраски. Оценки хроматического числа через плотность и число независимости графа. Теорема Зыкова. Оценки хроматического числа через максимальную степень вершин графа, а также через минимальные степени его порожденных подграфов. Теорема Брукса. Оценки хроматического числа через число вершин, ребер графа. Хроматический полином графа. Общий вид хроматического полинома. Хроматический полином дерева. Определение реберной раскраски, хроматический индекс. Теорема Визинга. Хроматический индекс полного графа и двудольного графа. Раздел 2. Планарные графы Плоский граф, его элементы. Теорема Эйлера. Свойства планарных графов. Критерий планарности Понтрягина-Куратовского (без доказательства). Плоская триангуляция, ее свойства. Раздел 3. Ориентированные графы Элементы ориентированного графа. Сильносвязный, одностороннесвязный и слабосвязный орграфы. Сильносвязная компонента. Конденсация орграфа и ее свойство. База и ядро орграфа. ЛИТЕРАТУРА по курсу "Избранные главы теории графов" Основная: 1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. Дополнительная:
Автор: доцент кафедры уравнений математической физики, кандидат физ.-мат.наук Ю.М. Метельский Рецензент: Профессор кафедры уравнений математической физики, доктор физ.-мат.наук Р. И. Тышкевич, Одобрена на заседании кафедры уравнений математической физики протокол № 7 от 06 июня 2007 г. Одобрена на заседании Ученого совета механико-математического факультета протокол № 7 от 20 июня 2007 г. Ответственный за выпуск: доцент Метельский Ю.М., вед. лаборант кафедры уравнений математической физики Л.Н. Кулибаба | ||||||||||||||||||||||||||||||||||||||||||||||||
Похожие:
 | Программа наименование дисциплины: Теория конечных графов Цели и задачи дисциплины: Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение... | | Программа наименование дисциплины: Теория конечных графов Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение методов теории конечных... |
 | Рабочая учебная программа По дисциплине: Избранные главы теории вероятностей По направлению: 010900 «Прикладные математика и физика» Цель дисциплины – освоение студентами избранных глав теории вероятностей, в частности, теории массового обслуживания и теории случайных... | | Рабочая учебная программа По дисциплине: Избранные главы теории кодирования По направлению: 010900 «Прикладные математика и физика» Цель дисциплины – освоение студентами избранных глав современной теории информации и современной теории кодирования |
| Рабочая программа дисциплины (модуля) Теория графов Направление подготовки Целями освоения дисциплины (модуля) «Теория графов» являются получение теоретических знаний по основам теории графов | | Программа по дисциплине Избранные главы алгебры и теории чисел для специальности Рабочая программа составлена на основании |
| Методические указания к самостоятельным и семинарским занятиям по теории графов Москва 2006 Предназначены для решения задач по теории графов как при самостоятельном изучении теории графов, так и при решении задач на семинарах... | | Программа элективного курса Элементы теории графов и комбинаторики Учитель Курс “Элементы теории графов и комбинаторики” является дополнительным к стандартному курсу математики 5 класса для образовательных... |
| Программа дисциплины «теория графов» Таким образом, теория графов стала существенной частью математического аппарата кибернетики, языком дискретной математики. В значительной... | | Лекции по теории графов читаются либо в виде отдельного курса например, в юургу он читается как «Комбинаторика и теория графов» Потребности программирования определяют развитие «стыка» информатики и математики (алгебры, математической логики, теории игр, общей... |