О задачах обхода графа
7
Приведем обоснование указанного алгоритма; оно опирается на
булевы функции. Рассмотрим множество
Z
2
, состоящее из двух буле-
вых величин 0, 1 с булевыми операциями: обычное умножение и
сложение по модулю 2. Напомним, что на языке алгебры множество
Z
2
есть поле. Возьмем далее множество всех функций
a → f
(
a
), где
a
пробегает множество окон, а значения функции принадлежат множе-
ству
Z
2
. Для таких функций определены операция сложения по моду-
лю 2 и операция умножения на элементы множества
Z
2
. Другими
словами, получили линейное пространство
L
над полем
Z
2
. Его раз-
мерность равна
mn
(в качестве базиса можно взять набор функций,
каждая из которых принимает значение 1 только на одном окне, а на
остальных окнах принимает значение 0). Понятия линейной зависи-
мости, базиса и другие вводятся так же, как в обычной линейной ал-
гебре (над полем вещественных либо комплексных чисел).
Определена и операция поточечного перемножения двух функций.
Введем булево скалярное произведение двух функций по форму-
ле
1 2
1
2
( ) ( ).
а
f f
f a f a
Итак, перемножаем функции
1 2
,
f f
и берем
сумму (по модулю 2) значений полученной функции для всех
a
A
.
Повторяя общеизвестные понятия линейной алгебры, назовем
функции ортогональными, если
1 2
,
0.
f f
Набор функций
f
k
назовем
ортонормированным, если
,
0
i
k
f f
при
i ≠ k
и
,
1
k k
f f
для всех
k
.
Для каждого окна
a
обозначим через
a
f
функцию, которая при-
нимает значение 1 на окнах, входящих в множество
T
a
, и значение
0 — на всех других окнах (другими словами,
a
f
есть характеристи-
ческая функция множества
T
a
).
Лемма
.
Семейство функций
a
f
есть ортонормированный базис
пространства L.
Читатель без труда докажет эту лемму (следует проследить, в
каком месте доказательства используется то, что
m
,
n
— четные
числа).
Вернемся к задаче 2.2 и обозначим через
E
множество закрытых
окон и через
g
E
характеристическую функцию этого множества. Та-
ким образом, действия над множествами превращаются в действия
над характеристическими функциями. Важнейшее обстоятельство
состоит в следующем: изменить состояние всех окон, входящих в
множество
T
a
, равносильно замене функции
E
g
функцией
E
g
.
a
f
Разложим функцию
E
g
в линейную комбинацию функций
,
a
f
обозначив коэффициенты разложения через
r
(
a
). Коэффициенты
r
(
a
)
находим по очевидным правилам вычисления коэффициентов ряда
Фурье по ортонормированному базису. Таким образом,
r
(
a
) =
