Графы и их приложения — различия между версиями
(→Объявления) |
PodymovVV (обсуждение | вклад) м |
||
| (не показаны 5 промежуточные версии 1 участника) | |||
| Строка 1: | Строка 1: | ||
| + | [[Категория:Лекционные курсы кафедры МК]] | ||
[[Категория:Спецкурсы кафедры МК]] | [[Категория:Спецкурсы кафедры МК]] | ||
Спецкурс для аспирантов. | Спецкурс для аспирантов. | ||
| Строка 8: | Строка 9: | ||
==Объявления== | ==Объявления== | ||
| − | + | Вопросы по содержанию курса можно присылать Селезневой Светлане Николаевне по эл. почте selezn@cs.msu.ru | |
==Экзамен== | ==Экзамен== | ||
| Строка 14: | Строка 15: | ||
Экзамен письменный. Продолжительность экзамена – 1 час 30 минут (90 минут). В проверочной работе десять заданий разной сложности по содержанию курса. Первые четыре задания – стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания – формулировки определений или теорем с дополнительным вопросом. Вопрос проясняет понимание аспирантом формулировки. Они оцениваются также в три балла каждое. Оставшиеся два задания – вопросы или задачи повышенной сложности. Они показывают, может ли аспирант извлекать новые сведения из полученных знаний в курсе. Всего за работу можно получить не более 32 баллов. Критерии оценок: не менее 27 баллов – «отлично», 21-26 баллов – «хорошо», 15-20 баллов – «удовлетворительно», менее 14 баллов – «неудовлетворительно». | Экзамен письменный. Продолжительность экзамена – 1 час 30 минут (90 минут). В проверочной работе десять заданий разной сложности по содержанию курса. Первые четыре задания – стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания – формулировки определений или теорем с дополнительным вопросом. Вопрос проясняет понимание аспирантом формулировки. Они оцениваются также в три балла каждое. Оставшиеся два задания – вопросы или задачи повышенной сложности. Они показывают, может ли аспирант извлекать новые сведения из полученных знаний в курсе. Всего за работу можно получить не более 32 баллов. Критерии оценок: не менее 27 баллов – «отлично», 21-26 баллов – «хорошо», 15-20 баллов – «удовлетворительно», менее 14 баллов – «неудовлетворительно». | ||
| − | '''Вопросы для подготовки к экзамену ( | + | '''Вопросы для подготовки к экзамену (2024-2025 уч. год)''' |
1. Граф. Степень вершины в графе, формула Эйлера. Пути, цепи и циклы в графе, их свойства. Связность, компоненты связности графа. Соотношение между числом вершин, числом ребер и числом компонент связности в графе. | 1. Граф. Степень вершины в графе, формула Эйлера. Пути, цепи и циклы в графе, их свойства. Связность, компоненты связности графа. Соотношение между числом вершин, числом ребер и числом компонент связности в графе. | ||
| Строка 20: | Строка 21: | ||
2. Деревья, основные свойства деревьев. | 2. Деревья, основные свойства деревьев. | ||
| − | 3. | + | 3. Разделяющие вершины и ребра (мосты) в графе. Критерии разделяющей вершины и моста в графе. |
| − | + | ||
| − | + | ||
| − | + | 4. Вершинно двусвязные графы. Критерий двусвязности графа. Реберно двусвязные графы. Критерий реберно двусвязного графа. | |
| − | + | 5. Компоненты двусвязности связного графа. Дерево компонент двусвязности и разделяющих вершин связного графа. | |
| − | 7. | + | 6. Остовные деревья. Число остовных деревьев в полном помеченном графе (теорема Кэли). |
| + | |||
| + | 7. Остовные деревья. Достижимость промежуточного числа висячих вершин в остовном дереве графа. | ||
| + | |||
| + | 8. Остовные деревья. Оценка числа висячих вершин в остовном дереве графа. | ||
| − | + | 9. Хроматическое число графа. Критерий раскрашиваемости вершин графа в два цвета (теорема Кенига). | |
| − | + | 10. Хроматическое число графа. Верхние оценки хроматического числа графа (теорема Брукса). | |
| − | + | 11. Хроматическое число графа. Существование графов без треугольников с произвольно большим хроматическим числом (теорема Зыкова). | |
| − | + | 12. Хроматический индекс графа. Хроматический индекс двудольного графа (теорема Кенига). | |
| − | + | 13. Хроматический индекс графа. Верхняя оценка хроматического индекса графа (теорема Визинга). | |
| − | + | 14. Наследственные свойства графов. Рекуррентное соотношение о наибольшем числе ребер в графе с наследственным свойством. | |
| − | + | 15. Наследственные свойства графов. Планарные графы. Наибольшее число ребер в планарном графе. | |
| − | + | 16. Наследственные свойства графов. Наибольшее число ребер в графе без треугольников. | |
| − | + | 17. Наследственные свойства графов. Наибольшее число ребер в графе без полного подграфа с n вершинами (теорема Турана). | |
| − | + | 18. Числа Рамсея. Рекуррентное соотношение для чисел Рамсея. Верхние оценки числа Рамсея. | |
| − | + | 19. Числа Рамсея. Нижняя оценка числа Рамсея (теорема Эрдеша). | |
==Лекции== | ==Лекции== | ||
| − | '''Лекция 1'''. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья. Остовные деревья. | + | <!---'''Лекция 1'''. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья. Остовные деревья. |
'''Лекция 2'''. Деревья. Остовные деревья. Число остовных деревьев в помеченном полном графе. Достижимость промежуточного числа висячих вершин в остовном дереве. Оценка числа висячих вершин в остовном дереве. | '''Лекция 2'''. Деревья. Остовные деревья. Число остовных деревьев в помеченном полном графе. Достижимость промежуточного числа висячих вершин в остовном дереве. Оценка числа висячих вершин в остовном дереве. | ||
| Строка 64: | Строка 67: | ||
'''Лекция 5'''. Числа Рамсея. Верхняя оценка числа Рамсея. Нижняя оценка числа Рамсея. | '''Лекция 5'''. Числа Рамсея. Верхняя оценка числа Рамсея. Нижняя оценка числа Рамсея. | ||
| − | '''Лекция 6'''. Раскраски вершин графов. Хроматическое число графа. Критерий двуцветности графа. Верхние оценки хроматического числа графа. Существование графа без треугольников с произвольно большим хроматическим числом. | + | '''Лекция 6'''. Раскраски вершин графов. Хроматическое число графа. Критерий двуцветности графа. Верхние оценки хроматического числа графа. Существование графа без треугольников с произвольно большим хроматическим числом.---> |
<!--- | <!--- | ||
'''Лекция 5'''. Раскраски ребер графов. Хроматический индекс графа. Хроматический индекс двудольных графов. Верхняя и нижняя оценки хроматического индекса графа. | '''Лекция 5'''. Раскраски ребер графов. Хроматический индекс графа. Хроматический индекс двудольных графов. Верхняя и нижняя оценки хроматического индекса графа. | ||
Текущая версия на 14:21, 7 октября 2024
Спецкурс для аспирантов.
Лектор - Селезнева Светлана Николаевна
Аннотация. В курсе рассматриваются основные структурные свойства графов и показывается их применение при решении подходящих задач. Разбираются простейшие свойства графов, связность и k-связность, деревья и остовные деревья, вершинные и реберные раскраски графов, наследственные свойства графов и экстремальные графы, числа Рамсея, статистические свойства графов и потоки в сетях. Кроме того, уделяется внимание алгоритмическим вопросам, связанным с графами, в частности, труднорешаемым графовым задачам. Приводятся как классические, так и достаточно новые результаты, относящиеся к свойствам графов.
Содержание
Объявления
Вопросы по содержанию курса можно присылать Селезневой Светлане Николаевне по эл. почте selezn@cs.msu.ru
Экзамен
Экзамен письменный. Продолжительность экзамена – 1 час 30 минут (90 минут). В проверочной работе десять заданий разной сложности по содержанию курса. Первые четыре задания – стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания – формулировки определений или теорем с дополнительным вопросом. Вопрос проясняет понимание аспирантом формулировки. Они оцениваются также в три балла каждое. Оставшиеся два задания – вопросы или задачи повышенной сложности. Они показывают, может ли аспирант извлекать новые сведения из полученных знаний в курсе. Всего за работу можно получить не более 32 баллов. Критерии оценок: не менее 27 баллов – «отлично», 21-26 баллов – «хорошо», 15-20 баллов – «удовлетворительно», менее 14 баллов – «неудовлетворительно».
Вопросы для подготовки к экзамену (2024-2025 уч. год)
1. Граф. Степень вершины в графе, формула Эйлера. Пути, цепи и циклы в графе, их свойства. Связность, компоненты связности графа. Соотношение между числом вершин, числом ребер и числом компонент связности в графе.
2. Деревья, основные свойства деревьев.
3. Разделяющие вершины и ребра (мосты) в графе. Критерии разделяющей вершины и моста в графе.
4. Вершинно двусвязные графы. Критерий двусвязности графа. Реберно двусвязные графы. Критерий реберно двусвязного графа.
5. Компоненты двусвязности связного графа. Дерево компонент двусвязности и разделяющих вершин связного графа.
6. Остовные деревья. Число остовных деревьев в полном помеченном графе (теорема Кэли).
7. Остовные деревья. Достижимость промежуточного числа висячих вершин в остовном дереве графа.
8. Остовные деревья. Оценка числа висячих вершин в остовном дереве графа.
9. Хроматическое число графа. Критерий раскрашиваемости вершин графа в два цвета (теорема Кенига).
10. Хроматическое число графа. Верхние оценки хроматического числа графа (теорема Брукса).
11. Хроматическое число графа. Существование графов без треугольников с произвольно большим хроматическим числом (теорема Зыкова).
12. Хроматический индекс графа. Хроматический индекс двудольного графа (теорема Кенига).
13. Хроматический индекс графа. Верхняя оценка хроматического индекса графа (теорема Визинга).
14. Наследственные свойства графов. Рекуррентное соотношение о наибольшем числе ребер в графе с наследственным свойством.
15. Наследственные свойства графов. Планарные графы. Наибольшее число ребер в планарном графе.
16. Наследственные свойства графов. Наибольшее число ребер в графе без треугольников.
17. Наследственные свойства графов. Наибольшее число ребер в графе без полного подграфа с n вершинами (теорема Турана).
18. Числа Рамсея. Рекуррентное соотношение для чисел Рамсея. Верхние оценки числа Рамсея.
19. Числа Рамсея. Нижняя оценка числа Рамсея (теорема Эрдеша).
Лекции
Литература
Основная:
1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2009.
2. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.
Дополнительная:
3. Diestel R. Graph Theory. Springer, 2010.
4. Карпов Д.В. Теория графов
5. Харари Ф. Теория графов. М.: Мир, 1973.
6. Оре О. Теория графов. М.: Наука, 1980.
7. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
8. Липский В. Комбинаторика для программистов. М.: Мир, 1988.
9. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. М.: МЦНМО, 2014.
10. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.
11. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
