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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
Строка 1: Строка 1:
Курс по магистерской программе Дискретные структуры и алгоритмы.
+
Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"
 +
 
 +
Курс читается в 1-м семестре магистратуры, 2 ч лекций, 1 ч семинаров
 +
 
 +
Лектор — доцент [[Селезнева Светлана Николаевна]]
 +
 
 +
==Программа курса==
 +
 
 +
'''Лекция 1'''. Основные определения. Простейшие свойства графов. Граф, изоморфизм графов. Степень вершины, изолированная и висячая вершины. Теорема о сумме степеней вершин графа. Маршрут, путь, цикл в графе. Теорема о свойствах путей и циклов в графе. Связность, компонента связности. Теорема о числе ребер в связном графе. Дерево. Теоремы о свойствах деревьев.
 +
 
 +
'''Лекция 2'''. Остовное дерево. Алгоритмы построения остовного дерева связного графа. Теорема о числе остовных деревьев полного графа. Теорема о двух остовных деревьях связного графа. Теоремы об оценке числа висячих вершин остовного дерева связного графа. Труднорешаемые задачи, труднорешаемость задачи построения остовного дерева с наибольшим числом висячих вершин.
  
Чтение курса обеспечивается кафедрой математической кибернетики, лектор — доцент [[Селезнева Светлана Николаевна]].
 
  
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]
 
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]

Версия 12:52, 8 сентября 2015

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

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

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

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

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

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