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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

46
n
w
w
w
GW
...
)(
2
1
=
,
m
p
p
p
GP
...000
.....
0...00
0...00
)(
2
1
=
.
Таким образом, матрицы A
+
(G), A
−
(G), W(G) и P(G) полностью опи-
сывают взвешенный граф G = 〈{V, W}, {U, P}〉.
Рассмотрим логическую схему (рис. 19, а), реализующую функцию
сложения по модулю два f (x
1
, x
2
) = x
1
⊕ x
2
в базисе Шеффера
B = {ϕ
ш
}, где ϕ
ш
(x
1
, x
2
) = x
1
| x
2
=
21
xx ∨
− одноимённая функция. Эта
схема содержит четыре базисных элемента, каждый из которых пред-
ставляет функцию ϕ
ш
, а соответствующий ей взвешенный граф G =
= 〈{V, W}, U〉 изображён на рис. 19, б.
Вершины v
1
и v
2
графа взвешены переменными x
1
и x
2
соответствен-
но, каждая из вершин v
3
, v
4
, v
5
и v
6
– функциональной переменной ϕ
ш
,
а вершина v
7
– функциональной переменной f. Упомянутый взвешенный
граф G задаётся с использованием матрицы инциденций следующим об-
разом:
1 0 0 −1
0 0 0
1 0 −1
0 0 0 0 x
1
0 1 −1
0 0 0 0 x
2
0 1 0 0 −1
0 0
ϕ
ш
A(G) =
0 0 1 −1
0 0 0 , W(G) =
ϕ
ш
.
0 0 1 0 −1
0 0
ϕ
ш
0 0 0 1 0 −1
0
ϕ
ш
0 0 0 0 1 −1
0 f
0 0 0 0 0 1 −1
Элемент матрицы смежности S(G) = [s
ij
]
n × n
графа G, содержащего
n вершин и m дуг, определяется следующим образом:
∉
∈
=
,),(если,0
;),(если,1
Uvv
Uvv
s
ji
ji
ji
а если дуги этого графа взвешены, то:
∉
∈
=
.),(если,0
;весимеет),(дугаесли,
Uvv
pUvvp
s
ji
jijiji
ji
Матрицы S(G) и W(G) полностью описывают взвешенный граф
G = 〈{V, W}, {U, P}〉. Например, граф G = 〈{V, W}, U〉 (рис. 19, б) с помо-
щью матрицы смежности следует задать так:

Страницы