1535
.pdfПример: На следующем рисунке представлены: а) - исходный граф, б) – граф после удаления вершины v3, в) - результат удаления ребра e2, г) –отождествления вершин v3 и v4, д) –стягивание ребра e1, е) – подразбиение ребра e2.
v3 |
|
e1 |
v4 |
|
v4 |
v3 |
e1 |
v4 |
|
e2 |
|
e3 |
|
e4 |
e3 |
e4 |
|
e3 |
e4 |
|
|
|
e5 |
|
e5 |
|
|
e5 |
|
v1 |
|
v2 |
v1 |
v2 |
v1 |
|
v2 |
||
|
а) |
в) |
|||||||
|
|
|
|
б) |
|
|
|
||
v5 |
|
e1 |
|
v5 |
|
v3 |
e1 |
v4 |
|
|
|
|
|
|
|
e8 |
|
|
|
|
|
e3 |
e4 |
|
e3 |
e4 |
e3 |
e4 |
|
e2 |
|
v6 |
|||||||
|
e5 |
|
e2 |
|
e7 |
e5 |
|
||
|
|
|
|
e5 |
|
|
|||
v1 |
|
г) |
v2 |
v1 |
v2 |
v1 |
е) |
v2 |
|
|
|
|
|
д) |
|
|
|
Рис. 14
51
5.7. Маршруты в графах
Маршрутом в графе G=(V,E) называется чередующаяся последовательность вершин и ребер (дуг) – v1, e1, v2, e2, ….,vn, en,vn+1, в которой любые два соседних элемента инциденты.
Маршрут, соединяющий вершины v1 и vn+1 можно также задать последовательностью из одних вершин v1, v2, v3,…,vn, vn+1 или последовательностью ребер e1, e2,…,en. Число n ребер (или дуг) в маршруте называется его длиной. Маршрут называется циклическим, если v1=vn+1.
Маршруты в неориентированных графах.
Маршрут в неорграфе называется цепью, если все его ребра различны. Цепь называется простой, если все её вершины, кроме возможно первой и последней, различны. Циклическая цепь называется циклом, а простая циклическая цепь – простым циклом.
Неорграф без циклов называется ациклическим графом. Минимальная из длин циклов неорграфа называется его обхватом.
Пример 1: Рассмотрим неорграф
1 2
3 |
4 |
5 |
6 |
7 8
Рис. 15 В данном примере наборы вершин: (1,2) ; (1,2,4,7) яв-
ляются простыми цепями,: (1,2,4,7,8,4) - непростая цепь, (1,2,4,7,8,4,2) – маршрут, который не является цепью, (1,2,4,8,7,4,1) – непростой цикл, (1,2,4,1) – простой цикл. Об-
хват графа равен 3.
52
Маршруты в ориентированных графах.
Маршрут ориентированного графа называется путем, если все его дуги различны.
Путь называется контуром, если v1=vn+1. Граф не имеющий контуров называется безконтурным. Вершина v называется достижимой из вершины u, если существует путь из u в v.
Пример 2: Рассмотрим ориентированный граф
2
4 5
1 3
Рис. 16 В данном примере наборы вершин (1,2,3,1) образуют
контур. Заметим, что здесь вершина 5 – достигается из любой другой вершины, а из вершины 5 не достигается ни одна из остальных вершин.
5.8. Связность в графах.
Неорграф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Граф называется связным, если соответствующий ему неорграф является связным. В данном случае соответствующий неориентированный граф получается из исходного графа путём замены всех его дуг рёбрами. Граф называется сильно связным, если для каждой пары различных вершин u и v существуют маршруты (u,v) и (v,u). Из этого определения следует, что любой связный неорграф является также сильно связным. Понятия связности и сильной связности распространяются также и на мультиграфы.
Отметим, что граф в примере 1 является сильно связным, а в приме2 – не сильно связный граф.
53
Пример 3. На следующем рисунке показан несвязный
граф.
6
2
3 4
5 7
1
Рис. 17 Всякий максимальный по включению сильно связный
подграф данного графа называется его сильно связной компонентой, или сильной компонентой связности.
В примере 3 граф имеет две сильно связных компоненты.
Связность и матрица смежности графа.
Теорема 1. Любой граф представляется в виде объединения непересекающихся (сильно) связных компонент. Разложение графа на (сильно) связные компоненты определяется однозначно.
Таким образом, множество вершин связных компонент, а также сильных компонент образуют разбиение множества вершин графа, причем число с(G) связных компонент графа G определяется однозначно.
Теорема 2. Если A матрица смежности графа G, то (i, j) элемент матрицы Ak=A·A·A··…·A (k раз), есть число (vi, vj) маршрутов длины k.
Следствие 1. В графе G мощности n тогда и только тогда существует маршрут (vi, vj) , причем vi ≠vj , когда (i, j) – элемент матрицы A+A2+ A3+ A4+…+ An-1 не равен нулю.
Следствие 2. В графе G мощности n тогда и только тогда существует цикл, содержащий вершину vi когда (i, i) – элемент матрицы A+A2+ A3+ A4+…+ An-1+An не равен нулю.
54
Пример. При помощи матрицы смежности определим существование всевозможных (1, 3) - маршрутов в графе, изображенном на рисунке.
1 |
2 |
3 |
|
|
|
|
|
|
4 |
|
|
|
|
|
|
Рис. 18 |
По графу находим матрицу смежности A: |
||||||
|
0 |
0 |
0 |
1 |
|
|
|
|
|
0 |
1 |
1 |
|
A= |
1 |
|
||||
|
0 |
1 |
0 |
0 |
. |
|
|
|
|
||||
|
|
1 |
1 |
0 |
0 |
|
|
|
|
|
Её элемент (1,3)=0, следовательно. (1, 3) маршрутов |
||||||||||||||||||||
длины 1 в графе нет. Затем находим: |
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
0 |
0 |
0 |
1 |
|
0 0 0 |
1 |
|
1 |
1 |
0 |
0 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
= |
1 |
0 |
1 |
1 |
. |
1 0 1 |
1 |
= |
1 |
2 |
0 |
1 |
|||||||
|
A |
|
0 |
1 |
0 |
0 |
|
|
0 1 0 |
0 |
|
|
1 |
0 |
1 |
1 |
. |
||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
1 |
1 |
0 |
0 |
|
|
|
1 1 0 |
0 |
|
|
|
1 |
0 |
1 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
В этой матрице элемент (1,3)=0, т.е. (1, 3) маршрута |
||||||||||||||||||||
длины 2 в графе нет. Далее |
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
1 |
1 |
0 |
0 |
|
0 0 0 |
1 |
|
1 |
0 |
1 |
2 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
2 |
= |
1 |
2 |
0 |
1 |
· |
1 0 1 |
1 |
= |
3 |
1 |
2 |
3 |
|||||||
A |
= A ·A |
|
1 |
0 |
1 |
1 |
|
|
0 1 0 |
0 |
|
|
1 |
2 |
0 |
1 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
1 |
0 |
1 |
2 |
|
|
|
1 1 0 |
0 |
|
|
|
2 |
3 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
55 |
|
|
|
|
|
|
|
|
|
|
Eё элемент (1, 3)=1, т.е. существует ровно один (1, 3) - маршрут длины 3. Этот маршрут определяется набором вер-
шин (1, 4, 2, 3)
Эту последовательность вершин можно найти на основе перемножения матрицы смежности: Элемент (1, 3) матрицы A3 получается при перемножении элемента (1, 2) матрицы A2 на элемент (2, 3) матрицы A. В свою очередь элемент (1, 2) матрицы A2 образуется при перемножении элемента (1, 4) матрицы A на элемент (4, 2) матрицы A, т.е. следовательно, двигаясь от 1 к 3 за 3 шага, получаем маршрут
(1,4, 2, 3).
В матрице A3 элемент (4, 2) равен 3, это значит, что существуют три (4,2) маршрута длины 3 : (4, 1, 4, 2), (4, 2, 4, 2), (4, 2, 3, 2).
5.9. Матрица взаимодостижимости.
Образуем из матрицы E+ A+A2+…+ An=(bi, j) матрицу С порядка n по правилу:
1, |
если |
b |
|
0 |
|
|
i, j |
|
. |
сi, j= |
если |
b |
|
|
0, |
j |
0 |
||
|
|
i, |
|
Полученная матрица С называется матрицей связности, если G – неорграф и матрицей достижимости, если G – орграф.
Элемент этой матрицы сi, j=1 тогда и только тогда, когда в графе есть (vi, vj) – маршрут (i≠j).
Матрицей контрдостижимости называется матрица Q=(qi, j), элементы которой:
|
qi, |
j |
= |
1, |
есливершина |
vi достижимаиз |
вершины vj, |
|
впротивном |
случае. |
|
0, |
|
||
|
|
56 |
|
Отметим, что Q=CT. Матрицы достижимости и контрдостижимости используются для нахождения сильных компонент графа. Для этого используется матрица взаимодостижимости (сильных компонент) S C Q, где символ означает поэлементное произведение матрицС и Q, т.е. sij=cij·qij.
Элемент sij=1 тогда и только тогда, когда вершины vi и vjвзаимодостижимы. Это означает, что они находятся в одной сильной компоненте. Следовательно, сильная компонента, содержащая вершину vi, состоит из тех элементов vij, для которых sij=1.
Пример. Для графа, изображённого ниже, определим матрицы достижимости, контрдостижимости и взаимодостижимости
2 |
4 |
|
|
|
5 |
|
|
|
1 |
3 |
|
|
|
|
|
|
|
|
Рис. 19 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
||||||
|
|
|
|
1 |
1 |
1 |
1 |
|
|
|
1 |
|
|||||
Матрица достижимости C= |
|
1 |
1 |
1 |
1 |
1 |
. |
|
|
|
|
|
0 |
0 |
1 |
1 |
|
|
|
0 |
|
|||||
|
|
|
0 |
0 |
0 |
0 |
1 |
|
|
|
|
|
57
|
|
|
1 |
|
1 |
1 |
0 |
0 |
|
||
|
|
|
|
|
|
1 |
1 |
0 |
|
|
|
|
|
|
1 |
|
0 |
|
|||||
|
T |
= |
|
1 |
|
1 |
1 |
0 |
0 |
|
|
Матрица контрдостижимости Q=C |
|
|
|
|
|||||||
|
|
|
|
|
1 |
1 |
1 |
|
|
||
|
|
|
1 |
|
0 |
|
|||||
|
|
|
|
1 |
|
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
1 |
1 |
1 |
0 |
0 |
||
|
|
|
|
|
|
|
1 |
1 |
0 |
|
|
|
|
|
|
|
1 |
0 |
|||||
Матрица взаимодостижимости |
S C Q |
= |
|
1 |
1 |
1 |
0 |
0 |
|
||
|
|
|
|
|
|
0 |
0 |
1 |
|
|
|
|
|
|
|
|
0 |
0 |
|||||
|
|
|
|
|
|
0 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
По второй строке матрицы S находим, что сильная компонента, содержащая вершину 2 состоит из вершин (1, 2, 3).
5.10. Деревья
Свободные деревья.
Деревом называется связный граф без циклов (конту-
ров).
Несвязный граф без циклов (контуров) называется лесом. Компоненты связности леса являются деревьями.
Подграф G1=(V1, E1) графа G=(V, E) называется остовным деревом в графе G=(V, E), если G1=(V1, E1) – дерево и V1=V.
Дерево – это минимальный связный граф, т.к. при удалении хотя бы одного ребра (дуги) он теряет связность. Неориентированное дерево называется свободным.
Например: 1) Диаграммы всех различных свободных деревьев с 5-ю вершинами:
58
Рис. 20 2) Диаграммы всех различных свободных деревьев с
6-ю вершинами:
Рис. 21
Лемма 1. Если граф G=(V, E)связный и ребро(u, v)содержится в некотором цикле графа G, то при удалении этого ребра получится новый связный граф.
Доказательство: При удалении ребра (u, v), вершины u и v останутся в одной и той же связной компоненте, т.к. они остаются связными за счет оставшейся части цикла.
Теорема 1. Любой связный граф содержит хотя бы одно остовное дерево.
Доказательство: Если в графе G нет циклов, то G является искомым остовным деревом, если в G есть цикл, то удалим из G какое-нибудь ребро, входящее в цикл. В результате этого получается некоторый подграф G1. По лемме 1 G1
– связный граф. Если в графе G1 нет циклов, то G1 есть искомое остовное дерево. В противном случае процесс продолжается. Этот процесс должен завершиться, т.к. Е – конечное множество.
59
Лемма 2. Если к связному графу добавить новое ребро на тех же вершинах, то в нём появится цикл.
Доказательство: Пусть G=(V, E) – связный граф. Пусть u V, v V, (u, v) E. Т.к. G – связный граф, то в нем есть цепь от v к u, при этом она является простой цепью соединяющей v и u. Поэтому во вновь полученном графе с добавленным ребром (u, v) имеется цикл C(u, v).
Лемма 3. Пусть в графе G=(V, E) имеется n вершин и m ребер. Тогда в G не менее n-m связных компонент. Если при этом в графе G нет циклов, то он состоит ровно из n-m связных компонент.
Доказательство: Пусть к некоторому графу H, содержащему вершины u и v добавляется ребро (u, v). Тогда, если u и v лежат в разных связных компонентах графа H, то число связных компонент уменьшается на единицу. Если u и v лежат в одной связной компоненте графа H, то число связных компонент не уменьшится. Таким образом, число связных компонент при добавлении ребра уменьшается не более чем на единицу. Значит, при добавлении m ребер, число связных компонент уменьшается не более чем на m. Т.к. граф G, можно получить из графа G1=(V,Ø), добавлением m ребер, то в графе G не менее n-m связных компонент. Пусть далее в графе G нет циклов, и пусть в процессе получения G из G1 добавляется ребро (u, v). Если бы u и v лежали в одной связной компоненте, то в G, согласно лемме 2, возникал бы цикл. Следовательно, u и v лежат в разных связных компонентах и при добавлении ребра (u, v) число связных компонент уменьшается ровно на 1. Следовательно, G состоит ровно из n-m компонент.
Теорема 2. О различных определениях свободного дерева. (Свойства свободных деревьев).
Следующие пять определений эквивалентны:
1)G – свободное дерево
2)G – без циклов и m=n-1
60