Начальные понятия теории графов

Сформулируйте определения и утверждения, используя необходимые обозначения, и приведите примеры:

ü простого графа (неориентированного и ориентированного);

ü мультиграфа (неориентированного и ориентированного);

ü псевдографа (неориентированного и ориентированного);

ü инцидентных вершины и ребра;

ü смежных вершин и смежных ребер;

ü висячей и изолированной вершин графа;

ü кратных ребер (дуг) и петель;

ü подграфа;

ü маршрута (пути) и его длины в ненагруженном графе;

ü цепи, простой цепи и гамильтоновой цепи;

ü цикла (контура), простого цикла, гамильтонова цикла;

ü полного графа, число ребер полного графа;

ü связного графа;

ü нагруженного графа;

ü изоморфных графов;

ü плоского и планарного графа.

Матрицы инцидентности, смежности и способы задания графов

Сформулируйте определения и утверждения, используя необходимые обозначения, и приведите примеры:

ü матрицы инцидентности неориентированного и ориентированного графов;

ü матрицы смежности неориентированного и ориентированного графов;

ü способов задания графов.

Степени вершин

Сформулируйте определения и утверждения, используя необходимые обозначения, и приведите примеры:

ü степени вершины неориентированного графа, мультиграфа и псевдографа;

ü полустепеней исхода и захода вершины в орграфе;

ü лемма о рукопожатиях и её следствие;

ü теорема о сумме полустепеней вершин;

ü однородного графа.

Расстояния в графе

Сформулируйте определения и утверждения, используя необходимые обозначения, и приведите примеры:

ü минимального маршрута (пути) в ненагруженном графе;

ü расстояния между двумя вершинами в графе;

ü матрицы длин (весов) ребер или дуг в нагруженном графе;

ü длины маршрута (пути) в нагруженном графе;

ü минимального маршрута (пути) в нагруженном графе;

ü матрицы расстояний в графе;

ü диаметра графа;

ü эксцентриситета вершины;

ü радиуса графа;

ü центра графа.

Поиск минимального пути в ненагруженном орграфе. Волновой алгоритм

Сформулируйте определения и утверждения, используя необходимые обозначения, и приведите примеры:

ü образа вершины и множества вершин в орграфе;

ü прообраза вершины и множества вершин в орграфе;

ü волнового алгоритма;

ü теорему о фронте волны k -го уровня.

Поиск минимального пути в нагруженном орграфе. Алгоритм Дейкстры

Сформулируйте, используя необходимые обозначения, и приведите примеры:

ü алгоритма Дейкстры.

Деревья. Построение остовного дерева графа

Сформулируйте определения и утверждения, используя необходимые обозначения, и приведите примеры:

ü дерева;

ü о свойствах любого дерева;

ü о связности подграфа, полученного удалением висячей вершины связного графа;

ü остовного дерева связного графа;

ü цикломатического числа графа;

ü алгоритма поиска остовного дерева ненагруженного графа.

Построение минимального остовного дерева

Сформулируйте определения и утверждения, используя необходимые обозначения, и приведите примеры:

ü минимального остовного дерева;

ü алгоритма выделения МОД нагруженного связного графа.

Эйлеровы графы

Сформулируйте определения и утверждения, используя необходимые обозначения, и приведите примеры:

ü эйлерова цикла, цепи и графа;

ü теорему эйлера;

ü теорему об эйлеровой цепи;

ü алгоритма Флёри.

Гамильтоновы графы

Сформулируйте определения и утверждения, используя необходимые обозначения, и приведите примеры:

ü гамильтонова цикла, цепи и графа;

ü необходимые признаки гамильтоновости графа;

ü теорему Хватала;

ü теоремы Оре и Дирака;

ü теорему о гамильтоновости полного графа;

ü поиск гамильтоновых циклов и цепей методом перебора Робертса-Флореса.