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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Литература)
Строка 17: Строка 17:
 
== Литература ==
 
== Литература ==
 
#Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
 
#Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
#Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Изд. отд. ф-та ВМК МГУ имени М.В. ломоносова, 2002.
+
#Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Изд. отд. ф-та ВМК МГУ имени М.В. Ломоносова, 2002.
 
#Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
 
#Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
 
#Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
 
#Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

Версия 13:02, 8 сентября 2015

Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"

Курс читается в 1-м семестре магистратуры, 2 ч лекций, 1 ч семинаров

Лектор — доцент Селезнева Светлана Николаевна

Программа курса

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

Лекция 2. Остовное дерево. Алгоритмы построения остовного дерева связного графа. Теорема о числе остовных деревьев полного графа. Теорема о двух остовных деревьях связного графа. Теоремы об оценке числа висячих вершин остовного дерева связного графа. Труднорешаемые задачи, труднорешаемость задачи построения остовного дерева с наибольшим числом висячих вершин.

Программа семинарских занятий

Семинар 1. Простейшие свойства графов.

Литература

  1. Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
  2. Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Изд. отд. ф-та ВМК МГУ имени М.В. Ломоносова, 2002.
  3. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
  4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
  5. Карпов Д.В. Теория графов.
  6. Липский В. Комбинаторика для программистов. М.: Мир, 1988.
  7. Оре О. Теория графов. М.: Наука, 1980.
  8. Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.
  9. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.
  10. Харари Ф. Теория графов. М.: Мир, 1973.
  11. Kleitman D.J., West D.B.