Графы и их приложения — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Объявления)
(Объявления)
 
(не показаны 15 промежуточные версии 1 участника)
Строка 8: Строка 8:
 
==Объявления==
 
==Объявления==
  
'''Экзамен состоится в субботу, 25 декабря, в 10 ч 30 мин (по московскому времени) удаленно'''.
+
Итоги экзамена разосланы по почте. Посмотреть работы можно в пятницу, 29 декабря, в 13 ч 30 мин в к. 595 или 9 января в 13 ч 30 мин в к. 595.
  
В 10 ч на эл. почту студентам рассылаются экзаменационные задания.  приведен ниже на этой странице. На выполнение работы отводится 1 ч 30 мин (90 мин). Работу нужно написать от руки на светлых листах контрастной ручкой. Выполненную работу нужно отсканировать или сфотографировать. Затем скан или фотографию работы (в формате pdf, jpg или png) загрузить на проверку по ссылке, присланной в письме вместе с заданием. На сканирование/фотографирование и загрузку работы отводится 15 мин. Т.е. выполненные работы нужно загрузить до 11 ч 45 мин (иначе считается, что студент работу не сдал).
+
Экзамен состоится 20 декабря 2023 г. (в среду). Начало - в 16 ч 30 мин. Ауд. 503.
  
Лектор проверяет работы. При этом если в нескольких работах встречаются совпадающие решения какого-то задания, то это задание не засчитывается во всех этих работах. Затем итоги экзамена появляются на странице курса и объявляется время, когда студенты могут задать вопросы лектору по оценкам в своих работах. После этого оценки за экзамен выставляются в ведомость.
+
==Экзамен==
  
Все вопросы, связанные с отсутствием интернета во время экзамена, будут решаться отдельно в каждом случае.
+
Экзамен письменный. Продолжительность экзамена – 1 час 30 минут (90 минут). В проверочной работе десять заданий разной сложности по содержанию курса. Первые четыре задания – стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания – формулировки определений или теорем с дополнительным вопросом. Вопрос проясняет понимание аспирантом формулировки. Они оцениваются также в три балла каждое. Оставшиеся два задания – вопросы или задачи повышенной сложности. Они показывают, может ли аспирант извлекать новые сведения из полученных знаний в курсе. Всего за работу можно получить не более 32 баллов. Критерии оценок: не менее 27 баллов – «отлично», 21-26 баллов – «хорошо», 15-20 баллов – «удовлетворительно», менее 14 баллов – «неудовлетворительно».  
  
Вопросы по содержанию курса можно направлять по эл. почте лектору Селезневой Светлане Николаевне.
+
'''Вопросы для подготовки к экзамену (2023-2024 уч. год)'''
  
==Лекции==
+
1. Граф. Степень вершины в графе, формула Эйлера. Пути, цепи и циклы в графе, их свойства. Связность, компоненты связности графа. Соотношение между числом вершин, числом ребер и числом компонент связности в графе.
  
[[Media:gip-asp-l1-selezn.pdf|'''Лекция 1''']]. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья. Остовные деревья.
+
2. Деревья, основные свойства деревьев.
  
[[Media:gip-asp-l2-selezn.pdf|'''Лекция 2''']]. Точки сочленения и мосты. Связность, k-связность. Двусвязные графы. Компоненты двусвязности (блоки) графа. Дерево блоков и точек сочленения графа.
+
3. Остовные деревья. Число остовных деревьев в полном помеченном графе (теорема Кэли).
 +
 +
4. Остовные деревья. Оценка числа висячих вершин в остовном дереве графа.
  
[[Media:gip-asp-l3-selezn.pdf|'''Лекция 3''']]. Деревья. Остовные деревья. Число остовных деревьев в помеченном полном графе. Достижимость промежуточного числа висячих вершин в остовном дереве. Оценка числа висячих вершин в остовном дереве.
+
5. Остовные деревья. Достижимость промежуточного числа висячих вершин в остовном дереве графа.
  
[[Media:gip-asp-l4-selezn.pdf|'''Лекция 4''']]. Раскраски вершин графов. Хроматическое число графа. Критерий двуцветности графа. Верхние оценки хроматического числа графа. Существование графа без треугольников с произвольно большим хроматическим числом.
+
6. Разделяющие вершины и ребра (мосты) в графе. Критерии разделяющей вершины и моста в графе.
  
[[Media:gip-asp-l5-selezn.pdf|'''Лекция 5''']]. Раскраски ребер графов. Хроматический индекс графа. Хроматический индекс двудольных графов. Верхняя и нижняя оценки хроматического индекса графа.
+
7. Вершинно двусвязные графы. Критерий двусвязности графа. Реберно двусвязные графы. Критерий реберно двусвязного графа.
  
[[Media:gip-asp-l6-selezn.pdf|'''Лекция 6''']]. Наследственные свойства графов. Экстремальные графы. Наибольшее число ребер в графах с наследственным свойством. Наибольшее число ребер в планарных графах. Наибольшее число ребер в графах без полного подграфа с n вершинами.
+
8. Компоненты двусвязности связного графа. Поиск компонент двусвязности графа. Дерево компонент двусвязности и разделяющих вершин связного графа.
  
[[Media:gip-asp-l7-selezn.pdf|'''Лекция 7''']]. Числа Рамсея. Верхняя оценка числа Рамсея. Нижняя оценка числа Рамсея.
+
9. Пополнения в графе. Пополнения остовного дерева до двусвязного и реберно двусвязного графов.
  
[[Media:gip-asp-l8-selezn.pdf|'''Лекция 8''']]. Сеть. Поток в сети. Теорема о величине максимального потока в сети. Нахождение максимального потока в сети.
+
10. Наследственные свойства графов. Рекуррентное соотношение о наибольшем числе ребер в графе с наследственным свойством.
  
[[Media:gip-asp-l9-selezn.pdf|'''Лекция 9''']]. Труднорешаемые графовые задачи распознавания. NP-полнота задачи k-раскраски графов при каждом заданном числе k \ge 3.
+
11. Наследственные свойства графов. Планарные графы. Наибольшее число ребер в планарном графе.
 +
 
 +
12. Наследственные свойства графов. Наибольшее число ребер в графе без треугольников.
 +
 
 +
13. Наследственные свойства графов. Наибольшее число ребер в графе без полного подграфа с n вершинами (теорема Турана).
 +
 
 +
14. Числа Рамсея. Рекуррентное соотношение для чисел Рамсея. Верхние оценки числа Рамсея.
 +
 
 +
15. Числа Рамсея. Нижняя оценка числа Рамсея (теорема Эрдеша).
 +
 
 +
16. Хроматическое число графа. Критерий раскраски вершин графа в два цвета (теорема Кенига).
 +
 
 +
17. Хроматическое число графа. Верхние оценки хроматического числа графа (теорема Брукса).
 +
 
 +
18. Хроматическое число графа. Существование графов без треугольников с произвольно большим хроматическим числом (теорема Зыкова).
 +
 
 +
==Лекции==
 +
 
 +
'''Лекция 1'''. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья. Остовные деревья.
 +
 
 +
'''Лекция 2'''. Деревья. Остовные деревья. Число остовных деревьев в помеченном полном графе. Достижимость промежуточного числа висячих вершин в остовном дереве. Оценка числа висячих вершин в остовном дереве.
 +
 
 +
'''Лекция 3'''. Точки сочленения и мосты. Связность, k-связность. Двусвязные графы. Компоненты двусвязности (блоки) графа. Дерево блоков и точек сочленения графа.
 +
 
 +
'''Лекция 4'''. Наследственные свойства графов. Экстремальные графы. Наибольшее число ребер в графах с наследственным свойством. Наибольшее число ребер в планарных графах. Наибольшее число ребер в графах без полного подграфа с n вершинами.
 +
 
 +
'''Лекция 5'''. Числа Рамсея. Верхняя оценка числа Рамсея. Нижняя оценка числа Рамсея.
 +
 
 +
'''Лекция 6'''. Раскраски вершин графов. Хроматическое число графа. Критерий двуцветности графа. Верхние оценки хроматического числа графа. Существование графа без треугольников с произвольно большим хроматическим числом.
 +
<!---
 +
'''Лекция 5'''. Раскраски ребер графов. Хроматический индекс графа. Хроматический индекс двудольных графов. Верхняя и нижняя оценки хроматического индекса графа.
 +
 
 +
'''Лекция 8'''. Сеть. Поток в сети. Теорема о величине максимального потока в сети. Нахождение максимального потока в сети.
 +
 
 +
'''Лекция 9'''. Труднорешаемые графовые задачи распознавания. NP-полнота задачи k-раскраски графов при каждом заданном числе k \ge 3.--->
  
 
'''Литература'''
 
'''Литература'''
Строка 68: Строка 104:
 
==Экзамен==
 
==Экзамен==
  
Экзамен письменный. Продолжительность экзамена – 1,5 астрономических часа (90 минут). В проверочной работе десять заданий разной сложности по содержанию курса. Первые четыре задания – стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания – формулировки определений или теорем с дополнительным вопросом. Вопрос проясняет понимание аспирантом формулировки. Они оцениваются также в три балла каждое. Оставшиеся два задания – вопросы или задачи повышенной сложности. Они показывают, может ли аспирант извлекать новые сведения из полученных знаний в курсе. Всего за работу можно получить не более 32 баллов. Критерии оценок: не менее 27 баллов – «отлично», 21-26 баллов – «хорошо», 15-20 баллов – «удовлетворительно», менее 14 баллов – «неудовлетворительно».
+
<!---9. Хроматический индекс графа. Теорема о хроматическом индексе полного графа.
 
+
'''Вопросы для подготовки к экзамену'''
+
 
+
1. Точки сочленения и мосты в графе. Теорема о равносильных определениях точки сочленения. Связность, k-связность. Двусвязные графы. Теорема о равносильных определениях двусвязного графа.
+
+
2. Компоненты двусвязности (блоки) в графе. Критерий принадлежности двух вершин графа одной компоненте двусвязности. Свойства компонент двусвязности графа. Теорема о дереве блоков и точек сочленения графа.
+
 
+
3. Остовные деревья в графе. Теорема Кэли о числе остовных деревьев помеченного полного графа.
+
+
4. Остовные деревья в графе. Теорема о достижимости промежуточного числа висячих вершин в остовном дереве графа.
+
 
+
5. Остовные деревья в графе. Теорема об оценке числа висячих вершин в остовном дереве графа.
+
 
+
6. Хроматическое число графа. Критерий Кенига двуцветности графа. Верхние оценки хроматического числа графа.
+
 
+
7. Хроматическое число графа. Теорема Брукса о верхней оценке хроматического числа графа.
+
 
+
8. Хроматическое число графа. Теорема Зыкова о существовании графов без треугольников с произвольно большим хроматическим числом.
+
 
+
9. Хроматический индекс графа. Теорема о хроматическом индексе полного графа.
+
  
 
10. Хроматический индекс графа. Теорема Кенига о хроматическом индексе двудольного графа.
 
10. Хроматический индекс графа. Теорема Кенига о хроматическом индексе двудольного графа.
  
 
11. Хроматический индекс графа. Теорема Визинга о верхней оценке хроматического индекса графа.
 
11. Хроматический индекс графа. Теорема Визинга о верхней оценке хроматического индекса графа.
 
12. Наследственные свойства графов. Теорема об оценке наибольшего числа ребер в графе с наследственным свойством.
 
 
13. Наследственные свойства графов. Планарные графы, теорема о наибольшем числе ребер в планарном графе.
 
 
14. Наследственные свойства графов. Теорема о наибольшем числе ребер в графе без треугольников.
 
 
15. Наследственные свойства графов. Теорема Турана о наибольшем числе ребер в графе без полного подграфа с n вершинами.
 
 
16. Числа Рамсея. Теорема о верхней оценке числа Рамсея.
 
 
17. Числа Рамсея. Теорема Эрдеша о нижней оценке числа Рамсея.
 
  
 
18. Обходы графов. Алгоритмы построения остовных деревьев на основе обходов графа.
 
18. Обходы графов. Алгоритмы построения остовных деревьев на основе обходов графа.
Строка 116: Строка 120:
 
22. Паросочетания в графах. Алгоритм построения наибольшего паросочетания в двудольном графе на основе построения максимального потока в сети.
 
22. Паросочетания в графах. Алгоритм построения наибольшего паросочетания в двудольном графе на основе построения максимального потока в сети.
  
23. Труднорешаемые графовые задачи. NP-полнота задачи k-раскраски графа при каждом заданном числе k \ge 3.
+
23. Труднорешаемые графовые задачи. NP-полнота задачи k-раскраски графа при каждом заданном числе k \ge 3.--->

Текущая версия на 23:28, 28 декабря 2023

Спецкурс для аспирантов.

Лектор - Селезнева Светлана Николаевна

Аннотация. В курсе рассматриваются основные структурные свойства графов и показывается их применение при решении подходящих задач. Разбираются простейшие свойства графов, связность и k-связность, деревья и остовные деревья, вершинные и реберные раскраски графов, наследственные свойства графов и экстремальные графы, числа Рамсея, статистические свойства графов и потоки в сетях. Кроме того, уделяется внимание алгоритмическим вопросам, связанным с графами, в частности, труднорешаемым графовым задачам. Приводятся как классические, так и достаточно новые результаты, относящиеся к свойствам графов.

Объявления

Итоги экзамена разосланы по почте. Посмотреть работы можно в пятницу, 29 декабря, в 13 ч 30 мин в к. 595 или 9 января в 13 ч 30 мин в к. 595.

Экзамен состоится 20 декабря 2023 г. (в среду). Начало - в 16 ч 30 мин. Ауд. 503.

Экзамен

Экзамен письменный. Продолжительность экзамена – 1 час 30 минут (90 минут). В проверочной работе десять заданий разной сложности по содержанию курса. Первые четыре задания – стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания – формулировки определений или теорем с дополнительным вопросом. Вопрос проясняет понимание аспирантом формулировки. Они оцениваются также в три балла каждое. Оставшиеся два задания – вопросы или задачи повышенной сложности. Они показывают, может ли аспирант извлекать новые сведения из полученных знаний в курсе. Всего за работу можно получить не более 32 баллов. Критерии оценок: не менее 27 баллов – «отлично», 21-26 баллов – «хорошо», 15-20 баллов – «удовлетворительно», менее 14 баллов – «неудовлетворительно».

Вопросы для подготовки к экзамену (2023-2024 уч. год)

1. Граф. Степень вершины в графе, формула Эйлера. Пути, цепи и циклы в графе, их свойства. Связность, компоненты связности графа. Соотношение между числом вершин, числом ребер и числом компонент связности в графе.

2. Деревья, основные свойства деревьев.

3. Остовные деревья. Число остовных деревьев в полном помеченном графе (теорема Кэли).

4. Остовные деревья. Оценка числа висячих вершин в остовном дереве графа.

5. Остовные деревья. Достижимость промежуточного числа висячих вершин в остовном дереве графа.

6. Разделяющие вершины и ребра (мосты) в графе. Критерии разделяющей вершины и моста в графе.

7. Вершинно двусвязные графы. Критерий двусвязности графа. Реберно двусвязные графы. Критерий реберно двусвязного графа.

8. Компоненты двусвязности связного графа. Поиск компонент двусвязности графа. Дерево компонент двусвязности и разделяющих вершин связного графа.

9. Пополнения в графе. Пополнения остовного дерева до двусвязного и реберно двусвязного графов.

10. Наследственные свойства графов. Рекуррентное соотношение о наибольшем числе ребер в графе с наследственным свойством.

11. Наследственные свойства графов. Планарные графы. Наибольшее число ребер в планарном графе.

12. Наследственные свойства графов. Наибольшее число ребер в графе без треугольников.

13. Наследственные свойства графов. Наибольшее число ребер в графе без полного подграфа с n вершинами (теорема Турана).

14. Числа Рамсея. Рекуррентное соотношение для чисел Рамсея. Верхние оценки числа Рамсея.

15. Числа Рамсея. Нижняя оценка числа Рамсея (теорема Эрдеша).

16. Хроматическое число графа. Критерий раскраски вершин графа в два цвета (теорема Кенига).

17. Хроматическое число графа. Верхние оценки хроматического числа графа (теорема Брукса).

18. Хроматическое число графа. Существование графов без треугольников с произвольно большим хроматическим числом (теорема Зыкова).

Лекции

Лекция 1. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья. Остовные деревья.

Лекция 2. Деревья. Остовные деревья. Число остовных деревьев в помеченном полном графе. Достижимость промежуточного числа висячих вершин в остовном дереве. Оценка числа висячих вершин в остовном дереве.

Лекция 3. Точки сочленения и мосты. Связность, k-связность. Двусвязные графы. Компоненты двусвязности (блоки) графа. Дерево блоков и точек сочленения графа.

Лекция 4. Наследственные свойства графов. Экстремальные графы. Наибольшее число ребер в графах с наследственным свойством. Наибольшее число ребер в планарных графах. Наибольшее число ребер в графах без полного подграфа с n вершинами.

Лекция 5. Числа Рамсея. Верхняя оценка числа Рамсея. Нижняя оценка числа Рамсея.

Лекция 6. Раскраски вершин графов. Хроматическое число графа. Критерий двуцветности графа. Верхние оценки хроматического числа графа. Существование графа без треугольников с произвольно большим хроматическим числом.

Литература

Основная:

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.

Экзамен