Теория графов. Основные понятия и определения
Графом G=(V,E) (или G=(p,q)) называется пара множеств, где V – непустое, конечное множество, состоящее из р элементов (вершин графа G), E – множество неупорядоченных пар элементов q (ребра).
Отрезки, соединяющие вершины, называются дугами, если указано, какая вершина является начальной, и ребрами, если ориентация не указана.
Граф, состоящий из дуг, называется ориентированным (оргрфом). Граф образованный ребрами – неориентированный.
Если Е – пустое множество, то граф G – пустой граф.
Мультиграф – между двумя вершинами можно нарисовать 2 и более ребра.
Если имеются вершины V1 и V2 и ребро е образовано ими, то говорят, что ребро е инцидентно вершинам V1 и V2. V1 и V2 – смежные.
Степенью вершины называется число ребер инцидентных данной вершине (количество выходящих из нее ребер).
Вершина, степень которой равна 1, называется висящей.
Вершина, степень которой равна 0, называется изолированной.
Последовательность ребер V0, V1… называется маршрутом.
Если в маршруте не указаны ребра, то такой маршрут называется цепью.
Если V0=Vn, то цепь называют циклом.
Если в цепи не повторяются вершины, то такая цепь называется простой.
Граф называется связным, если любая пара его вершин соединена маршрутом.
Если в связном графе имеется цикл, проходящий через все ребра графа, то граф называется Эйлеровым.
Связный граф, не имеющий циклов – дерево.
Способы задания графов
1. Матрица смежности вершин графа – квадратная матрица n-ного порядка, где n – число вершин. Строки и столбцы матрицы соответствуют вершинам графа. Элементы рij равны числу дуг, направленных из i в j. Если орграф состоит из однократных дуг, то элементы матрицы равны либо 0, либо 1. В случае неориентированного графа ему вместе с ребром (Xi Xj) принадлежит ребро (Xj Xi).
2. Матрица смежности дуг – квадратная матрица m-ного порядка, m – число дуг. Строки и столбцы матрицы соответствуют дугам графа. Элементы qij равны 1, если дуга уi непосредственно предшествует дуге yj, и 0 в остальных случаях.
3. Матрица смежности ребер неориентированного графа – матрица m-ного порядка, m – число ребер с элементами qij = 1, если ребра yi yj имеют общую вершину, и 0 в остальных случаях.
4. Матрица инцидентности орграфа – прямоугольная матрица, размерности nхm, строки которой соответствуют вершинам, а столбцы дугам орграфа. Элементы rij равны 1, если дуга yj исходит из i-той вершины и равны 0, если дуга не инцидентна i-той вершине.
В случае неориентированного графа будет или 0, или 1.
U5
U4
6
U7
X5
X1
X2
X3
X4
X6
U9
U8
U3
U2
U1
1.
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
0 |
1 |
0 |
0 |
0 |
0 |
|
x2 |
0 |
0 |
0 |
1 |
0 |
0 |
|
x3 |
1 |
1 |
0 |
1 |
0 |
0 |
|
x4 |
0 |
0 |
0 |
0 |
0 |
1 |
|
x5 |
1 |
0 |
1 |
0 |
0 |
1 |
|
x6 |
0 |
0 |
0 |
0 |
0 |
0 |
2.
|
|
U1 |
U2 |
U3 |
U4 |
U5 |
U6 |
U7 |
U8 |
U9 |
|
U1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
U2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
U3 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
|
U4 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
U5 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
U6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
U7 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
U8 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
U9 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
4.
|
|
U1 |
U2 |
U3 |
U4 |
U5 |
U6 |
U7 |
U8 |
U9 |
|
X1 |
1 |
-1 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
|
X2 |
1 |
0 |
0 |
0 |
-1 |
1 |
0 |
0 |
0 |
|
X3 |
0 |
0 |
-1 |
1 |
1 |
0 |
1 |
0 |
0 |
|
X4 |
0 |
0 |
0 |
0 |
0 |
-1 |
-1 |
0 |
1 |
|
X5 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
|
X6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
-1 |