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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

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

Страницы