Файл: Кодирования.pdf

Матрицы L и U согласно формуле (
7.30
) равны
L =




a
0 0
0 0
a
1
a
0 0
0
a
2
a
1
a
0 0
a
3
a
2
a
1
a
0




,
U =


0 a
3
a
2
a
1 0
0
a
3
a
2 0
0 0
a
3


Таким образом, промежуточные векторы d и e согласно формуле (
7.29
) равны d = Lb =




a
0 0
0 0
a
1
a
0 0
0
a
2
a
1
a
0 0
a
3
a
2
a
1
a
0




·




b
0
b
1
b
2
b
3




=




a
0
b
0
a
1
b
0
+ a
0
b
1
a
2
b
0
+ a
1
b
1
+ a
0
b
2
a
3
b
0
+ a
2
b
1
+ a
1
b
2
+ a
0
b
3




=




d
0
d
1
d
2
d
3




,
e = Ub =


0 a
3
a
2
a
1 0
0
a
3
a
2 0
0 0
a
3


·




b
0
b
1
b
2
b
3




=


a
3
b
1
+ a
2
b
2
+ a
1
b
3
a
3
b
2
+ a
2
b
3
a
3
b
3


=


e
0
e
1
e
2


Подставляя полученную матрицу Q и векторы d и e в формулу (
7.31
), получим результат c:
c = d + Q
T
e =




d
0
d
1
d
2
d
3




+




1 0 0 1 1 0 0 1 1 0 0 1




·


e
0
e
1
e
2


=




d
0
+ e
0
d
1
+ e
0
+ e
1
d
2
+ e
1
+ e
2
d
3
+ e
2




=




c
0
c
1
c
2
c
3




Схема умножителя для рассмотренного поля показана на рис.
7.12 65

b
3
b
2
b
1
b
0
a
3
a
2
a
1
a
0
IP-сеть d
0
e
0
d
1
e
1
d
2
e
2
d
3
d
0
c
0
e
1
d
1
e
0
c
1
e
1
d
2
e
1
c
2
e
2
d
3
c
3
e
2
Q-сеть
Рис. 7.12. Умножитель двух элементов двоичного поля Галуа GF(2
m
) p(x) = x
4
+ x + 1
по схеме Рейхани-Мазолеха
Контрольные вопросы

8. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
Теория графов является разделом дискретной математики, изучающим свойства графов. Эта область науки крайне обширна и столь же интересна,
сколь и сложна. Этот математический инструмент находит применение во многих отраслях науки и промышленности. В качестве примеров использо- вания теории графов можно привести поиск кратчайшего маршрута на карте,
построение блок-схем алгоритмов, схемы размещения элементов на печатных платах, принципиальные и структурные схемы устройств (например рис.
2.4
и
7.1
) и многое другое. В данном пособии даны только основные понятия теории и те элементы, которые могут пригодиться при рассмотрении теории помехо- устойчивого кодирования.
Основоположником теории графов является Леонард Эйлер (1707–
1782), который решил в 1736 г. известную в то время задачу о семи ке- нигсбергских мостах. Впоследствии эта задача стала одной из классических задач теории графов. Впоследствии методы теории графов применялись и другими известными учеными в самых различных областях науки: в 1847 г.
Кирхгоф использовал теорию деревьев для расчета силы тока в электриче- ской цепи; в 1857 г. Кэли использовал деревья в решении задач органической химии. И таких примеров можно привести ещё много [
32
].
8.1. Основные понятия
В общем смысле граф G задается множеством точек или вершин (уз- лов) x
1
, x
2
, . . . , x n
(обозначается символом X ) и множеством линий или ребер a
1
, a
2
, . . . , a m
(обозначается A), которые соединяют между собой все или часть этих вершин. То есть, граф полностью задается и обозначается парой (X , A)
[
33
,
34
]. Существует и другое обозначение. Граф, содержащий n вершин и m ребер, называется (n, m)-графом, а (1, 0)-граф называется тривиальным [
32
].
Пример графа показан на рис.
8.1
Две вершины x i
и x j
, соединенные ребром a k
, называются смежными.
Их иногда обозначают как x i
adj x j
. При этом говорят, что вершина x i
и ребро a
k инцидентны, как и x j
и a k
. Два различных ребра, инцидентных одной и той же вершине, также называются смежными [
32
]. Так, на рис.
8.1
вершины x
1
и x
2
смежные, также смежными являются ребра a
1
и a
3
, которые инцидентны вершине x
2
Если в графе G = (X , A) ребра из множества A ориентированы (обычно показывается стрелкой), то такой граф называется ориентированным гра- фом или орграфом, а сами ребра называются дугами [
32
,
34
]. Граф, ребра которого не имеют ориентации, называется неориентированным, а содержа- щий и ориентированные, и неориентированные ребра — смешанным. Неори- ентированный граф, соответствующий орграфу G = (X , A), обозначается как
67

x
1
x
2
x
3
x
4
x
5
a
1
a
2
a
3
a
4
a
5
a
6
(а)
x
1
x
2
x
3
x
4
x
5
(б)
x
1
x
2
x
3
x
4
x
5
(в)
Рис. 8.1. Примеры графа:
(а)
неориентированный граф;
(б)
ориентированный граф;
(в)
смешанный граф.
¯
G
= (X , ¯
A
) и называется неориентированным дубликатом или неориентиро- ванным двойником графа G [
34
]. Примеры всех трех видов графа показаны на рис.
8.1
. При этом, граф на рис.
8.1(а)
является неориентированным дубли- катом графа на рис.
8.1(б)
Дуги орграфа удобно обозначать парами вершин вида (x i
, x j
), указывая от какой вершины к какой направлена дуга [
32
,
34
]. Например, на рис.
8.1(б)
можно выделить дугу (x
1
, x
2
), соответствующую ребру a
1
неориентированно- го графа на рис.
8.1(а)
Отдельно выделяют два вида графов. Мультиграф (см. рис.
8.2(а)
), в котором нет петель, но две вершины могут быть соединены более чем одним ребром — такие ребра называются кратными. Петлей называется ребро (ду- га) начальная и конечная вершины которой совпадают. Граф, в котором до- пускаются и кратные ребра и петли, называется псевдографом (рис.
8.2(б)
)
[
32
,
34
].
x
1
x
2
x
3
x
4
(а)
(б)
Рис. 8.2. Мультиграф
(а)
и псевдограф
(б)
Орграф, не имеющий симметричных пар дуг, называется направленным графом. При этом симметричными называют дуги, соединяющие одну и ту же пару вершин, но ориентированные в противоположных направлениях, на-
68

пример (x i
, x j
) и (x j
, x i
) [
32
]. На рис.
8.3(а)
показан пример направленного гра- фа. Дуги (x
2
, x
4
) и (x
4
, x
2
) ненаправленного графа на рис.
8.3(б)
являются сим- метричными.
(а)
x
1
x
2
x
3
x
4
(б)
Рис. 8.3. Направленный
(а)
и ненаправленный
(б)
графы
Если вершины графа имеют какие-либо метки, отличающие их друг от друга, то такой граф называется помеченным или перенумерованным [
32
].
Например, графы на рис.
8.2(а)
и рис.
8.3(б)
являются помеченными, а графы на рис.
8.2(б)
и
8.3(а)
— нет.
Граф G
1
, все вершины и ребра которого принадлежат графу G, назы- вается подграфом графа G, а G, в свою очередь, является надграфом для
G
1
. Подграф графа G, содержащий все его вершины, называется остовным подграфом или частичным графом [
35
,
32
]. Графы на рис.
8.4(б)
и
8.4(в)
яв- ляются подграфами графа
8.4(а)
, который является для них надграфом. При этом, граф
8.4(в)
является остовным подграфом графа
8.4(а)
(а)
(б)
(в)
Рис. 8.4. Граф
(а)
и его подграфы
(б)
и
(в)
Маршрутом в графе G называют чередующуюся последовательность вершин и ребер x
1
, a
1
, x
2
, a
2
, . . . , x n
−1
, a n
−1
, x n
, которая начинается и заканчи- вается вершиной, а каждое ребро инцидентно двум вершинам — непосред- ственно предшествующей и непосредственно следующей за ним [
32
]. Фак- тически, достаточно говорить просто про последовательность вершин или про последовательность ребер — одно подразумевает другое [
32
,
34
]. Такой маршрут, соединяющий вершины x
1
и x n
, иногда называют (x
1
–x n
)-маршру- том [
32
]. Если x
1
= x n
, то маршрут называется замкнутым, в ином случае —
открытым. Маршрут, все ребра которого различны, называется цепью. Если при этом различны все вершины, то маршрут называется простой цепью. За- мкнутая цепь называется циклом, а если все n вершин замкнутого маршрута различны и n ≥ 3, то он называется простым циклом [
32
].
69

В случае, если речь идет об ориентированных графах, используют по- нятие ориентированный маршрут или путь, под которым понимают после- довательность дуг (и, соответственно, вершин), в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следую- щей. Аналогично понятиям цепи и простой цепи выделяют ориентированную цепь (орцепь) и простую орцепь [
34
].
Длина (мощность) маршрута определяется количеством ребер в нем.
При этом, каждое ребро считается столько раз, сколько оно встречается в этом маршруте. Расстоянием d(x i
, x j
) между вершинами x i
и x j
графа назы- вается длина кратчайшей простой цепи, соединяющей их. Для несоединенных x
i и x j
полагают d(x i
, x j
) = ∞ [
32
,
34
].
Иногда дугам (x i
, x j
) графа G ставится в соответствие некоторое число c
i j
, называемое весом (длиной, стоимостью) дуги. Такой граф G называет- ся графом со взвешенными дугами. Если же некоторые веса v i
приписаны вершинам x i
, то такой граф называется графом со взвешенными вершинами или просто взвешенным. Иногда взвешенным называют граф, дуги и вершины которого имеют соответствующие им веса [
34
].
В том случае, если рассматривается некоторый путь µ, представленный последовательностью дуг, то за его вес принимается число l(µ), равное сумме весов всех дуг, входящих в µ [
34
]:
l
(µ) =
∑
(x i
,x j
)∈µ
c i j
8.2. Матричное представление графа
Для алгебраического задания граф удобно представлять в виде матриц
[
34
].
Для примера возьмем граф G, представленный на рис.
8.5
x
1
x
2
x
3
x
4
x
5
x
6
a
1
a
3
a
5
a
7
a
8
a
9
a
10
a
6
a
4
a
2
Рис. 8.5. Пример графа для матричного представления
70

8.2.1. Матрица смежности
Матрица смежности графа G полностью определяет структуру графа
[
34
]. Она обозначается как A = [a i j
], где a
i j
= 1, если в G существует дуга (x i
, x j
),
a i j
= 0, если в G отсутствует дуга (x i
, x j
).
Таким образом, для графа G на рис.
8.5
матрица смежности будет равна
A =
x
1
x
2
x
3
x
4
x
5
x
6
x
1 1
1 0
0 0
1
x
2 0
0 1
1 0
0
x
3 0
0 1
0 1
0
x
4 0
0 0
0 0
0
x
5 0
1 0
1 0
0
x
6 0
0 0
0 1
0 8.2.2. Матрица инциденций
Матрица инциденций графа G с n вершинами и m дугами, обозначается как B = [b i j
] [
34
]. Она имеет размерность n × m и определяется как b
i j
= 1,
если x i
— начальная вершина дуги a j
,
b i j
= −1,
если x i
— конечная вершина дуги a j
,
b i j
= 0,
если x i
не инцидентна a j
или a j
— петля.
Таким образом, для графа G на рис.
8.5
матрица инциденций будет равна
B =
a
1
a
2
a
3
a
4
a
5
a
6
a
7
a
8
a
9
a
10
x
1 1
0 0
0 0
0 1
0 0
0
x
2
−1 0 1
0 1
−1 0
0 0
0
x
3 0
0
−1 0 0
0 0
0 1
0
x
4 0
0 0
0
−1 0
0 0
0
−1
x
5 0
0 0
0 0
1 0
−1 −1 1
x
6 0
0 0
0 0
0
−1 1
0 0
Так как каждая дуга инцидентна двум различным вершинам, кроме случая,
когда она образует петлю, каждый столбец матрицы инциденций либо содер- жит и «1» и «−1», либо все его элементы равны «0» [
34
].
Для неориентированного графа матрица инциденций определяется ана- логично, за исключением того, что «−1» заменяется на «1» [
34
].
71

8.2.3. Матрицы достижимостей и контрадостижимостей
Матрица достижимостей R = [r i j
] определяется как r
i j
= 1,
если вершина x j
достижима из x i
,
r i j
= 0,
в противном случае.
Множество вершин R(x i
) графа G, достижимых из заданной вершины x i
, со- стоит из таких x j
, для которых элемент r i j в матрице R равен «1». Все диаго- нальные элементы R равны «1», так как каждая вершина достижима из себя самой с помощью пути длины 0 [
34
].
Матрица достижимостей R для графа G на рис.
8.5
равна
R =
x
1
x
2
x
3
x
4
x
5
x
6
x
1 1
1 1
1 1
1
x
2 0
1 1
1 1
0
x
3 0
1 1
1 1
0
x
4 0
0 0
1 0
0
x
5 0
1 1
1 1
0
x
6 0
1 1
1 1
1
Матрица контрадостижимостей (или матрица обратных дости- жимостей) Q = [q i j
] определяется как r
i j
= 1,
если вершина x i
достижима из x j
,
r i j
= 0,
в противном случае.
Таким образом, контрадостижимое множество Q(x i
) графа G — это множе- ство таких вершин, что из любой вершины этого множества можно достигнуть вершины x i
[
34
].
Из определений матриц Q и R следует, что матрица контрадостижимо- стей Q равна транспонированной матрице достижимостей R
T
[
34
]:
Q = R
T
Матрица контрадостижимостей Q для графа G на рис.
8.5
равна
Q =
x
1
x
2
x
3
x
4
x
5
x
6
x
1 1
0 0
0 0
0
x
2 1
1 1
0 1
1
x
3 1
1 1
0 1
1
x
4 1
1 1
1 1
1
x
5 1
1 1
0 1
1
x
6 1
0 0
0 0
1 72

8.3. Линейные графы сигналов и передача графа
Граф сигналов — это графическое представление соотношений между несколькими переменными. В случае линейности этих соотношений, граф вы- ражает систему линейных алгебраических уравнений и называется линейным графом сигналов. Такой способ представления позволяет наглядно выразить систему уравнений и решить ее непосредственно путем анализа графа [
36
].
Граф сигналов представляет из себя ориентированную цепь, в которой каждая дуга
4
(x j
x k
) связана с числом t jk
, называемым передачей дуги, а каж- дому узлу x j
соответствует так называемый узловой сигнал X
j
[
36
].
В дальнейшем, говоря в этом разделе о графах, будем иметь в виду именно линейные графы сигналов.
Узловые сигналы определяются уравнениями вида [
36
]:
X
k
=
∑
j
X
j t
jk
,
k
= 1, 2, 3, . . . .
(8.1)
x
1
x
2
x
3
x
4
t
12
t
13
t
24
t
42
t
34
t
32
t
23
Рис. 8.6. Пример графа сигналов
Для примера рассмотрим граф сигналов на рис.
8.6
. Согласно формуле
(
8.1
) его узловые сигналы будут равны
X
2
= X
1
t
12
+ X
3
t
32
+ X
4
t
42
;
X
3
= X
1
t
13
+ X
2
t
23
;
X
4
= X
2
t
24
+ X
3
t
34
Таким образом, можно сказать, что линейный граф сигналов представ- ляет из себя систему линейных уравнений, представленную особым обра- зом — вместо символов «+», «=» используются направленные дуги и узлы.
Каждое уравнение в этой системе имеет форму «причина — следствие». При этом каждый зависимый узловой сигнал выражен один раз в виде явного след- ствия, вызванного другими узловыми сигналами, действующими в качестве причин. Совокупность этих свойств приводит к тому, что уравнения вида (
8.1
)
могут быть решены непосредственно путем вычисления графа [
36
].
4
В источниках (например, [
36
] и [
37
]) также используют термины «ребро» и «ветвь».
73