Графы и их применения — различия между версиями
| Строка 9: | Строка 9: | ||
'''Лекция 1'''. Основные определения. Простейшие свойства графов. Граф, изоморфизм графов. Степень вершины, изолированная и висячая вершины. Теорема о сумме степеней вершин графа. Маршрут, путь, цикл в графе. Теорема о свойствах путей и циклов в графе. Связность, компонента связности. Теорема о числе ребер в связном графе. Дерево. Теоремы о свойствах деревьев. | '''Лекция 1'''. Основные определения. Простейшие свойства графов. Граф, изоморфизм графов. Степень вершины, изолированная и висячая вершины. Теорема о сумме степеней вершин графа. Маршрут, путь, цикл в графе. Теорема о свойствах путей и циклов в графе. Связность, компонента связности. Теорема о числе ребер в связном графе. Дерево. Теоремы о свойствах деревьев. | ||
| − | '''Лекция 2'''. Остовное дерево. Алгоритмы построения остовного дерева связного графа. Теорема о числе остовных деревьев полного графа. Теорема о двух остовных деревьях связного графа. Теоремы об оценке числа висячих вершин остовного дерева связного графа. Труднорешаемые задачи, труднорешаемость задачи построения остовного дерева с наибольшим числом висячих вершин. | + | '''Лекция 2'''. Остовное дерево. Алгоритмы построения остовного дерева связного графа. Теорема о числе остовных деревьев полного графа. Теорема о двух остовных деревьях связного графа. Теоремы об оценке числа висячих вершин остовного дерева связного графа. Труднорешаемые задачи, труднорешаемость задачи построения остовного дерева с наибольшим числом висячих вершин. |
| + | |||
| + | ==Программа семинарских занятий== | ||
| + | |||
| + | '''Семинар 1'''. Простейшие свойства графов. | ||
| + | |||
| + | == Литература == | ||
| + | #Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. | ||
| + | #Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Изд. отд. ф-та ВМК МГУ имени М.В. ломоносова, 2002. | ||
| + | #Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. | ||
| + | #Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. | ||
| + | #Карпов Д.В. Теория графов. | ||
| + | #Липский В. Комбинаторика для программистов. М.: Мир, 1988. | ||
| + | #Оре О. Теория графов. М.: Наука, 1980. | ||
| + | #Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986. | ||
| + | #Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966. | ||
| + | #Харари Ф. Теория графов. М.: Мир, 1973. | ||
| + | #Kleitman D.J., West D.B. | ||
| + | |||
| + | |||
[[Категория:Лекционные курсы кафедры МК]] | [[Категория:Лекционные курсы кафедры МК]] | ||
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]] | [[Категория:Магистерская программа Дискретные структуры и алгоритмы]] | ||
Версия 13:01, 8 сентября 2015
Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"
Курс читается в 1-м семестре магистратуры, 2 ч лекций, 1 ч семинаров
Лектор — доцент Селезнева Светлана Николаевна
Программа курса
Лекция 1. Основные определения. Простейшие свойства графов. Граф, изоморфизм графов. Степень вершины, изолированная и висячая вершины. Теорема о сумме степеней вершин графа. Маршрут, путь, цикл в графе. Теорема о свойствах путей и циклов в графе. Связность, компонента связности. Теорема о числе ребер в связном графе. Дерево. Теоремы о свойствах деревьев.
Лекция 2. Остовное дерево. Алгоритмы построения остовного дерева связного графа. Теорема о числе остовных деревьев полного графа. Теорема о двух остовных деревьях связного графа. Теоремы об оценке числа висячих вершин остовного дерева связного графа. Труднорешаемые задачи, труднорешаемость задачи построения остовного дерева с наибольшим числом висячих вершин.
Программа семинарских занятий
Семинар 1. Простейшие свойства графов.
Литература
- Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
- Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Изд. отд. ф-та ВМК МГУ имени М.В. ломоносова, 2002.
- Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
- Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
- Карпов Д.В. Теория графов.
- Липский В. Комбинаторика для программистов. М.: Мир, 1988.
- Оре О. Теория графов. М.: Наука, 1980.
- Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.
- Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.
- Харари Ф. Теория графов. М.: Мир, 1973.
- Kleitman D.J., West D.B.
