Научная литература
booksshare.net -> Добавить материал -> Математика -> Яблонский С.В. -> "Введение в дискретную математику " -> 25

Введение в дискретную математику - Яблонский С.В.

Яблонский С.В. Введение в дискретную математику — Наука , 1986. — 384 c.
Скачать (прямая ссылка): vvedenievdiskretnuyum1986.djvu
Предыдущая << 1 .. 19 20 21 22 23 24 < 25 > 26 27 28 29 30 31 .. 104 >> Следующая

Соотношение эквивалентности позволяет в исходном дереве множество всех поддеревьев разбить на классы эквивалентности.
Определение. Число г классов эквивалентности, на которое разбивается множество всех поддеревьев данного дерева, называется весом дерева и соответственно весом детерминированной функции*).
*) Данпое определение может быть распространено и на константы. Последовательность (7(1), 7(2), ..у(т), ...,} изображается вырожденным деревом, состоящим из одной ветви
у<1) у(2) у{тп)
О ___^ О О # щ Л О ^ 0 • • •
В нем можно рассматривать поддеревья и определи1ь эквивалентность поддеревьев,
6*
84
Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ШШЕАЩШЙШ
Иначе говоря, вес — это максимальное число попарно неэквивалентных поддеревьев. При этом не исключается случай, когда вес г бесконечен.
Обратимся к примеру 3. В дереве для функции /^(.^1,^2) (рис. 3), как мы видели, все поддеревья эквивалентны, поэтому Г “ 1. В дереве для функции 2 = X + у (рис. 4) каждое поддерево эквивалентно либо поддереву с корнем Бв, либо поддереву с корнем поэтому г = 2.
В дереве для функции 2 = х2 (рис. 5) поддеревья с корнями |0, ^1, ?2> ... (лежащие на левой ветви) попарно неэквивалентны, так как в силу справедливости соотношения
{О ... О а (г + 1), .. .}2 = (0 ... О а (г + 1), ...}
г 2г
поддерево с корнем ^ в первых I ярусах заполнено пулями, а в (г+ 1)-м ярусе имеет ребро, которому приписано значение 1. Здесь г = оо.
Для занумерованных деревьев можно ввести нумерацию вершин. Сначала перенумеруем классы эквивалентности числами 0, 1, ... так, чтобы класс, в который но-
Рис. 6
падает исходное дерево, имел номер 0. Таким образом, нумерация содержит большой произвол. Далее, взяв произвольную вершину |, определим класс, в который попадает дерево с корнем Пусть х — номер этого класса. Тогда вершине | присваивается номер х. Мы получаем дерево, у которого занумерованы также и вершины, причем корень имеет номер 0. На рис. 8 приведены нумера-
ГЛ. 3. О.-Д. ФУНКЦИИ С ОПЕРАЦИЯМИ
85
цип вершин для двух основных примеров — функций /&(*!, Хг) Е г = X + у.
Если в рассматриваемом дереве сохранить только нумерацию вершин, то легко видеть, что нумерация ребер не восстанавливается однозначным образом. Тем не менее, нумерация вершин весьма, полезна при исследовании исходного дерева. В ряде случаев нумерацию вершин можно осуществлять параллельно с нумерацией ребер. Так, в примере для г — х + у номер вершины 0 появляется в случае отсутствия переноса, а 1 — при наличии переноса*). Рассмотрим теперь дерево с занумерованными ребрами и вершинами. Возьмем произвольную ветвь, она проходит через вершины
1о) 11) ? ? *) ЬЬ ? • ч 1ь • * •
Пусть этим вершинам приписаны соответственно
номера
О, ^1, . .., ?
Допустим, что х( ~ x^ (г Ф }) и для всех пар (ц /) у),
ДЛЯ которых X* ~ X/, индекс У является наименьшим. Произведем усечение данной ветви, сохранив ее начальный отрезок до вершины Производя эту операцию усечения для каждой ветви, мы получим усеченное дерево.
Для случая фупкции конечного веса г на каждой ветви происходит повторение номеров вершин и номер У,
ч
В 1 1 г
Рис. 7
определяющий усечение, удовлетворяет неравенству У ^ г. Поэтому для таких функций усеченное дерево будет конечным.
*) Вспомним, нто в примере 3, б) при наличии переноса в следующий разряд конец соответствующего ребра мы помечали кружочком.
86
Ч. I. ФУНЩИиИАЛЬйыи ишлычи и иньгАцып^ш
На рис. 7 приведены усеченные деревья для функций /&(^ь хг) и г = х 4- у. Эти усеченные деревья непосредственно получаются из деревьев, приведенных на рис. 6.
Легко видеть, что усеченное дерево с занумерованными ребрами и вершинами позволяет полностью восстановить исходное занумерованное дерево.
§ 3. Ограниченно-детерминированные функции
и способы их задания
Определение. Детерминированная функция ](хи ..., хп) называется ограниченно-детерминированной (о.-д.) функцией, если она имеет конечный вес.
Класс всех о.-д, функций, принадлежащих Рд,*, обозначим через Р0д. * *).
Примеры 3, а) и 3, б) предыдущего параграфа дато^ примеры о.-д. функций, а пример 3, в) показывает, чтю
(2,1) (1,0)
Рис. 8
класс Род, * — класс всех о.-д, функций является собствегд-вым подклассом класса Рд-* — класса детермннироваьн-ных функций.
Для любой о.-д. функции соответствующее ей полное (бесконечное) занумерованное дерево можно всегда свье-сти к конечному дереву с занумерованными ребрами и вершинами. Если в этом усеченном дереве произвеситя отождествление вершив с одинаковыми номерами, то получим так называемую диаграмму Мура **), На рис. 8
*) Класс Род, л, в частности, содержит все периодические шло-следовательности изРс.ь.
**) Диаграммы Мура можно использовать и для представление просто детерминированных функций. Б этом случае диаграмма .©будет содержать, вообще говоря, бесконечное число вершин,-
ГЛ. 8. й.-д. ФУНКЦИЙ С ОПЕРАЦИЯМИ
87
приведена диаграмма Мура для функции г == х + у. В ней
нулем отмечена начальная вершина и для удобства ребрам приписаны пары чисел {а, 7), первое из которых обозначает номер ребра, а второе — число, соответствующее атому ребру.
Предыдущая << 1 .. 19 20 21 22 23 24 < 25 > 26 27 28 29 30 31 .. 104 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed