Избранные вопросы теории графов — различия между версиями
PodymovVV (обсуждение | вклад) м |
|||
| Строка 3: | Строка 3: | ||
Обязательный курс для студентов 418 группы | Обязательный курс для студентов 418 группы | ||
| − | + | Лекторы - [[Романов Дмитрий Сергеевич]], [[Селезнева Светлана Николаевна]]. | |
Список вопросов по курсу "Избранные вопросы теории графов". <sup>[[Media:Список вопросов к экзамену по курсу ИВТГ_.doc|Список в формате .doc]]</sup> | Список вопросов по курсу "Избранные вопросы теории графов". <sup>[[Media:Список вопросов к экзамену по курсу ИВТГ_.doc|Список в формате .doc]]</sup> | ||
| + | |||
| + | '''Часть 1'''. Лектор - Романов Дмитрий Сергеевич | ||
| + | |||
| + | '''Часть 2'''. Лектор - Романов Дмитрий Сергеевич | ||
| + | |||
| + | '''Часть 3'''. Лектор - Селезнева Светлана Николаевна | ||
| + | |||
| + | [[Media:gip-l1-selezn.pdf|'''Лекция 1''']]. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья. Остовные деревья. | ||
| + | |||
| + | [[Media:gip-l2-selezn.pdf|'''Лекция 2''']]. Точки сочленения и мосты. Связность, k-связность. Двусвязные графы. Компоненты двусвязности (блоки) графа. Дерево блоков и точек сочленения графа. | ||
| + | |||
| + | [[Media:gip-l3-selezn.pdf|'''Лекция 3''']]. Деревья. Остовные деревья. Число остовных деревьев помеченного полного графа. Достижимость промежуточного числа висячих вершин в остовном дереве. Оценка числа висячих вершин в остовном дереве. | ||
| + | |||
| + | [[Media:gip-l4-selezn.pdf|'''Лекция 4''']]. Раскраски вершин графов. Хроматическое число графа. Критерий двуцветности графа. Верхние оценки хроматического числа графа. Существование графов без треугольников с произвольно большим хроматическим числом. | ||
| + | |||
| + | [[Media:gip-l5-selezn.pdf|'''Лекция 5''']]. Раскраски ребер графов. Хроматический индекс графа. Хроматический индекс двудольных графов. Верхняя и нижняя оценки хроматического индекса графа. | ||
| + | |||
| + | [[Media:gip-l6-selezn.pdf|'''Лекция 6''']]. Наследственные свойства графов. Наибольшее число ребер в графах с наследственным свойством. Наибольшее число ребер в планарных графах. Наибольшее число ребер в графах без полного подграфа с n вершинами. | ||
| + | |||
| + | [[Media:gip-l7-selezn.pdf|'''Лекция 7''']]. Числа Рамсея. Верхняя и нижняя оценки числа Рамсея. | ||
Версия 17:24, 26 августа 2019
Обязательный курс для студентов 418 группы
Лекторы - Романов Дмитрий Сергеевич, Селезнева Светлана Николаевна.
Список вопросов по курсу "Избранные вопросы теории графов". Список в формате .doc
Часть 1. Лектор - Романов Дмитрий Сергеевич
Часть 2. Лектор - Романов Дмитрий Сергеевич
Часть 3. Лектор - Селезнева Светлана Николаевна
Лекция 1. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья. Остовные деревья.
Лекция 2. Точки сочленения и мосты. Связность, k-связность. Двусвязные графы. Компоненты двусвязности (блоки) графа. Дерево блоков и точек сочленения графа.
Лекция 3. Деревья. Остовные деревья. Число остовных деревьев помеченного полного графа. Достижимость промежуточного числа висячих вершин в остовном дереве. Оценка числа висячих вершин в остовном дереве.
Лекция 4. Раскраски вершин графов. Хроматическое число графа. Критерий двуцветности графа. Верхние оценки хроматического числа графа. Существование графов без треугольников с произвольно большим хроматическим числом.
Лекция 5. Раскраски ребер графов. Хроматический индекс графа. Хроматический индекс двудольных графов. Верхняя и нижняя оценки хроматического индекса графа.
Лекция 6. Наследственные свойства графов. Наибольшее число ребер в графах с наследственным свойством. Наибольшее число ребер в планарных графах. Наибольшее число ребер в графах без полного подграфа с n вершинами.
Лекция 7. Числа Рамсея. Верхняя и нижняя оценки числа Рамсея.
