Начальные понятия теории графов
Сформулируйте определения и утверждения, используя необходимые обозначения, и приведите примеры:
ü простого графа (неориентированного и ориентированного);
ü мультиграфа (неориентированного и ориентированного);
ü псевдографа (неориентированного и ориентированного);
ü инцидентных вершины и ребра;
ü смежных вершин и смежных ребер;
ü висячей и изолированной вершин графа;
ü кратных ребер (дуг) и петель;
ü подграфа;
ü маршрута (пути) и его длины в ненагруженном графе;
ü цепи, простой цепи и гамильтоновой цепи;
ü цикла (контура), простого цикла, гамильтонова цикла;
ü полного графа, число ребер полного графа;
ü связного графа;
ü нагруженного графа;
ü изоморфных графов;
ü плоского и планарного графа.
Матрицы инцидентности, смежности и способы задания графов
Сформулируйте определения и утверждения, используя необходимые обозначения, и приведите примеры:
ü матрицы инцидентности неориентированного и ориентированного графов;
ü матрицы смежности неориентированного и ориентированного графов;
ü способов задания графов.
Степени вершин
Сформулируйте определения и утверждения, используя необходимые обозначения, и приведите примеры:
ü степени вершины неориентированного графа, мультиграфа и псевдографа;
ü полустепеней исхода и захода вершины в орграфе;
ü лемма о рукопожатиях и её следствие;
ü теорема о сумме полустепеней вершин;
ü однородного графа.
Расстояния в графе
Сформулируйте определения и утверждения, используя необходимые обозначения, и приведите примеры:
ü минимального маршрута (пути) в ненагруженном графе;
ü расстояния между двумя вершинами в графе;
ü матрицы длин (весов) ребер или дуг в нагруженном графе;
ü длины маршрута (пути) в нагруженном графе;
ü минимального маршрута (пути) в нагруженном графе;
ü матрицы расстояний в графе;
ü диаметра графа;
ü эксцентриситета вершины;
ü радиуса графа;
ü центра графа.
Поиск минимального пути в ненагруженном орграфе. Волновой алгоритм
Сформулируйте определения и утверждения, используя необходимые обозначения, и приведите примеры:
ü образа вершины и множества вершин в орграфе;
ü прообраза вершины и множества вершин в орграфе;
ü волнового алгоритма;
ü теорему о фронте волны k-го уровня.
Поиск минимального пути в нагруженном орграфе. Алгоритм Дейкстры
Сформулируйте, используя необходимые обозначения, и приведите примеры:
ü алгоритма Дейкстры.
Деревья. Построение остовного дерева графа
Сформулируйте определения и утверждения, используя необходимые обозначения, и приведите примеры:
ü дерева;
ü о свойствах любого дерева;
ü о связности подграфа, полученного удалением висячей вершины связного графа;
ü остовного дерева связного графа;
ü цикломатического числа графа;
ü алгоритма поиска остовного дерева ненагруженного графа.
Построение минимального остовного дерева
Сформулируйте определения и утверждения, используя необходимые обозначения, и приведите примеры:
ü минимального остовного дерева;
ü алгоритма выделения МОД нагруженного связного графа.
Эйлеровы графы
Сформулируйте определения и утверждения, используя необходимые обозначения, и приведите примеры:
ü эйлерова цикла, цепи и графа;
ü теорему эйлера;
ü теорему об эйлеровой цепи;
ü алгоритма Флёри.
Гамильтоновы графы
Сформулируйте определения и утверждения, используя необходимые обозначения, и приведите примеры:
ü гамильтонова цикла, цепи и графа;
ü необходимые признаки гамильтоновости графа;
ü теорему Хватала;
ü теоремы Оре и Дирака;
ü теорему о гамильтоновости полного графа;
ü поиск гамильтоновых циклов и цепей методом перебора Робертса-Флореса.