Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.12.2023
Просмотров: 524
Скачиваний: 6
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
118
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
Информация о структуре графа может быть задана матрицей бинарного отношения. Пусть G = hM; Ri — граф, в котором множество вершин имеет n
элементов: M = {a
1
, a
2
, . . . , a
n
}. Матрицей смежности A
G
= (A
ij
) графа G
называется матрица порядка n, определенная следующим образом:
A
ij
(
1,
если (a
i
, a
j
) ∈ R,
0,
если (a
i
, a
j
) /
∈ R.
Если A
ij
= 1, то вершина a
j
называется последователем вершины a
i
,
а a
i
— предшественником a
j
. Вершины a
i
и a
j
называются смежными, если
A
ij
= 1 или A
ji
= 1.
Если G — мультиграф, то в матрице смежности A
G
элемент A
ij
по опреде- лению равен числу дуг, исходящих из вершины a
i
и заходящих в вершину a
j
(i, j ∈ {1, . . . , n}).
Пример 4.1.4. Граф G, изображенный на рис. 4.6, имеет матрицу смежности
•
•
•
•
•
a
5
a
1
a
2
a
3
a
4
-
¡
¡
¡
ª
m m
Рис. 4.6
A
G
=
1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0
. ¤
Отметим, что если G — неорграф, то матрица смежности A
G
симметрична, т. е. не меняется при транспонировании:
A
T
G
= A
G
Петлей в графе G называется дуга, соединяющая вершину саму с собой.
Если G — граф без петель, то в матрице смежности A
G
по главной диагонали стоят нулевые элементы:
A
G
=
0 0
∗
∗
0
.
4.1. ВИДЫ И СПОСОБЫ ЗАДАНИЯ ГРАФОВ
119
Пусть
G
1
= hM
1
; R
1
i,
G
2
= hM
2
; R
2
i
—
графы,
в которых
M
1
= {a
1
, . . . , a
n
}, M
2
= {b
1
, . . . , b
n
}. Если ϕ — изоморфизм графов G
1
и G
2
,
действующий по правилу ϕ(a
i
) =
1 ... 11 12 13 14 15 16 17 18 ... 29
b
i
, i = 1, . . . , n, то матрицы смежности A
G
1
и A
G
2
совпадают. В общем случае справедлива
Теорема 4.1.1. Графы изоморфны тогда и только тогда, когда их мат-
рицы смежности получаются друг из друга одновременными перестанов-
ками строк и столбцов (т. е. одновременно с перестановкой i-й и j-й строк
переставляются i-й и j-й столбцы). ¤
Согласно этой теореме граф восстанавливается однозначно, с точностью до изоморфизма, по своей матрице смежности.
В мультиграфе G = hM, U, P i дуга u ∈ U называется инцидентной вер-
шине a ∈ M, если (a, u, b) ∈ P или (b, u, a) ∈ P для некоторого b ∈ M .
Если M = {a
1
, . . . , a
m
}, U = {u
1
, . . . , u
n
}, то матрицей инцидентности
B
G
= (B
ij
) мультиграфа G называется матрица размера m×n, определяемая по следующему правилу:
B
ij
1,
если дуга u
j
исходит из вершины a
i
;
−1, если дуга u
j
заходит в вершину a
i
и u
j
не является петлей;
0
— в противном случае.
Пример 4.1.5. Мультиграф G, изображенный на рис. 4.7, имеет матрицу инцидентности
•
•
•
¾
l
®
U
µ
R
*
a
1
a
3
a
2 1
2 3
4 5
6
Рис. 4.7
B
G
=
−1 −1 0 0
0 0
1 1 1 1 −1 1
0 0 0 −1 1 −1
. ¤
Мультиграфы G = hM, U, P i и G
0
= hM
0
, U
0
, P
0
i
называются изоморфными, если существуют биекции
ϕ: M ↔ M
0
и ψ: U ↔ U
0
такие, что (a, u, b) ∈ P то- гда и только тогда, когда (ϕ(a), ψ(u), ϕ(b)) ∈ P
0
Аналогично теореме 4.1.1. справедлива
Теорема 4.1.2. Мультиграфы G и G
0
изоморфны тогда и только
тогда, когда их матрицы инцидентности получаются друг из друга неко-
торыми перестановками строк и столбцов. ¤
120
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
•
•
•
•
Q
Q
Q
Q
Q
Q¡
¡
¡
¡
Q
Q
Q
Q
Q
Q
681
a
4
Павлодар
a
3
Кемерово
a
2
Новосибирск
Омск a
1 413 274 589
Рис. 4.8
Во многих задачах требуется дополнительная информация о верши- нах и ребрах, например, о расстоянии между населенными пунктами в слу- чае, когда граф представляет собой сеть дорог, или о времени прохождения сигнала от одного узла связи к другому и т. д. В таких задачах используются взвешенные графы.
Пусть S
M
, S
R
— множества меток. Пометкой или распределением меток
графа G = hM; Ri называется пара функций f : M → S
M
(распределение
меток вершин), g: R → S
R
(распределение меток дуг). Четверка hM, R, f, gi
называется взвешенным или помеченным графом. Для вершины a ∈ M
элемент f (a) называется весом вершины a, а для дуги u ∈ R элемент g(u) —
весом дуги u. Часто бывают помеченными только вершины (в этом случае
g = const) или дуги (в этом случае f = const).
Пример 4.1.6. Пусть M = {a
1
, a
2
, a
3
, a
4
}, R = [a
1
, a
2
] ∪ [a
2
, a
3
] ∪ [a
1
, a
4
]∪
∪[a
2
, a
4
], f : M → C, где C — множество городов, g: R → ω, f (a
1
) = Омск,
f (a
2
) = Новосибирск, f (a
3
) = Кемерово, f (a
4
) = Павлодар, g([a
1
, a
2
]) = 681,
g([a
2
, a
3
]) = 274,
g([a
1
, a
4
]) = 413,
g([a
2
, a
4
]) = 589.
Помеченный граф
hM, R, f, gi изображен на рис. 4.8 и представляет собой схему автомобильных дорог с указанием их протяженности. ¤
Информацию о весах дуг во взвешенном графе можно представлять в ви- де матрицы весов W = (w
ij
), где w
ij
— вес дуги (a
i
, a
j
), если дуга (a
i
, a
j
)
существует, а для несуществующих дуг веса обычно помечают нулем или знаком ∞ в зависимости от приложений. В примере 4.1.6 матрица весов имеет вид
W =
0 681
∞
413 681 0
274 589
∞
274 0
∞
413 589
∞
0
.
4.2. ПОДГРАФЫ И ЧАСТИ ГРАФА. ОПЕРАЦИИ НАД ГРАФАМИ
121
Если граф G = hM ; Ri является разреженным, т. е. число дуг |R| до- статочно мало по сравнению с числом вершин |M|, то более эффектив- ным, чем с помощью матрицы смежности, является представление дуг гра- фа посредством списка дуг. Этот список задается двумя наборами
m = (m
1
, m
2
, . . . , m
|R|
) и n = (n
1
, n
2
, . . . , n
|R|
), где (a
m
i
, a
n
i
) — i-я дуга графа G.
Пример 4.1.7. Орграф, изображенный на рис. 4.6, представляется сле- дующим списком дуг: m = (1, 1, 2, 3, 4, 4), n = (1, 2, 3, 4, 3, 4). Для пред- ставления рассматриваемого графа матрицей смежности требуется 5 2
= 25
элементов, а списком дуг — только 6 · 2 = 12 элементов. ¤
Другим представлением графа, удобным при работе с графами, в кото- рых удаляются или добавляются вершины, является структура смежно-
сти, получаемая составлением для каждой вершины a списка номеров ее
последователей, т. е. номеров вершин b, для которых имеется дуга (a, b).
Пример 4.1.8. Орграф, изображенный на рис. 4.6, представляется сле- дующей структурой смежности:
Вершины
Списки последователей
1:
1, 2 2:
3 3:
4 4:
3, 4 5:
§ 4.2.
Подграфы и части графа.
Операции над графами
Граф G
0
= hM
0
; R
0
i называется подграфом графа G = hM; Ri, если
M
0
⊆ M и R
0
= R ∩ (M
0
)
2
. Граф G
0
называется частью графа G, если
M
0
⊆ M и R
0
⊆ R ∩ (M
0
)
2
Пример 4.2.1. Граф G
0
= h{1, 2, 3}; [1, 2] ∪ [2, 3] ∪ {(1, 3)}i (рис. 4.9б )
является подграфом графа G = h{1, 2, 3, 4}; [1, 2]∪[1, 4]∪[2, 3]∪[3, 4]∪{(1, 3)}i
(рис. 4.9а), а граф G
00
= h{1, 2, 3}; [1, 2] ∪ {(3, 2)}i (рис. 4.9в) — частью графа G. ¤
122
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
•
•
•
•
-
¡
¡
¡
@
@
@
¡
¡
¡
@
@
@
1 1
1 3
3 3
2 2
2 4
•
•
•
-
¡
¡
¡
@
@
@
•
•
•
¡
¡
¡
@
@
@
I
а
б
в
Рис. 4.9
Рассмотрим некоторые основные операции, производимые над графами.
Операцией добавления к графу G = hM; Ri вершины a образуется граф
hM ∪ {a}; Ri. Операция добавления дуги (a, b) к графу G состоит в образо- вании графа hM ∪ {a, b}; R ∪ {(a, b)}i. Под операцией удаления дуги (a, b)
из графа G понимается операция, заключающаяся в удалении пары (a, b)
из множества дуг R, в результате получается граф hM; R \ {(a, b)}i. Опера-
ция удаления вершины a из графа G заключается в удалении вершины a
вместе с инцидентными ей дугами:
hM \ {a}; R \ {(b, c) | b = a или c = a}i.
Операция отождествления вершин a и b графа G = hM; Ri состоит в удале- нии из графа G вершин a и b и присоединении новой вершины a
0
, дуг (a
0
, c),
если (a, c) ∈ R или (b, c) ∈ R, и дуг (c, a
0
), если (c, a) ∈ R или (c, b) ∈ R:
h(M \ {a, b}) ∪ {a
0
}; (R \ {(c, d) | c = a, или d = a, или c = b, или d = b})∪
∪{(a
0
, c) | (a, c) ∈ R или (b, c) ∈ R, c /
∈ {a, b}} ∪ {(c, a
0
) | (c, a) ∈ R
или (c, b) ∈ R, c /
∈ {a, b}} ∪ {(a
0
, a
0
) | найдутся c, d ∈ {a, b}, где (c, d) ∈ R}i.
Говорят, что построенный граф получается из графа G отождествлением
вершин a и b. В случае, когда a и b соединены дугой, операцию отождеств- ления вершин a и b называют стягиванием дуги (a, b).
Пример 4.2.2. Из графа G, показанного на рис. 4.10, добавлением вер- шины 5 образуется граф G
1
, добавлением дуги (3, 1) — граф G
2
, удалением дуги (3, 2) — граф G
3
, удалением вершины 2 — граф G
4
, отождествлением вершин 1 и 4 — граф G
5
, стягиванием дуги (2, 3) — граф G
6
. ¤
4.2. ПОДГРАФЫ И ЧАСТИ ГРАФА. ОПЕРАЦИИ НАД ГРАФАМИ
123
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
?
?
?
?
?
•
•
•
•
C
C
C
C
CC
¤
¤
¤
¤
¤¤
±°
²¯
¢
¢
¢
¢
¢
¢®
-
¢
¢
¢
¢
¢
¢®
1 1
1 1
1 2
2 2
2 3
3 3
3 3
3 4
4 4
4 4
5 1
0
2 1
4 2
0
G
G
1
G
2
G
3
G
4
G
5
G
6
Рис. 4.10
Дополнением
графа без петель
G = hM; Ri
называется граф
G hM; M
2
\ (R ∪ id
M
)i.
Пример 4.2.3. Дополнением графа G, изображенного на рис. 4.10, яв- ляется граф G, показанный на рис. 4.11. ¤
Пусть G
1
= hM
1
; R
1
i, G
2
= hM
2
; R
2
i — графы. Объедине-
•
•
•
•
¡
¡
¡
¡
¡
¡
@
@
@
@
@
@
6 1
4 2
3
Рис. 4.11
нием G
1
∪ G
2
графов G
1
и G
2
называется граф hM
1
∪ M
2
;
R
1
∪ R
2
i.
Если M
1
∩ M
2
6= ∅, то пересечением G
1
∩ G
2
графов G
1
и G
2
называется граф hM
1
∩M
2
; R
1
∩R
2
i. Кольцевой суммой
G
1
⊕ G
2
графов G
1
и G
2
называется граф hM
1
∪ M
2
; R
1
⊕ R
2
i,
где R
1
⊕ R
2
= (R
1
\ R
2
) ∪ (R
2
\ R
1
).
Пример 4.2.4. Для графов G
1
= h{a
1
, a
2
, a
3
}; [a
1
, a
2
]∪
∪{(a
2
, a
3
)}i и G
2
= h{a
1
, a
2
, a
4
}; {(a
1
, a
2
), (a
4
, a
1
)}i (рис. 4.12) найдем G
1
∪G
2
,
G
1
∩G
2
, G
1
⊕G
2
. По определению имеем G
1
∪G
2
= h{a
1
, a
2
, a
3
, a
4
}; [a
1
, a
2
]∪
∪{(a
2
, a
3
), (a
4
, a
1
)}i, G
1
∩ G
2
= h{a
1
, a
2
}; {(a
1
, a
2
)}i, G
1
⊕ G
2
= h{a
1
, a
2
, a
3
, a
4
};
{(a
2
, a
1
), (a
2
, a
3
), (a
4
, a
1
)}i. ¤
Соединением G
1
+ G
2
графов G
1
и G
2
называется граф hM
1
∪ M
2
; R
1
∪
∪R
2
∪ ∪{[a, b] | a ∈ M
1
, b ∈ M
2
, a 6= b}i.
Пример 4.2.5. Для графов G
1
и G
2
, показанных на рис. 4.13а, соедине- нием G
1
+ G
2
является граф, представленный на рис. 4.13б. ¤
Часто при рассмотрении операции соединения графов предполагается,
что M
1
∩ M
2
= ∅.
Произведением G
1
× G
2
графов G
1
и G
2
называется граф hM
1
× M
2
; Ri,
в котором ((a
1
, b
1
), (a
2
, b
2
)) ∈ R тогда и только тогда, когда a
1
= a
2
и (b
1
, b
2
) ∈ R
2
, или b
1
= b
2
и (a
1
, a
2
) ∈ R
1
Пример 4.2.6. На рис. 4.14 изображено произведение G
1
× G
2
графов
G
1
= h{1, 2}; {(1, 1), (2, 1)}i и G
2
= h{a, b, c}; [a, b] ∪ {(b, c)}i. ¤
124
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
•
•
•
¡
¡
¡@
@@
R
a
1
a
2
a
3
G
1
•
•
•
X
X
X
X
X
X
y
»»»
»»
»
:
a
1
a
4
a
2
G
2
•
•
•
•
@
@
@
I
¡
¡
¡@
@@
R
a
1
a
2
a
3
a
4
G
1
∪ G
2
•
•
6
a
1
a
2
G
1
∩ G
2
•
•
•
•
@
@
@
I
¡
¡
¡
ª
@
@@
R
a
1
a
2
a
3
a
4
G
1
⊕ G
2
Рис. 4.12
•
•
•
¢
¢
¢
¢
¢¢AA
A
A
AAU
¾
a
1
a
3
a
2
•
•
•
¢
¢
¢
¢
¢
¢
A
A
A
A
A
AK
a
2
a
4
a
5
а
•
•
•
•
•
´
´
´
´
´
´
´
´
´
Q
Q
Q
Q
Q
Q
Q
Q
Q
¾
a
1
a
3
a
4
a
5
a
2
б
Рис. 4.13
•
•
6
j
2 1
G
1
×
•
•
•
-
a
b
c
G
2
=
•
•
•
•
•
•
6 6
6
n n
n
-
-
(2, a)
(2, b)
(2, c)
(1, a)
(1, b)
(1, c)
G
1
× G
2
Рис. 4.14
4.2. ПОДГРАФЫ И ЧАСТИ ГРАФА. ОПЕРАЦИИ НАД ГРАФАМИ
125
•
•
•
•
(0, 0)
(1, 0)
(0, 1)
(1, 1)
•
•
•
•
•
•
•
•
©©
©©
©
©©
©©
©
HH
HHH
HH
HHH
(0, 0, 0)
(0, 1, 0)
(0, 0, 1)
(0, 1, 1)
(1, 0, 0)
(1, 1, 0)
(1, 0, 1)
(1, 1, 1)
Рис. 4.15
Неорграф без петель называется полным, если его любые две различ- ные вершины смежны. Полный граф, имеющий n вершин, обозначается че- рез K
n
С помощью операции произведения определим по индукции важ- ный класс графов, называемых n-мерными кубами (n-кубами). Рассмотрим граф K
2
, вершины которого обозначим 0 и 1. n-Мерный куб, или n-куб Q
n
,
определяется по следующим правилам: Q
0
— граф без петель, состоящий из одной вершины, Q
1
K
2
, Q
n
K
2
× Q
n−1
, n > 1. Вершинами n-мерного куба Q
n
являются всевозможные n-ки, состоящие из нулей и единиц (все- го таких наборов 2
n
), а ребра задаются по следующему правилу: вершины смежны тогда и только тогда, когда соответствующие кортежи различаются ровно одной координатой. На рис. 4.15 показаны двумерный Q
2
и трехмер- ный Q
3
кубы.
Композицией G
1
[G
2
] графов G
1
и G
2
называется граф hM
1
×M
2
; Ri, в ко- тором ((a
1
, b
1
), (a
2
, b
2
)) ∈ R тогда и только тогда, когда выполняется одно из следующих условий:
1) (a
1
, a
2
) ∈ R
1
;
2) a
1
= a
2
и (b
1
, b
2
) ∈ R
2
Пример 4.2.7. Композицией G
1
[G
2
] графов G
1
и G
2
, рассмотренных в примере 4.2.6, является граф, изображенный на рис. 4.16, а композицией
G
2
[G
1
] — граф, представленный на рис. 4.17. ¤