Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
будет следовать нужное нам свойство относительно Y-U. Если X -"-" У и X -
*-* U, где U С У, то А' -"-" У - U. Имеем
У = i/0 У', Y' = Y - U.
Iq(Y/X)' = Iq(Y/X0 Zj) = /0(t/ 0 У'/А' 0 Zj) =
= /0(tf/* 0 Zj) + I0(Y'/X 0 Zj 0 U) =
= /0(t//X) + I0(Y'/X 0 Zj 0 60-
Поскольку
/о(У/А0 = I0(U 0 У'/А') = Iq(Y'/X) + /0(i//A: 0 У) =
= IQ(Y'/X) + IQ{U/X),
получаем
Iq(Y'/X 0 Zj 0 60 = I0(Y'/X).
Мб. Псевдотранзитивность: Если X -"-" У u У 0 Ж -"-" U,
то
X <8> W -*-* ?/- (У0
55
Доказательство. Свойство X -*-* Y в сочетании с пополнением дает
X(r) W -*-* Y.
Далее,
X(r)W -*-* W, I0{W/X (r)W(r)Z) = 0 = I0{W/X (r) W).
Применяя аддитивность, получаем,
X (r) W -*-* Y (r) W.
Поскольку
Y(r)W^U,
из транзитивности следует
X(r) U - (Y (r) W).
Так же, как и в случае функциональных зависимостей, можно показать, что
система правил Ml-Мб является полной, так что, применяя эти правила,
можно получить все многозначные зависимости, характерные для данного
отношения. После устранения этих зависимостей отношение оказывается в 4-й
нормальной форме.
4. СЛОВА И ГРАФЫ
4.1. Граф алгебраического канала
В гл. 1 алгебраический канал был определен посредством пары слов х <8> у.
Этот канал преобразует слова орбиты Ох в слова
орбиты Оу, а закон преобразования определяется переходной
матрицей, соответствующей словам х и у.
В то же время паре слов х(r) у соответствует некоторый граф,
если считать его ребром столбец из пары х (r) у. Например,
если
х {a a a b b с с\ у \а b b a d b а)' то граф выглядит следующим образом:
Заметим что мы получили граф самого общего вида-ориентированный граф с
кратными ребрами и петлями. Такой граф обычно называют мультиграфом.
Обратно, каждому мультиграфу соответствует некоторая пара слов х <8> у.
Поскольку граф не зависит от того, в каком порядке выписаны его ребра,
пара х (r) У и пара ах <Э cry, где а-некоторая подстановка, определяют один
и тот же граф. Мы будем всегда определять граф посредством пары слов х
<8> у, где х отсортировано (его буквы лексикографически упорядочены).
Таким образом, понятие алгебраического канала эквивалентно понятию графа.
Переходная матрица канала является матрицей инцидентности
соответствующего графа:
abed
а 1 2 3
Ь 1 1 2
с 1 1 2
d 0
3 3 1 7
57
Множество ребер графа обычно обозначают через Е, а величина \Е\
определяет сложность объекта "граф": чтобы задать граф, нужно каким-то
образом перечислить его ребра.
Граф, у которого каждая пара вершин соединена ребром,
2
называется полным. Очевидно, у полного графа \Е\ = I VI , где V-множество
вершин. Таким образом, всегда выполнено неравенство
\Е\ < \V\2.
Мультиграф удобно записывать парой слов х <8* у с указанием внизу
кратности соответствующей дуги:
/а а Ъ Ь с с \ а Ъ a d Ъ а
U 2 1 1 1 1
Таким образом, мультиграф-это обычный граф, у которого каждое ребро
снабжается некоторым целым числом (весом ребра).
4.2. Поиск пути
Основной алгоритм на графе называется "Поиск пути". Этот алгоритм
позволяет найти путь из вершины а в вершину t, состоящий из минимального
количества ребер:
Компактная запись этого графа:
(a a a bcddeeffffikktt\
\d е ifbgkbicektge i с к)'
Поиск пути начинаем с того, что определяем вершины 1-го поколения. Это
множество вершин, в которые можно попасть из начальной вершины. Каждой из
этих вершин ставим в соответствие метку-вершину, из которой мы пришли:
Метка
а
b
с
d а
е а
/
8
i а
к
t
58
Теперь находим вершины 2-го поколения, просматривая все вершины,
помеченные на предыдущем этапе. Если вершина уже помечена, то новая метка
не Ставится.
Метка 1-го поколения Метка 2-го поколения
а
Ь е
с
d а
е а
f
S d
i а
к d
t
Продолжаем этот процесс, пока не1 будет помечена конечная вершина t.
Метка Метка Метка Метка
1-го поколения 2-го поколения 3-го поколения 4-го поколения
а
Ь е
с
d а
е а
/ Ь
S i а d
к d
t /
Для наглядности мы "разнесли" метки разных поколений по различным
столбцам. На самом деле все метки следует хранить в одном столбце. Как
только конечная вершина ( оказалась помеченной, процесс расстановки меток
прекращается. Искомый путь строим, отправляясь от конечной вершины.
Находим метку вершины t-она равна /. Теперь находим метку вершины /-она
равна Ь, и т. д. В результате получаем
Путь = (а, е, Ь, /, t).
Граф называется связным, если для любой пары вершин (г, f) существует
путь из г в у. Описанный алгоритм можно применить для определения
связности графа, но проще эту задачу решить с помощью остовного дерева.
59
4.3. Остовное дерево графа
Деревом называется неориентированный связный граф без циклов.
Пример дерева:
В каждом дереве найдется хотя бы одна вершина, которая связана лишь одним
ребром с остальной частью графа (такая вершина называется висячей).
Действительно, допустим, что каждая вершина имеет по крайней мере два
ребра. Тогда можно "войти" в вершину i по одному ребру, а "выйти" по
другому. В результате получим новую вершину у. С этой вершиной можно
