Дискретная математика. Кулаков Ю.В - 33 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

б) S = {
2
1
xx
,
2
x };
д) S = { x
2
∨
3231
xxxx ∨ , x
1
x
2
∨
x
2
x
3
};
в) S = { x
1
x
3
,
31
2
xxx ∨ ,
3
x ∨
2
1
xx };
е) S = {
3
2
xx ∨ , x
1
x
2
x
3
,
1
x }.
6 ВЗВЕШЕННЫЙ ГРАФ И ЕГО МАТРИЧНОЕ ЗАДАНИЕ
Выше понятие графа было определено как совокупность 〈V, U〉 множества
вершин V и дуг U ⊂ V
2
. Дуга u, соединенная с вершиной v, называется инцидентной вершине v, а вер-
шина v – коинцидентной дуге u. В дуге (v
i
, v
j
) вершины v
i
и v
j
называются граничными, причем v
i
– нача-
ло, v
j
– конец дуги.
При удалении дуг из графа G = 〈V, U〉 получаем частичный граф G' ⊂ G, G' =
〈V, U'〉, U' ⊂ U графа G, при удалении вершин и инцидентных им дуг – подграф G" = 〈V", U"〉, V" ⊂ V, U"
⊂ U графа G, при дальнейшем удалении дуг из подграфа G" графа G - частичный подграф G
~
= 〈V", U
~
〉,
U
~
⊂ U" графа G.
Две дуги u
α
и u
β
называются смежными, если они инцидентны одной и той
же вершине. Две вершины v
a
и v
b
называются смежными, если они соединены дугой.
Используя понятие окрестности единичного радиуса вершины v
α
, обозна-
чаемой O(v
α
) или Гv
α
, граф определяют как совокупность множества вершин и множества окрестностей
этих вершин: G = 〈V, Г〉.
Определим понятие взвешенного графа. Сопоставим каждой вершине v
i
∈ V
, V = {v
i
/ i = 1, 2, ..., n} графа G = 〈V, U〉 вес w
j
из множества весов
W = {w
j
/ j = 1, 2, ..., m}. В результате получим множество взвешенных вершин, при этом необязательно,
чтобы веса различных вершин были различными. Сопоставим каждой дуге u
i
∈ U , U = {u
i
/ i = 1, 2, ...,
k} графа
G = 〈V, U〉 вес p
j
из множества весов P = {p
j
/ j = 1, 2, ..., l}. В результате получим множество взвешенных
дуг, при этом необязательно, чтобы веса различных дуг были различными.
Определенные выше множества взвешенных вершин и взвешенных дуг оп-
ределяют в совокупности взвешенный граф G = 〈(V, W), (U, P)〉.
Для задания графов существует несколько классов матриц, основными из
которых являются класс матриц инциденций и класс матриц смежности. Рассмотрим эти классы мат-
риц.
Класс матриц инциденций. Если граф G содержит n вершин и m дуг, то мат-
рица инциденций A(G) = [a
ij
]
m × n
определяется как
−−
−
=
.дугенакоинцидентневершинаесли,0
;дугиконецвершинаесли,1
;дугиначаловершинаесли,1
ij
ij
ij
ji
uv
uv
uv
a
Иногда граф содержит петли, т.е. дуги вида (v
i
, v
i
). В этом случае некоторые
элементы матрицы A одновременно должны быть равны и 1, и –1, что приводит к неоднозначности эле-
ментов матрицы A.
Для задания графа с петлями «расщепим» матрицу A на две матрицы: мат-
рицу A
+
= [
+
ij
a ]
m × n
, где
−
=
+
случаепротивномв,0
;дугиначаловершинаесли,1
ij
ji
uv
a
и матрицу A
−
= [
−
ij
a ]
m × n
, где
−
=
−
случае.противномв,0
;дугиконецвершинаесли,1
ij
ji
uv
a
Если граф без петель, то A = A
+
− A
−
. Матрицы A
+
и A
−
описывают граф без
учета весов вершин и дуг.
Зададим веса вершин графа G в виде столбцовой матрицы

Страницы