2.9 Практическое занятие № 20. Контрольная работа
Контрольная работа включает в себя шесть задач по следующим темам:
1) «Множества и операции над множествами»;
2) «Множества: свойства подмножеств и операций над множествами»;
3) «Бинарные отношения: способы задания, операции, свойства»;
4) «Группы, кольца, поля»;
5) «Комбинаторика: выборки, перестановки»;
6) «Комбинаторика: формула включений и исключений».
2.10 Практические занятия № 21 – 22. Орграфы и бинарные отношения. Связность. Компоненты связности
2.10.1 Теоретические сведения и методические рекомендации по решению задач
Граф G – совокупность двух множеств: вершин V и ребер Х, между которыми определено отношение инцидентности: каждое ребро х из множества Х инцидентно ровно двум вершинам v', v'', которые оно соединяет. При этом вершина v' и ребро х называются инцидентными друг другу, а вершины v' и v'' называются смежными.
Если |V(G)|=n, |E(G)|=m, то граф G есть (n,m) граф, где n – порядок графа, m – размер графа.
Ребро (v',v'') может быть ориентированным и иметь начало v' и конец v'', в этом случае ребро называется дугой, а граф называется ориентированным или орграфом.
Граф, не содержащий ориентированные ребра (дуги), называется неографом.
Ребро (v,v) называется петлей (концевые вершины совпадают).
Ребра, инцидентные одной паре вершин, называются параллельными или кратными.
Граф с кратными ребрами называется мультиграфом.
Граф, содержащий петли (и, возможно, кратные ребра), называется псевдографом.
Конечный граф – граф, число вершин и ребер которого конечно.
Пустой граф – граф, множество ребер которого пусто (число вершин может быть произвольным).
Полный граф –граф без петель и кратных ребер, каждая пара вершин соединена ребром.
Локальная степень (валентность)вершины – число ребер ей инцидентных.
В неографе сумма степеней всех вершин равна удвоенному числу ребер (лемма о рукопожатиях). Петля дает вклад, равный 2, в степень вершины.
Произвольный граф имеет четное число вершин нечетной степени.
Число ребер в полном графе равно n(n-1)/2.
В орграфе две локальных степени вершины v: deg(v)+ и deg (v)- – число дуг с началом и концом в v .
Графы равны, если множества вершин и инцидентных им ребер совпадают.
Графы, отличающиеся только нумерацией вершин и ребер, называются изоморфными.
Матрица смежностиА=аijnn орграфа (графа)G– это матрица, элементы которой определяются из условия:
Матрица инциденцийВ=bijnmорграфаG– это матрица, строки которой соответствуют вершинам, а столбцы – ребрам орграфа; элементы матрицы определяются следующим образом:
Матрица инциденцийВ=bijnmграфаG– это матрица, строки которой соответствуют вершинам, а столбцы – ребрам графа; элементы матрицы определяются следующим образом:
Для ребер, являющихся петлями, bij=2.
Маршрут – последовательность вершин, в которой каждые две соседние вершины являются смежными.
Маршрут, в котором начало и конец совпадают, – замкнутый.
Замкнутый маршрут в графе, в котором все ребра разные, называется циклом.
Незамкнутый маршрут в неографе, в котором все ребра разные, называется цепью.
Маршрут в орграфе, в котором все дуги разные, – путь.
Путь, в котором начало и конец совпадают, называется контуром.
Цепь с неповторяющимися вершинами – простая.
Цикл с неповторяющимися вершинами (за исключением начальной и конечной) называется простым.
Число ребер маршрута – его длина.
Между орграфами G(V,
X)с петлями, но
без кратных дуг, и бинарными отношениямиX существует
взаимно однозначное соответствие: пара
тогда и только тогда, когда в орграфеGесть дуга(a, b).
Матрица достижимости Т={tij}nnграфа (орграфа)G– это матрица, элементы которой определяются так:
Матрица сильной связностиS={sij}nnорграфаG– это матрица, элементы которой определяются так:
При этом считается, что вершина xjдостижима изxi, если либоxj=xi, либо существует путь, соединяющий хiсxj.
Отношение достижимости вершин графа (орграфа) является транзитивным и рефлексивным замыканием отношения смежности.
Элементы матрицы S можно определить с помощью элементов матрицы Т следующим образом:
.
Связанный граф (сильно связанный орграф) – граф, все вершины которого достижимы друг из друга.