|
|
(не показаны 16 промежуточные версии 1 участника) |
Строка 25: |
Строка 25: |
| Лектор - [[Селезнева Светлана Николаевна]] | | Лектор - [[Селезнева Светлана Николаевна]] |
| | | |
− | '''Программа''' части 3 | + | '''Программа 3 части''' |
− | | + | |
− | * Графы. Изоморфизм графов. Пути и циклы. Связность. Простейший свойства графов. Обходы графов. Деревья. Свойства деревьев. Остовные деревья. Число остовных деревьев в полном графе. Достижимость промежуточного числа висячих вершин в остовных деревьях. Число висячих вершин в остовных деревьях. Непересекающиеся остовные деревья.
| + | |
− | * Разделяющие вершины в графе. Свойства разделяющих вершин. Двусвязные графы. Свойства двусвязных графов. Мосты в графе. Свойства мостов. Реберно двусвязные графы их свойства. Компоненты двусвязности графа. Свойства компонент двусвязности. Разложение графа на компоненты двусвязности. Дерево компонент двусвязности и разделяющих вершин графа. Цепные разложения графа. Независимые деревья в графе. Реберно независимые деревья в графе.
| + | |
− | | + | |
− | '''Лекции''' | + | |
− | <!---[[Media:ivtg3-l1-selezn.pdf|'''Лекция 1''']]. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья.
| + | |
− | | + | |
− | [[Media:ivtg3-l2-selezn.pdf|'''Лекция 2''']]. Точки сочленения и мосты. Связность, k-связность. Двусвязные графы. Компоненты двусвязности (блоки) графа. Дерево блоков и точек сочленения графа.
| + | |
− | | + | |
− | [[Media:ivtg3-l3-selezn.pdf|'''Лекция 3''']]. Деревья. Остовные деревья. Достижимость промежуточного числа висячих вершин в остовном дереве. Оценка числа висячих вершин в остовном дереве.
| + | |
− | | + | |
− | [[Media:ivtg3-l4-selezn.pdf|'''Лекция 4''']]. Раскраски вершин графов. Хроматическое число графа. Критерий двуцветности графа. Верхние оценки хроматического числа графа. Существование графа без треугольников с произвольно большим хроматическим числом.
| + | |
− | | + | |
− | [[Media:ivtg3-l5-selezn.pdf|'''Лекция 5''']]. Раскраски ребер графов. Хроматический индекс графа. Хроматический индекс двудольных графов. Верхняя и нижняя оценки хроматического индекса графа.
| + | |
− | | + | |
− | [[Media:ivtg3-l6-selezn.pdf|'''Лекция 6''']]. Наследственные свойства графов. Экстремальные графы. Наибольшее число ребер в графах с наследственным свойством. Наибольшее число ребер в планарных графах. Наибольшее число ребер в графах без полного подграфа с n вершинами.
| + | |
− | | + | |
− | [[Media:ivtg3-l7-selezn.pdf|'''Лекция 7''']]. Числа Рамсея. Верхняя оценка числа Рамсея. Нижняя оценка числа Рамсея--->
| + | |
− | <!---'''Лекция 8'''. Сеть. Поток в сети. Теорема о величине максимального потока в сети. Нахождение максимального потока в сети.
| + | |
− | | + | |
− | '''Лекция 9'''. Труднорешаемые графовые задачи распознавания. NP-полнота задачи k-раскраски графов при каждом заданном числе k \ge 3.--->
| + | |
| | | |
| + | *Графы. Простейшие свойства графов. Деревья. Свойства деревьев. Остовные деревья. Число остовных деревьев. Оценки числа висячих вершин в остовном дереве. Достижимость промежуточного числа висячих вершин в остовном дереве. |
| + | *Связность, компоненты связности. Разделяющие вершины и разделяющие ребра (мосты). Свойства разделяющих вершин и ребер. Двусвязность и реберная двусвязность. Свойства двусвязных и реберно двусвязных графов. Разложение связного графа на компоненты двусвязности. |
| | | |
| '''Литература''' к части 3 | | '''Литература''' к части 3 |
Строка 55: |
Строка 36: |
| 2. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008. | | 2. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008. |
| | | |
− | 3. Diestel R. Graph Theory. Springer, 2010. | + | 3. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. |
− | | + | |
− | 4. Липский В. Комбинаторика для программистов. М.: Мир, 1988.
| + | |
− | | + | |
− | 5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
| + | |
− | | + | |
− | <!---'''Дополнительная''':
| + | |
− | | + | |
− | 6. Харари Ф. Теория графов. М.: Мир, 1973.
| + | |
− | | + | |
− | 7. Оре О. Теория графов. М.: Наука, 1980.
| + | |
− | | + | |
− | 8. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
| + | |
− | | + | |
− | 9. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. М.: МЦНМО, 2014.
| + | |
− | | + | |
− | 10. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.--->
| + | |
− | | + | |
− | '''Проверочные работы''' по части 3.
| + | |
− | | + | |
− | <!---В течение семестра по части 3 проводятся три проверочные работы:
| + | |
− | | + | |
− | 1-я по темам "Простейшие свойства графов. Двусвязность. Остовные деревья";
| + | |
− | | + | |
− | 2-я по темам "Раскраски вершин. Раскраски ребер. Экстремальные графы";
| + | |
− | | + | |
− | 3-я по темам "Теория Рамсея. Потоки в сетях. Труднорешаемые задачи".--->
| + | |
− | По итогам проверочных работ для каждого студента выводится предварительная оценка по части 3. Для подтверждения предварительной оценки по части 3 на экзамене проводится опрос студента по темам этой части (определения, формулировки теорем, основные идеи доказательств). Для повышения предварительной оценки по части 3 (не более, чем на один балл), студент тянет билет по этой части, готовится (30 мин) и отвечает на вопрос билета, после чего проводится опрос по темам этой части (определения, формулировки теорем, основные идеи доказательств).
| + | |
Лекции 3 ч в неделю, отчетность - экзамен.
1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2009.
2. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.
3. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.