Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
а — <а(1), а(2), ..а(т), ..
где т — номер яруса, а а(т)—номер ребра, входящего в эту ветвь, если идти до ней, начиная от корня. Так, например, ветви, помеченной на рис. 2 штриховой ли-
*) Упорядоченное множество ребер, в котором конец предыдущего ребра является началом последующего.
ЬО ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
ниеи, соответствует последовательность {0, 1, Л' — 1, .. Очевидно, что а ^ Ес^. Справедливо и обратное утверждение: каждой последовательности а из ?с,д- соответствует некоторая ветвь дерева. Таким образом, мы имеем взаимно однозначное соответствие между ветвями дерева и элементами множества В силу этого мы можем
пользоваться деревом для геометрического задания множества гу.
Пусть /(X) является функцией из Рд,л- (Лг — А:") и X =(^1, ..хп). Используя соотношение
при помощи /(X) каждому ребру дерева припишем число из Ек. Для этого возьмем произвольное ребро из т-то яруса {т — 1, 2, ...) и рассмотрим путь, ведущий из корня к этому ребру — он может быть также определен как отрезок произвольной ветви, проходящей через данное ребро. Очевидно, что путь определен однозначным образом и может быть охарактеризован некоторым кортежем а(1), а(2), ..а{т) номеров ребер пути, отсчитываемых от корня. Исходному ребру припишем т-й члея выходной последовательности — число 7(пг), где
Полученное дерево будем называть занумерованным деревом (точнее, деревом с занумерованными ребрами).
Пример 3. а) Для функции (ад, хг) имеем:&=» =** п = 2, Дг = 4 и
7 (я*)в/м(Яі, Х2, Хт) — /т (Х,л) = Хі (т) & х2 (т).
Следовательно, Y(ffг) зависит только от последнего члена кортежа, ведущего к данному ребру, т. е. от номера ребра.
Ребру с номером 0 — (0, 0) соответствует
На рис. 3 представлено соответствующее занумерованное дерево.
7(пг) = /т(а(1), а(т)).
«
«
1=(0, 1) 2-(1, 0) 3«<1, 1)
значение 0 & 0 — О,
« 0 & 1 = О,
« 4 & 0 = О,
« 1 & 1 = 1.
ГЛ. 3. О.-Д. ФУНКЦИЙ С ОПЕРАЦИЯМИ 81
б) Для функции z — х + у имеем к = 2, п = 2 и N = 4. Очевидно, что
fx(m) -|- у(т) (mod 2) при отсутствии переноса,
[ я(т)-р у{т) + 1 (mod 2) при наличии переноса.
Отсюда нетрудно усмотреть закон получения занумерованного дерева (рис. 4). Процесс приписывания ребрам
Рис, 3
чисел начинается с 1-го яруса. Затем переходят ко 2-му ярусу и т. д. При этом, если появляется перенос в следующий разряд, то конец соответствующего ребра помечается кружочком. Это позволяет выполнить вычисления в следующем ярусе.
Рис. 4
в) Для функции г = хг имеем к — 2, /г = 1 и N = 2. Здесь явное выражение для г(т) в виде функции /,„(#(1), ,.х{т)) значительно сложнее, чем в предыдущих случаях, и удобнее вычислять г(т), пользуясь алго-
6 С. Б, Яблоьский
82 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
ритмом возведения в квадрат. Из него видно, что
*(1)-*(1),
2(2)» О,
z(3)» дг(2) + #(1)2(2) (mod 2),
2(4)» ^(1)^(3) + #(1)#(2) (mod 2) и т. д.
Соответственно получаем начальный фрагмент занумерованного дерева (рпс. 5).
Рис. 5
Итак, мы видим, что по детерминированной функции можно получить занумерованное дерево. Обратное утверждение, вообще говоря, неверно: ванумерованное дерево может определять несколько детерминированных функции. Параметры N и к' (где N — число ребер, исходящих из каждой вершины, а к — максимум чисел, приписанных ребрам) могут допускать несколько решений уравнения N =- кп при к > к*. (Всегда существует решение к ** N и п = 1, т. е, определяется детерминированная функция от одного переменного.) Однако, если по детерминированной функции }(хи ..., яп) построить занумерованное дерево, то по этому занумерованному дереву с параметрами кип определится единственная детерминированная функция, а именно f{xu ..хя), Таким образом, занумерованными деревьями можно пользоваться в качестве аппарата для изучения детерминированных функций.
Возьмем занумерованное дерево для некоторой детерминированной функции ](Х)=* ..., хп). Пусть ? —
произвольная его вершина т-го яруса. В нее из корня ?0 ведет путь
а(1), ..а(т)
iJl. Д. u.-д- Ц'а'ниции С ОПЕРАЦИЯМИ
S3
(при ? = ?0 путь является пустым). Совокупность всех ветвей, исходящих из ?, порождает некоторое дерево с корнем которое будем называть специальным поддеревом исходного дерева. Это поддерево определяется множеством всех последовательностей из Etsh с фиксированным началом
сс(1), ..., а{т).
Так как исходное дерево занумеровано, то поддерево является также занумерованным. Если в поддерево ввести нумерацию ярусов, начиная с 1-го, то ему будет соответствовать детерминированная функция /е (X). Ее можно аналитически определить следующим образом: пусть
/(Х)~{Л(ХL),h{Xi>x2), ...}* №)~{/№U I
Тогда
f]{Xlt ...t Xj) =*/m+i(a( 1), а(т)г Xu
(i~U 2, ...).
Определение. Два поддерева с корнями |i и ?2
исходного дерева называются эквивалентными, если
lh{X)^f\X).
Очевидно, что при естественном наложении двух эквивалентных поддеревьев их нумерации совпадают. Так, в дереве на рис. 3 все поддеревья эквивалентны, а в дереве на рис. 4 поддеревья с корнями ?0 и |г эквивалентны, а с корнями |0 и ?i — не эквивалентны.
