Методическое пособие 598
.pdfG х6
х1 х5
х7
х2 |
х4 |
|
х3 |
Рис. 43. Неорграф
Определим кличество всех остовов графа G , используя теорему Кирхгофа.
Матрица Кирхгофа B bij , i, j 1, n,
1, xi и x j смежны,
bij 0, xi и x j смежны и i j, 1, n,
P xi , i j.
|
|
х1 |
х2 |
х3 х4 х5 х6 |
|
х7 |
||||
х1 |
2 -1 0 |
0 |
-1 0 |
0 |
||||||
х |
|
-1 3 |
-1 0 |
-1 0 |
0 |
|
||||
2 |
|
|
|
|
|
|
|
|
|
|
х |
|
0 |
-1 2 -1 0 |
0 |
0 |
|
||||
3 |
|
|
|
|
|
|
|
|
|
|
B х4 |
0 |
0 |
|
-1 2 -1 0 |
0 |
|
||||
х |
|
-1 -1 |
0 |
-1 4 |
-1 |
0 |
|
|||
5 |
|
|
|
|
|
|
|
|
|
|
х6 |
|
0 |
0 |
|
0 |
0 |
-1 2 |
-1 |
||
|
|
0 |
0 |
|
0 |
0 |
0 |
-1 |
1 |
|
х7 |
|
|
131
|
|
1 |
0 |
1 |
0 |
0 |
|
|
3 |
|
|||||
|
1 |
2 |
1 |
0 |
0 |
0 |
|
A 1 1 1 |
0 |
1 |
2 |
1 0 |
0 |
|
|
11 |
1 |
0 |
1 |
4 |
1 |
0 |
по 6 ой строке |
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
2 |
1 |
|
|
0 |
0 |
0 |
0 |
1 |
1 |
|
|
|
|
1 |
0 |
1 |
0 |
|
|
|
3 |
|
||||
|
|
1 |
2 |
1 |
0 |
0 |
|
1 1 6 5 |
0 |
1 |
2 |
1 |
0 |
|
|
|
|
1 |
0 |
1 |
4 |
0 |
|
|
|
0 |
0 |
0 |
1 |
1 |
|
|
1 |
0 |
1 |
0 |
|
|
|
|
3 |
|
|
||||
|
1 |
2 |
1 |
0 |
0 |
|
|
1 1 6 6 |
0 |
1 |
2 |
1 |
0 |
|
|
|
1 |
0 |
1 |
4 |
1 |
|
|
|
0 |
0 |
0 |
1 |
2 |
|
|
|
|
|
|
|
1 |
0 |
1 |
|
|
|
|
|
|
3 |
|
||||
|
1 1 5 5 |
1 |
2 |
|
1 |
0 |
|
||
по 5 ой строке |
|
|
|
0 |
1 |
2 |
1 |
|
|
|
|
|
|
1 |
0 |
|
1 |
4 |
|
|
|
1 |
0 |
|
0 |
|
|
|
|
|
|
3 |
|
|
|
|
|||
1 1 5 4 |
1 |
2 |
1 |
|
0 |
|
|
|
|
|
|
0 |
1 |
2 |
|
0 |
|
|
|
|
|
1 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
132
|
3 1 0 |
1 |
|
|
3 1 |
0 1 |
|
|
3 |
1 0 0 |
|
|||||||||||||
|
|
|
|
|
|
|||||||||||||||||||
2 1 5 5 |
1 |
2 1 0 |
|
|
1 2 |
1 |
0 |
|
1 |
2 1 |
0 |
|
||||||||||||
|
0 1 2 |
1 |
|
|
0 1 |
2 1 |
|
|
0 |
1 2 0 |
|
|||||||||||||
|
1 |
0 1 4 |
|
|
1 0 |
1 |
4 |
|
|
1 |
0 1 |
1 |
|
|||||||||||
|
|
|
|
|
2 |
|
1 |
0 |
|
|
|
|
|
|
1 |
1 |
0 |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
3 1 1 1 |
1 |
2 1 |
1 1 1 2 |
0 |
2 1 |
|
|
||||||||||||||||
по 1 ой строке |
|
|
|
0 |
|
1 |
4 |
|
|
|
|
|
|
1 |
1 |
4 |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
1 |
2 |
|
1 |
|
|
|
|
3 |
1 |
0 |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
1 1 1 4 |
0 |
1 |
|
2 |
|
1 1 4 4 |
1 |
2 1 |
|
|
|
|||||||||||||
|
|
|
1 |
0 |
|
1 |
|
|
|
|
0 |
1 |
2 |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 16 2 4 1 4 1 12 3 2 8 1 1 11.
Следовательно, у исходного графа имеется 11 разных остовов, они представлены на рис. 44.
Число (G) m n k, где m – количество рёбер, n –
количество вершин, k – количество компонент связности,
именуется цикломатическим числом или циклическим рангом графа G, число (G) n k – коциклическим рангом или корангом.
(G) равно количеству рёбер, составляющих всякий
остов графа G.
(G) (G) m n k n k m.
Теорема. Количество рёбер любого связного неориентированного графа G, которые нужно вычеркнуть для построения остова, не зависит от порядка их отбрасывания и равно циклическому рангу (G) графа G.
Следствие 1. Для того, чтобы неориентированный граф был лесом, необходимо и достаточно, чтобы G 0.
133
Рис. 44. Остовы неорграфа
134
Следствие 2. Для того, чтобы неориентированный граф содержал только один цикл, необходимо и достаточно,
чтобы G 1.
Задача об остове экстремального веса.
Предположим, что G S,U , – связная сеть. В прикладных задачах нередко возникает задача о нахождении остова графа G минимального веса. В частности, G S,U ,
является моделью железнодорожной сети, соединяющей пункты х1, х2 ,..., хn S , а (хi , х j ) – расстояние между пунк-
тами xi и x j . Надо построить сеть телеграфных линий вдоль железнодорожной сети таким образом, чтобы все пункты х1, х2 ,..., хn были связаны между собой телеграфной сетью и общая длина линий телеграфной сети была минимальной.
Алгоритм Прима (алгоритм ближайшего соседа) построения экстремального остовного дерева.
Предположим, что
S S, S S, S S S , S S , таким образом, S и S
разделяют совокупность узлов сети на два непересекающиеся
подмножества. Введём пошаговое расстояние между |
множе- |
||||||
ствами S и S |
по формуле: |
j |
|
|
|||
|
i j |
i |
|
|
|||
d(S , S ) min |
(х , х |
) : х |
S , х |
|
S , |
(38) |
|
здесь (хi , хj ) – |
дуга, соединяющая вершины xi и x j . |
|
|||||
Шаг 1. Присвоение начальных значений. Принимают |
|||||||
S S \ S , U . |
|
|
|
|
|
|
|
Шаг 2. Обновление данных. Ищется ребро (хi , хj ) , у |
|||||||
которого xi S , xj |
S , и вычисляется расстояние d(S , S ) |
по формуле (3.5.1). Принимают
S S U хj , S S \ S ,U U U (хi , хj . 135
Шаг 3. Проверка на завершение. В том случае, когда S S, алгоритм заканчивает работу и G S ,U – требуе-
мый остов. В противном случае возвращаемся к шагу 2. Замечание. В том случае, когда надо построить наи-
больший по весу остов, нужно формуле (15) надо min поменять на max.
Пример. Выделить остов минимального веса в сети, определяемой весовой матрицей .
|
|
|
x1 |
x2 |
x3 x4 x5 |
x6 |
|
||
|
x1 |
|
5 |
10 |
14 |
|
|
||
|
x |
|
5 |
|
5 |
6 |
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
x |
10 |
5 |
|
7 |
8 |
9 |
|
|
|
3 |
|
|
|
|
|
|
|
. |
|
x4 |
14 |
6 |
7 |
4 |
|
|||
|
x |
|
|
|
8 |
4 |
|
12 |
|
|
5 |
|
|
|
|
|
|
|
|
|
x |
|
9 |
12 |
|
||||
|
6 |
|
|
|
|
|
|
|
|
Решение. Изобразим по этой матрице сеть. Поскольку– симметрическая матрица, то имеем неориентированный граф.
|
х2 |
8 |
|
х |
|
|
|
|
|
|
5 |
|
6 |
|
|
|
|
|
5 |
|
|
4 |
12 |
х1 |
14 |
|
|
|
|
|
|
|
|
||
7 |
х |
|
|
|
|
|
4 |
|
|
||
|
10 |
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
х6 |
|
|
х3 |
|
|
|
|
|
|
|
|
|
Рис. 45. Неорсеть
Шаг 1. S x1 , S xi , i 2, 6 , U .
136
Первая итерация. Шаг 2.
d S , S x1, x2 5, S x1, x2 , S xi , i 3, 6 , U x1, x2 .
Шаг 3. S S, возврат к шагу 2.
Вторая итерация. Шаг 2.
d (S , S ) ( х2 , х3 ) 5, S х1, х2 , х3 , S х4 , х5, х6 , U (х1, х2 ),( х2 , х3 ) .
Шаг 3. S S, возврат к шагу 2.
Третья итерация. Шаг 2.
d (S , S ) ( х2 , х4 ) 6, S х1, х2 , х3, х4 , S х5, х6 , . U ( х1, х2 ),( х2 , х3 ),( х2 , х4 ) .
Шаг 3. S S, возврат к шагу 2.
Четвёртая итерация. Шаг 2.
d (S , S ) ( х4 , х5 ) 4, S х1, х2 , х3, х4 , х5 , S х6 , U ( х1, х2 ),( х2 , х3 ),( х2 , х4 ),( х4 , х5 ) .
Шаг 3. S S, возврат к шагу 2.
Пятая итерация. Шаг 2.
d (S , S ) ( х3, х6 ) 9, S х1, х2 , х3, х4 , х5, х6 , S , U (х1, х2 ),( х2 , х3 ),( х2 , х4 ),( х4 , х5 ),( х3, х6 ) .
Шаг 3. S S.
Таким образом, построен остов G (S ,U ) с весом
(G ) 5 5 6 4 9 29.
137
|
|
х2 |
|
|
х5 |
||
|
5 |
|
|
6 |
|
4 |
|
|
|
|
|
х4 |
|
||
|
|
|
|
|
|
||
х1 |
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
х6 |
|
|
|
х |
3 |
|
|
||
|
|
|
|
|
|
||
|
|
|
|
Рис. 46. Остов неорсети |
|||
Фундаментальные циклы. |
|
|
|||||
Предположим, что G S, U |
– неориентированный |
граф, имеющий n вершин, m рёбер и к компонент связности,
G – остов графа G, |
содержащий |
* G n k рёбер |
u1, u2 , ..., un k . Данные рёбра называются |
ветвями остова G . |
|
Другие m n k рёбер |
1, 2 , ..., m n k , |
не содержащиеся в |
G , именуются хордами остова G . |
|
|
Согласно определению дерева, если остов G дополнить |
некоторой хордой i , то в новом графе G i будет единственный цикл Ci , содержащий хорду i и определённые ветви остова G . Цикл Ci называется фундаментальным циклом графа G по отношению к хорде i остова G . Совокупность C C1,C1,...,Cm n k всех фундаментальных циклов по
отношению к хордам остова G именуется фундаменталь-
ным множеством циклов графа G по отношению к остову
G . Card C G m n k.
Предположим, что w1, w2 ,..., wm последовательность1, 2 , ..., m n k , u1, u2 , ..., un k всех рёбер графа G . Фундамен-
138
тальному циклу Ci отвечает вектор C Ci1, Ci 2 , ..., Cim , построенный таким образом:
C 1, если wi Ci , ij 0, если wi Ci .
В этом случае фундаментальное множество циклов C определяется матрицей фундаментальных циклов
|
|
|
|
c11 |
c12 |
... |
c1m |
|
|
|
|
|
c21 |
c22 |
... |
c2m |
|
C |
* |
|
|
|
||||
|
... |
... |
... |
... |
|
|||
|
|
|
||||||
|
|
|
|
|
c |
... |
c |
|
|
|
|
c |
|
||||
|
|
|
|
G ,1 |
G ,2 |
|
G ,m |
|
|
|
1 |
0 |
... |
0 |
c1, G 1 |
c1, G 2 |
... |
c1m |
|
|
|
|
|
|
|
0 |
1 |
... |
0 |
c |
c |
... |
c2m |
|
|
вида: |
C* |
|
|
|
|||||||||
|
|
|
|
|
2, G 1 |
2, G 2 |
|
|
|
||||
|
|
|
... ... ... ... |
... |
... |
... |
... |
|
|
||||
|
|
|
|
0 |
0 |
... |
1 |
c |
c |
... |
c |
|
|
C1* | C2* |
|
|
|
|
|
|
G , G 1 |
G , G 1 |
|
G ,m |
|
||
, |
|
здесь |
C1* |
– |
единичная матрица порядка G – |
||||||||
заключает информацию |
только о хордах фундаментальных |
циклов Ci .
Пример. Определить матрицу фундаментальных циклов графа G:
|
|
5 |
|
|
6 |
|
|
|
7 |
|
4 |
1 |
2 |
|
3 |
|
|
||
|
|
|
|
|
|
8 |
10 |
|
|
|
9
Рис. 47. Неорсеть
139
Решение. В нашем случае m 10, n 7, k 1. Поскольку цикломатическое число равно G 10 7 1 4, то для
построения остова G нужно вычеркнуть 4 ребра. Предположим, что эти рёбра 1, 2, 3 и 4. Получим остов G :
Рис. 48. Остов неорсети
Другие рёбра графа G обозначим цифрами от 5 до 10. Из рис.
47 следует, что фундаментальный цикл C1 , |
отвечающий хор- |
|||||||||||
де 1, содержит рёбра 1, 6, 7, 8; цикл C2 |
– рёбра 2, 7, 9; цикл |
|||||||||||
C3 – рёбра 3, 5, 7, цикл C4 |
– |
рёбра 4, 5, 7, 10. Таким образом, |
||||||||||
C* имеет вид: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 2 |
3 |
4 5 |
6 |
7 |
8 |
9 |
10 |
|||
C |
1 |
|
|
|
|
|
|
0 |
||||
0 0 |
0 |
0 |
1 |
1 |
1 |
0 |
||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
C* C2 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
. |
|
C |
|
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
3 |
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
|
C |
|
|
||||||||||
4 |
|
|
|
|
|
|
|
|
|
|
|
|
140