Федеральное государственное бюджетное образовательное
учреждение высшего образования 
Московский государственный университет имени М.В. Ломоносова
Факультет вычислительной математики и кибернетики

УТВЕРЖДАЮ
декан факультета вычислительной математики и кибернетики
______________/И.А. Соколов /
«___» ________________20___г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Наименование дисциплины:
Избранные вопросы теории графов
Уровень высшего образования:
бакалавриат
Направление подготовки / специальность:
01.03.02 «Прикладная математика и информатика» (3++)
Направленность (профиль):
Математические методы обработки информации и принятия решений
Форма обучения:
очная

Москва 2023

Рабочая программа дисциплины (модуля) разработана в соответствии с самостоятельно установленным МГУ образовательным стандартом (ОС МГУ) для реализуемых основных профессиональных образовательных программ высшего образования по направлению подготовки 01.03.02, 01.04.02 "Прикладная математика и информатика" программы бакалавриата  Утвержден приказом МГУ от 30 августа 2019 года № 1041 (в редакции приказов МГУ от 11 сентября 2019 года № 1109, от 10 июня 2021 года № 609, от 7 октября 2021 года № 1048, от 21 декабря 2021 года № 1404, от 2 ноября 2022 года № 1299)

1. Дисциплина относится к вариативной части ОПОП ВО.

2. Входные требования для освоения дисциплины (модуля): учащиеся должны владеть знаниями по математическому анализу, линейной алгебре и дискретной математике в объеме, соответствующем программе первых двух лет обучения основных образовательных программ бакалавриата по укрупненным группам направлений и специальностей 01.00.00 «Математика и механика», 02.00.00 «Компьютерные и информационные науки».

3. Результаты обучения по дисциплине (модулю), соотнесенные с требуемыми компетенциями выпускников.

Компетенции выпускников, частично формируемые при реализации дисциплины (модуля):

•	ОПК-1.Б Способность применять и адаптировать существующие математические и компьютерные методы для разработки и реализации алгоритмов решения актуальных задач в области фундаментальной и прикладной математики
•	ПК-2.Б Способность понимать и применять в научно-исследовательской деятельности современный математический аппарат
•	СПК-ИВТГ-1.Б Способность понимать и применять подходы и методы теории графов, основные свойства графов при решении задач в профессиональной деятельности.

Планируемые результаты обучения по дисциплине (модулю):

Знать:
1.	общие свойства графов, основные свойства деревьев и остовных деревьев в графах;
2.	основные свойства связных, двусвязных и k-связных графов;  
3.	свойства вершинных и реберных раскрасок графов, их верхние и нижние оценки;
4.	некоторые наследственные свойства графов и экстремальные графы для этих свойств;
5.	основы теории Рамсея, верхние и нижние оценки чисел Рамсея; 
6.	основные свойства потоков в сетях, алгоритмы построения максимальных потоков в сетях;
7.	некоторые графовые алгоритмы и труднорешаемые графовые задачи,
8.	основные свойства матриц, связанных с графами,
9.	свойства алгебр смежности мультиграфов и характеристических многочленов мультиграфов,
10.	некоторые свойства матриц мультиграфов, связанные с их симметриями,
11.	основы теории перечисления помеченных графов,
12.	основы теории перечисления непомеченных графов.

Уметь:
1.	находить или оценивать число неизоморфных графов с заданными свойствами;
2.	находить компоненты связности и двусвязности в графах, строить bc-дерево связного графа;
3.	находить или оценивать хроматическое число или хроматический индекс графа;
4.	описывать графы с заданным наследственным свойством, оценивать числа Рамсея;
5.	находить максимальный поток в сети и его величину,
6.	строить матрицы смежности, инцидентности, степеней мультиграфов и мультиорграфов и устанавливать взаимосвязи между ними,.
7.	определять по матрицам, связанным с графом, некоторые метрические характеристики графа, в том числе число его компонент связности и древесную сложность графа, 
8.	находить характеристический многочлен мультиграфа,
9.	получать оценки размерности алгебры смежности мультиграфа,
10.	выражать через характеристический многочлен регулярного мультиграфа характеристический многочлен его реберного мультиграфа,
11.	выражать через характеристический многочлен простого регулярного графа характеристический многочлен его дополнения,
12.	вычислять спектры графов из специальных классов (циркулянтные графы, полные графы, циклы, гипероктаэдральные и триангулированные графы),
13.	распознавать с помощью матриц, является ли подстановка автоморфизмом графа,
14.	распознавать некоторые свойства графов, связанные с вершинной и реберной группами автоморфизмов графа,
15.	находить количества попарно неизоморфных помеченных и непомеченных графов из некоторых специальных классов.

Владеть:  
1.	навыками понимания и применения графовых понятий и их свойств при решении прикладных задач в профессиональной деятельности.

4. Формат обучения: лекции проводятся с применением слайдов.

5. Объем дисциплины (модуля) составляет 3 з.е., в том числе 54 академических часа, отведенных на контактную работу обучающихся с преподавателем, 54 академических часа на самостоятельную работу обучающихся. 

6. Содержание дисциплины (модуля), структурированное по темам (разделам) с указанием отведенного на них количества академических часов и виды учебных занятий.

Наименование и краткое содержание разделов и тем дисциплины (модуля),

Форма промежуточной аттестации по дисциплине (модулю)	Всего
(часы)	В том числе	
		Контактная работа 
(работа во взаимодействии с преподавателем)
Виды контактной работы, часы	Самостоятельная работа обучающегося,
 часы 
	
		Занятия лекционного типа*	Занятия семинарского типа*	Всего		
1.	Тема 1 «Структурные свойства графов».  Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья. Остовные деревья. Точки сочленения и мосты. Связность, k-связность. Двусвязные графы. Компоненты двусвязности (блоки) графа. Дерево блоков и точек сочленения графа. Деревья. Остовные деревья. Достижимость промежуточного числа висячих вершин в остовном дереве. Оценка числа висячих вершин в остовном дереве. Раскраски вершин графов. Хроматическое число графа. Критерий двуцветности графа. Верхние оценки хроматического числа графа. Существование графа без треугольников с произвольно большим хроматическим числом. Раскраски ребер графов. Хроматический индекс графа. Хроматический индекс двудольных графов. Верхняя и нижняя оценки хроматического индекса графа.  Наследственные свойства графов. Экстремальные графы. Наибольшее число ребер в графах с наследственным свойством. Наибольшее число ребер в планарных графах. Наибольшее число ребер в графах без полного подграфа с n вершинами. Числа Рамсея. Верхняя оценка числа Рамсея. Нижняя оценка числа Рамсея. Сеть. Поток в сети. Теорема о величине максимального потока в сети. Нахождение максимального потока в сети. Труднорешаемые графовые задачи распознавания. NP-полнота задачи k-раскраски графов при каждом заданном числе k  3.	20	16	0	16	4	
2.	Текущий контроль успеваемости: коллоквиум № 1.	4	2	0	2	2	
3.	Тема 2 « Методы линейной алгебры в теории графов». Помеченные графы, изоморфизм помеченных графов. Связь между числом помечиваний вершин простого графа и порядком его группы автоморфизмов. Матрицы смежности, инцидентности, степеней вершин, полустепеней исхода и захода, расстояний. Интерпретация элементов степеней матрицы смежности. Теоремы о связи матриц инцидентности для мультиграфов и мультиорграфов с их матрицами смежности. Теоремы о тотальной унимодулярности и ранге матрицы инцидентности мультиорграфа. Теорема Г. Кирхгофа о деревьях. Следствия из нее (о числе остовных деревьев в полном графе и формуле для древесной сложности мультиграфа). Алгебра смежности мультиграфа. Теоремы о размерности алгебры смежности при заданном диаметре мультиграфа и при заданном числе его собственных значений. Утверждение о величине некоторых коэффициентов характеристического многочлена графа. Теорема о верхней границе для собственных значений графа. Теорема о собственных значениях регулярного мультиграфа. Критерий принадлежности матрицы Jn алгебре смежности мультиграфа. Следствие о виде матрицы Jn. Нижняя оценка для собственных значений реберного мультиграфа. Теорема о связи характеристических многочленов регулярного мультиграфа и его реберного мультиграфа. Выражение сложности регулярного мультиграфа через его характеристический многочлен. Теорема о сложности реберного мультиграфа, построенного для регулярного связного мультиграфа. Верхняя оценка для сложности регулярного связного мультиграфа. Циркулянтные графы и их спектры. Спектры полных графов, циклов, гипероктаэдральных и триангулированных графов. Теорема о спектрах дополнительных графов. Матрицы подстановок. Теорема о перестановочности матрицы подстановки, соответствующей автоморфизму графа, с матрицей смежности графа. Теорема о связи матриц подстановок с простыми собственными значениями графа. Теорема об автоморфизме, порядок которого больше 2. Вершинно-транзитивные и реберно-транзитивные графы. Теорема о двудольности реберно-транзитивных графов. Теорема о простом собственном значении вершинно-транзитивного графа. Реберно-симметрические графы. Теорема о простых собственных значениях реберно-симметрических графов.	20	16	0	16	4	
4.	Текущий контроль успеваемости: коллоквиум № 2.	4	2	0	2	2	
5.	Тема 3 «Перечисление графов». Число помеченных графов и орграфов. Рекуррентная формула для помеченных связных графов. Теорема об асимптотике отношения числа помеченных связных n-графов к числу всех помеченных n-графов. Лемма о перечислении помеченных графов. Интерпретации операций над формальными рядами (умножение и деление на переменную, дифференцирование ряда). Формула, связывающая производящие функции для помеченных графов некоторого семейства и помеченных связных графов из этого же семейства. Частные случаи этой формулы (для всех графов и для всех четных графов). Асимптотика числа помеченных блоков. Формулировки леммы Бернсайда, ограниченной формы леммы Бернсайда и теоремы Д. Пойа (для случая одной переменной и случая многих переменных). Вывод формулы для циклового индекса симметрической группы. Рекуррентная формула, связывающая цикловые индексы симметрических групп. Вывод формулы для суммы цикловых индексов симметрических групп всех степеней. Связь циклового индекса знакопеременной группы с цикловым индексом симметрической группы. Теорема о перечислении взаимно однозначных функций. Перечисление корневых непомеченных деревьев. Рекуррентная формула для числа корневых деревьев. Теорема Р. Оттера о производящей функции для непомеченных деревьев. Перечисляющий многочлен для n-графов. Асимптотика числа n-графов. Связь производящей функции для непомеченных графов с производящей функцией для непомеченных связных графов. Рекуррентная формула для числа непомеченных связных графов. Константная форма теоремы перечисления степенной группы. Перечисление самодополнительных графов. Теорема перечисления степенной группы в форме степенного ряда.	20	16	0	16	4	
6.	Текущий контроль успеваемости: коллоквиум № 3. 	4	2	0	2	2	
Аттестация: экзамен	36				36	
Итого	108	54	0	54	54	

7. Фонд оценочных средств (ФОС) для оценивания результатов обучения по дисциплине (модулю)
7.1. Типовые контрольные задания или иные материалы для проведения текущего контроля успеваемости.

Коллоквиум № 1. Пример задания коллоквиума № 1.

1.	Что такое остовное дерево в графе? Как найти остовное дерево связного графа? Сформулировать теорему об оценке числа висячих вершин в остовном дереве графа. Как доказывается эта теорема?
2.	Что такое хроматический индекс графа? Привести простейшие оценки хроматического индекса графа. Сформулировать и доказать теорему Кенига о хроматическом индексе двудольного графа.
3.	Что такое поток в сети и его величина? Привести и доказать верхнюю оценку величины потока в сети. Что такое максимальный поток в сети? Сформировать теорему о величине максимального потока в сети. Как можно найти максимальный поток в заданной сети?
Коллоквиум № 2. Пример задания коллоквиума № 2.

1.	Что такое алгебра смежности мультиграфа? Сформулировать теоремы о размерности алгебры смежности при заданном диаметре мультиграфа и при заданном числе его собственных значений. Как доказываются эти теоремы?
2.	Что такое вершинно-транзитивные и реберно-транзитивные графы. Сформулировать теорему о двудольности реберно-транзитивных графов. Как доказывается эта теорема?

Коллоквиум № 3. Пример задания коллоквиума № 3.

1.	Какова рекуррентная формула для числа помеченных связных графов? Выведите эту формулу. Сформулируйте теорему об асимптотике отношения числа помеченных связных n-графов к числу всех помеченных n-графов. Как доказываются эти теоремы?
2.	Выведите формулу для суммы цикловых индексов симметрических групп всех степеней. Установите связь циклового индекса знакопеременной группы с цикловым индексом симметрической группы.

7.2. Типовые контрольные задания или иные материалы для проведения промежуточной аттестации.

Вопросы к экзамену.

В билете три вопроса  (по одному из каждой части курса).  

Часть 1. Структурные свойства графов.

1.	Точки сочленения и мосты в графе. Теорема о равносильных определениях точки сочленения. Связность, k-связность. Двусвязные графы. Теорема о равносильных определениях двусвязного графа.
2.	Компоненты двусвязности (блоки) в графе. Критерий принадлежности двух вершин графа одной компоненте двусвязности. Свойства компонент двусвязности графа. Теорема о дереве блоков и точек сочленения графа.
3.	Остовные деревья в графе. Теорема о достижимости промежуточного числа висячих вершин в остовном дереве графа. Теорема об оценке числа висячих вершин в остовном дереве графа.
4.	Хроматическое число графа. Критерий Кенига двуцветности графа. Верхние оценки хроматического числа графа. Теорема Брукса о верхней оценке хроматического числа графа.
5.	Хроматическое число графа. Теорема Зыкова о существовании графов без треугольников с произвольно большим хроматическим числом.
6.	Хроматический индекс графа. Теорема Кенига о хроматическом индексе двудольного графа. Теорема Визинга о верхней оценке хроматического индекса графа.
7.	Наследственные свойства графов. Теорема об оценке наибольшего числа ребер в графе с наследственным свойством. Планарные графы, теорема о наибольшем числе ребер в планарном графе.
8.	Наследственные свойства графов. Теорема о наибольшем числе ребер в графе без треугольников. Теорема Турана о наибольшем числе ребер в графе без полного подграфа с n вершинами.
9.	Числа Рамсея. Теорема о верхней оценке числа Рамсея. Теорема Эрдеша о нижней оценке числа Рамсея.
10.	Потоки в сетях. Теорема Форда и Фалкерсона о величине максимального потока в сети. Алгоритм расстановки пометок для построения максимального потока в сети.
11.	 Труднорешаемые графовые задачи. NP-полнота задачи k-раскраски графа при каждом заданном числе k  3.

Часть 2. Методы линейной алгебры в теории графов

12.	Помеченные графы, изоморфизм помеченных графов. Связь между числом помечиваний вершин простого графа и порядком его группы автоморфизмов.
13.	Матрицы смежности, инцидентности, степеней вершин, полустепеней исхода и захода, расстояний.
14.	Интерпретация элементов степеней матрицы смежности.
15.	Теоремы о связи матриц инцидентности для мультиграфов и мультиорграфов с их матрицами смежности.
16.	Теоремы о тотальной унимодулярности и ранге матрицы инцидентности мультиорграфа.
17.	Теорема Г. Кирхгофа о деревьях. Следствия из нее (о числе остовных деревьев в полном графе и формуле для древесной сложности мультиграфа).
18.	Алгебра смежности мультиграфа. Теоремы о размерности алгебры смежности при заданном диаметре мультиграфа и при заданном числе его собственных значений.
19.	Утверждение о величине некоторых коэффициентов характеристического многочлена графа.
20.	Теорема о верхней границе для собственных значений графа.
21.	Теорема о собственных значениях регулярного мультиграфа.
22.	Критерий принадлежности матрицы Jn алгебре смежности мультиграфа. Следствие о виде матрицы Jn.
23.	Нижняя оценка для собственных значений реберного мультиграфа.
24.	Теорема о связи характеристических многочленов регулярного мультиграфа и его реберного мультиграфа.
25.	Выражение сложности регулярного мультиграфа через его характеристический многочлен.
26.	Теорема о сложности реберного мультиграфа, построенного для регулярного связного мультиграфа.
27.	Верхняя оценка для сложности регулярного связного мультиграфа.
28.	Циркулянтные графы и их спектры. Спектры полных графов, циклов, гипероктаэдральных и триангулированных графов. 
29.	Теорема о спектрах дополнительных графов.
30.	Матрицы подстановок. Теорема о перестановочности матрицы подстановки, соответствующей автоморфизму графа, с матрицей смежности графа.
31.	Теорема о связи матриц подстановок с простыми собственными значениями графа.
32.	Теорема об автоморфизме, порядок которого больше 2.
33.	Вершинно-транзитивные и реберно-транзитивные графы. Теорема о двудольности реберно-транзитивных графов.
34.	Теорема о простом собственном значении вершинно-транзитивного графа.
35.	Реберно-симметрические графы. Теорема о простых собственных значениях реберно-симметрических графов.

Часть 3. Перечисление графов

36.	Число помеченных графов и орграфов. Рекуррентная формула для помеченных связных графов.
37.	Теорема об асимптотике отношения числа помеченных связных n-графов к числу всех помеченных n-графов.
38.	Лемма о перечислении помеченных графов.
39.	Интерпретации операций над формальными рядами (умножение и деление на переменную, дифференцирование ряда).
40.	Формула, связывающая производящие функции для помеченных графов некоторого семейства и помеченных связных графов из этого же семейства. Частные случаи этой формулы (для всех графов и для всех четных графов).
41.	Асимптотика числа помеченных блоков.
42.	Теорема А. Кэли о числе помеченных деревьев (доказательство Д. Пойа).
43.	Формулировки леммы Бернсайда, ограниченной формы леммы Бернсайда и теоремы Д. Пойа (для случая одной переменной и случая многих переменных).
44.	Вывод формулы для циклового индекса симметрической группы. Рекуррентная формула, связывающая цикловые индексы симметрических групп. Вывод формулы для суммы цикловых индексов симметрических групп всех степеней.
45.	Связь циклового индекса знакопеременной группы с цикловым индексом симметрической группы.
46.	Теорема о перечислении взаимно однозначных функций.
47.	Перечисление корневых непомеченных деревьев. Рекуррентная формула для числа корневых деревьев.
48.	Теорема о характеристике неподобия для графов.
49.	Теорема о центре дерева.
50.	Теорема Р. Оттера о характеристике неподобия для деревьев.
51.	Теорема Р. Оттера о производящей функции для непомеченных деревьев.
52.	Перечисляющий многочлен для n-графов.
53.	Асимптотика числа n-графов.
54.	Связь производящей функции для непомеченных графов с производящей функцией для непомеченных связных графов.
55.	Рекуррентная формула для числа непомеченных связных графов.
56.	Константная форма теоремы перечисления степенной группы.
57.	Перечисление самодополнительных графов.
58.	Теорема перечисления степенной группы в форме степенного ряда.	
Экзаменационный билет состоит из трёх вопросов, например

1.	Хроматическое число графа. Критерий Кенига двуцветности графа. Верхние оценки хроматического числа графа. Теорема Брукса о верхней оценке хроматического числа графа.
2.	Теоремы о связи матриц инцидентности для мультиграфов и мультиорграфов с их матрицами смежности.
3.	Константная форма теоремы перечисления степенной группы.

ШКАЛА И КРИТЕРИИ ОЦЕНИВАНИЯ результатов обучения (РО) по дисциплине (модулю)  	
Оценка
РО и
соответствующие виды оценочных средств 	2	3	4	5	
Знания
Коллоквиум,
Экзамен	Отсутствие знаний	Отдельные знания	Общие, но не структурированные знания	Сформированные систематические знания	
Умения
Контрольная работа, зачет	Отсутствие умений	В целом успешное, но не систематическое умение	В целом успешное, но содержащее отдельные пробелы умение (допускает неточности непринципиального характера)	Успешное и систематическое умение	
Навыки (владения, опыт деятельности)
Экзамен	Отсутствие навыков (владений, опыта)	Наличие отдельных навыков (наличие частичного опыта)	В целом, сформированные навыки (владения), но недостаточно используемые 	Сформированные навыки (владения), применяемые при решении задач	

Соответствие результатов обучения и компетенций, в развитии которых участвует дисциплина (модуль)	
Результаты обучения	Компетенция, с частичным формированием которой связано достижение результата обучения	
Знать:
1.	общие свойства графов, основные свойства деревьев и остовных деревьев в графах;
2.	основные свойства связных, двусвязных и k-связных графов;  
3.	свойства вершинных и реберных раскрасок графов, их верхние и нижние оценки;
4.	некоторые наследственные свойства графов и экстремальные графы для этих свойств;
5.	основы теории Рамсея, верхние и нижние оценки чисел Рамсея; 
6.	основные свойства потоков в сетях, алгоритмы построения максимальных потоков в сетях;
7.	некоторые графовые алгоритмы и труднорешаемые графовые задачи,
8.	основные свойства матриц, связанных с графами,
9.	свойства алгебр смежности мультиграфов и характеристических многочленов мультиграфов,
10.	некоторые свойства матриц мультиграфов, связанные с их симметриями,
11.	основы теории перечисления помеченных графов,
12.	основы теории перечисления непомеченных графов.

Уметь:  
1.	находить или оценивать число неизоморфных графов с заданными свойствами;
2.	находить компоненты связности и двусвязности в графах, строить bc-дерево связного графа;
3.	находить или оценивать хроматическое число или хроматический индекс графа;
4.	описывать графы с заданным наследственным свойством, оценивать числа Рамсея;
5.	находить максимальный поток в сети и его величину,
6.	строить матрицы смежности, инцидентности, степеней мультиграфов и мультиорграфов и устанавливать взаимосвязи между ними,.
7.	определять по матрицам, связанным с графом, некоторые метрические характеристики графа, в том числе число его компонент связности и древесную сложность графа, 
8.	находить характеристический многочлен мультиграфа,
9.	получать оценки размерности алгебры смежности мультиграфа,
10.	выражать через характеристический многочлен регулярного мультиграфа характеристический многочлен его реберного мультиграфа,
11.	выражать через характеристический многочлен простого регулярного графа характеристический многочлен его дополнения,
12.	вычислять спектры графов из специальных классов (циркулянтные графы, полные графы, циклы, гипероктаэдральные и триангулированные графы),
13.	распознавать с помощью матриц, является ли подстановка автоморфизмом графа,
14.	распознавать некоторые свойства графов, связанные с вершинной и реберной группами автоморфизмов графа,
15.	находить количества попарно неизоморфных помеченных и непомеченных графов из некоторых специальных классов.

Владеть:  
1.	навыками понимания и применения графовых понятий и их свойств при решении прикладных задач в профессиональной деятельности.

ОПК-1.Б, ПК-2.Б, СПК-ИВТГ-1.Б	

8. Ресурсное обеспечение:

Основная литература:
  
1.	Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2009.
2.	Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.
3.	Гаврилов Г. П., Романов Д. С. Методы линейной алгебры в теории графов. М.: Изд-во ВМиК МГУ, 1996 г.
4.	Харари Ф., Палмер Э. Перечисление графов. М.: «Мир», 1977.
5.	Стенли Р. Перечислительная комбинаторика. М.: «Мир». I том, 1992; II том, 2005.

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

1.	Diestel R. Graph Theory. Springer, 2010.
2.	 Харари Ф. Теория графов. М.: Мир, 1973.
3.	 Оре О. Теория графов. М.: Наука, 1980.
4.	Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
5.	Липский В. Комбинаторика для программистов. М.: Мир, 1988.
6.	Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.
7.	Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.  
8.	Цветкович Д., Дуб М., Захс Х. Спектры графов. Теория и применение. — Киев: «Наукова думка», 1984 г.
9.	Де Брёйн Н. Теория перечисления Пойа // В сб. «Прикладная комбинаторная математика». М.: «Мир», 1968. Стр. 61–106.
10.	Пойа Д. Комбинаторные вычисления для групп, графов и химических соединений // в сб. «Перечислительные задачи комбинаторного анализа». М.: «Мир», 1979. Стр. 36–138.
11.	Оттер Р. Число деревьв. Там же, стр. 139–159.
12.	Айгнер М., Комбинаторная теория. М.: «Мир», 1982.
13.	Риордан Дж. Введение в комбинаторный анализ. М.: ИЛ, 1963.
14.	Сачков В.Н. Введение в комбинаторные методы дискретной математики. М.: «Физматлит», 2004.
15.	Татт У.Т. Теория графов. М.: «Мир», 1988.

Информационные справочные системы:

http://mk.cs.msu.ru/index.php/Избранные_вопросы_теории_графов  - страница курса

Материально-техническое обеспечение:  аудитория с партами, проектором, экраном и меловой доской.

9. Язык преподавания - русский.

10. Преподаватели:	профессор факультета ВМК МГУ С.Н. Селезнева,
			доцент факультета ВМК МГУ Д.С. Романов.

11. Авторы программы:  профессор факультета ВМК МГУ Г.П. Гаврилов, 
			       профессор факультета ВМК МГУ С.Н. Селезнева,
			       доцент факультета ВМК МГУ Д.С. Романов