Критерии оценки

Для оценки уровня полученных знаний при выполнении разработанных тестовых заданий по модулю предлагается использовать следующую шкалу:

85 – 100% правильных ответов – оценка «отлично»;

70 – 84% правильных ответов – оценка «хорошо»;

55 – 69% правильных ответов – оценка «удовлетворительно»;

менее 55% правильных ответов – оценка «неудовлетворительно».

Глоссарий к модулю 4 Глоссарий к главе 1

Блок графа – это его максимальный неразделимый подграф.

Вершинная связность графа – это наименьшее число вершин, удаление которых приводит к несвязному графу. Связность в графе с точкой сочленения равна 1. Связность в несвязном графе равна 0.

Взвешенный граф – это граф с весами на ребрах.

Граф – это объект, состоящий из двух множеств: точек и линий, которые находятся между собой в некотором отношении. Понятие графа опирается на понятие множества.

Граф – математический объект, который состоит из множества вершин и множества ребер или дуг, находящихся между собой в некотором отношении.

Длина маршрута определяется числом ребер, входящих в маршрут.

Если ребро соединяет две вершины графа, то говорят, что ребро инцидентно этим вершинам или вершины инцидентны данному ребру.

Конечный граф – граф, у которого множества вершин и ребер представляют собой конечные множества.

Локальная степень или просто степень вершины графа – это число ребер, инцидентных данной вершине. Локальная степень вершины x_i обозначается (x_i) или _i.

Маршрут в графе – это некоторая конечная последовательность ребер имеющая начальную и конечную вершину.

Граф также может быть задан с помощью матрицы инцидентности. Матрица инцидентности – это прямоугольная таблица, состоящая из нулей и единиц. Строкам матрицы соответствуют вершины, а столбцам – ребра графа. Причем на пересечении строки столбца ставится единица, если вершина, соответствующая данной строке, инцидентна ребру, соответствующему данному столбцу.

При матричном способе задания графов можно использовать матрицу смежности. Матрица смежности – это квадратная таблица, состоящая из нулей и единиц. Строкам и столбцам матрицы соответствуют вершины графа, причем на пересечении строки столбца ставится единица, если вершины, соответствующие данной строке и столбцу, являются смежными (т.е. соединены ребром).

Множество вершин – это множество точек графа.

Множество ребер или дуг – множество линий, соединяющих любые пары вершин графа.

Мультиграф – граф, у которого существует хотя бы одна пара вершин, соединяемых несколькими ребрами. Ребра, соединяющие одну и ту же пару вершин, называются кратными. Максимальное число кратных ребер в мультиграфе называется его мультичислом.

Неориентированный граф (неорграф) – граф, содержащий только подмножество ребер.

Неразделимый граф – это связный, непустой, не имеющий точек сочленения граф.

Нуль-граф – граф, у которого множество ребер является пустым, а все его вершины – изолированные.

Ориентированный граф (орграф) – это граф, содержащий только подмножество дуг.

Отношение связности является отношением эквивалентности.

Перешеек (мост) в графе – это разрез, состоящий из одного ребра.

Подграф – часть графа, у которой все вершины и ребра принадлежат исходному графу, а ребра подграфа соединяют только вершины подграфа. Подграф можно получить, удалив из исходного графа одну или несколько вершин с инцидентными им ребрами.

Подмножество дуг – подмножество ориентированных линий, для которых существен порядок соединения вершин. Каждая дуга определяется упорядоченной парой (кортежем длины два) вершин, которые она соединяет.

Подмножество петель – подмножество линий, каждая из которых выходит и входит в одну и ту же соответствующую этой линии вершину. Каждая петля может определяться как упорядоченной, так и неупорядоченной парой вершин.

Подмножество ребер графа – подмножество неориентированных линий, для которых несуществен порядок соединения вершин. Каждое ребро определяется неупорядоченной парой вершин, которые оно соединяет.

Полный граф – граф, между любой парой вершин которого имеется ребро. Полный граф обозначается K_n.

Правильный разрез графа – это разрез, который разбивает исходный граф точно на две компоненты связности. Тривиальными разрезами считают разрез, в который входят все ребра графа и разрез, не содержащие ни одного ребра графа.

Простая цепь (цикл) – это цепь (цикл), которая не содержит повторяющихся вершин, кроме первой и последней.

Простой граф – это граф, не содержащий петель и кратных ребер.

Разбиение графа представляет собой разбиение на непересекающиеся классы при условии, что ребра графа будут соединять только вершины внутри этих классов.

Разрез графа – это такое разбиение графа на два подмножества, при котором во множестве ребер графа одни концевые вершины принадлежат первому подмножеству вершин, а другие – второму.

Реберная связность – это наименьшее число ребер, удаление которых приводит к несвязному или тривиальному графу.

Регулярный граф – граф, все вершины которого имеют одинаковые локальные степени.

Две произвольные вершины графа называются связными, если существует маршрут, в котором концевыми будут эти вершины.

Граф является связным, если любые две его вершины связаны. В противном случае граф не связен, а каждый из составляющих его подграфов называется компонентой связности.

Смежностный (двойственный) граф – граф, вершинами которого являются ребра исходного графа, а ребрами пары ребер исходного графа, имеющие общую вершину. Для построения двойственного графа на каждом ребре исходного графа выбирают среднюю точку и считают ее вершиной.

Любые две вершины графа называются смежными, если существует соединяющие эти вершины ребра. Аналогично, если два ребра инцидентны одной и той же вершине, то они также называются смежными.

Смешанный граф – это граф, содержащий подмножества ребер, дуг и петель.

Основные способы задания графа – геометрический, аналитический и матричный.

Суграф – это часть графа, содержащая обязательно все вершины исходного графа, а также все либо часть его ребер.

Точка сочленения – вершина графа, после удаления которой граф распадается на связные компоненты.

Треугольник – цикл длины 3.

Цепь – это маршрут, в котором нет повторяющихся ребер.

Цикл – это замкнутая цепь, в которой первая и последняя вершины совпадают.

Циклический граф (цикл) – связный регулярный граф степени 2.