Дискретная математика. Громов Ю.Ю - 44 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

44
В результате удаления дуг из подграфа G′′ получают частичный
подграф
G
~
графа G:
G
~
= 〈V′′,
U
~
〉,
U
~
⊂ U′′.
Например, для графа G, изображённого на рис. 18, а, частичный граф
G′, подграф G′′ и частичный подграф
G
~
представлены на рис. 18, б, в и г
соответственно.
Две дуги u
α
и u
β
графа называются смежными дугами, если они ин-
цидентны одной и той же вершине. Две вершины v
a
и v
b
графа называют-
ся смежными вершинами, если они соединены одной и той же дугой.
Определим понятие взвешенного графа. Для этого сопоставим каж-
дой вершине v
i
из множества вершин V = {v
i
/ i = 1, 2, ..., n} графа G =
= 〈V, U〉 вес w
j
из множества весов W = {w
j
/ j = 1, 2, ..., m}. В результате
получим множество взвешенных вершин {V, W}. При этом необязательно,
чтобы веса различных вершин были различными.
Сопоставим каждой дуге u
i
из множества дуг U = {u
i
/ i = 1, 2, ..., k}
графа G = 〈V, U〉 вес p
j
из множества весов P = {p
j
/ j = 1, 2, ..., l}. В ре-
зультате получим множество взвешенных дуг {U, P}. При этом необяза-
тельно, чтобы веса различных дуг были различными.
Определённые выше множества взвешенных вершин и взвешенных
дуг определяют в совокупности взвешенный граф G:
G = 〈{V, W}, {U, P}〉.
При задании графов матричным способом используют два типа мат-
риц: матрицы инциденций и матрицы смежности.
Рис. 18
а)
v
1
v
2
v
4
v
5
v
3
б)
v
1
v
2
v
4
v
5
v
3
в)
v
1
v
2
v
5
v
3
г)
v
1
v
2
v
5
v
3

Страницы