Картинки из квадратов \ О гармоническом \ Бинарность \ Полные бинарные деревья \

10.4.4.9. Векторно-матричная модель
для Дерева

 
Начало см. здесь.
Продолжение разговора, начатого ранее на форуме у Экслера:
http://forum.exler.ru/arc/index.php?s=0&showtopic=126383. Ниже приведен калькулятор, упоминавшийся там (этот калькулятор будет гарантированно работать в браузере Internet Explorer):

Напомню смысл этого калькулятора. В арифметике есть интересный, хотя, быть может, и не очень известный факт: любое положительное рациональное число можно породить из единицы путем применения к ней в соответствующей последовательности всего лишь только двух очень простых матриц V и H, показанных на рис. ниже:
На этом рисунке показано также применение этих матриц к двумерным вектор-столбцам, которые репрезентируют собой дроби с числителем m и знаменателем n. Будем считать что рациональные числа у нас представлены обыкновенными несократимыми дробями. Под “единицей” будем понимать дробь 1/1. Можно показать, что применение к единице сколько угодно раз и в любой последовательности матриц V и H будет давать в результате только несократимые дроби, причем таким образом можно породить любую несократимую дробь, т. е. любое рациональное число.
Иллюстрировать эти рассуждения лучше всего на "поверхностном дереве" (известном также как "Calkin-Wilf Tree"). На рисунке ниже слева изображено "поверхностное" дерево, а справа —Stern-Brocot Tree. Оба дерева дорощены до четвертого уровня.
"Поверхностное дерево" самым непосредственным образом порождается фундаментальными для всех наших рассмотрений операторами V и H по следующим правилам:
(i)  корень дерева помечаем числом 1;
(ii)  если некоторая вершина дерева помечена положительным рациональным числом x, то левого сына этой вершины помечаем числом V(x), а правого сына этой вершины помечаем числом H(x).
При помощи этих двух унарных операций H и V, примененных в различных комбинациях к 1, мы, как можно показать, можем получить все положительные рациональные числа, причем разным комбинациям будут соответствовать разные числа. Например, V(H(H(1))) = 3/4, что можно проверить прямым вычислением в соответствии с определением операций H и V.

Смысл векторно-матричной модели для "поверхностного дерева" заключается в том, что дроби с числителем m и знаменателем n, фигурирующие на этом дереве, представляются соответствующими двумерными вектор-столбцам с первым компонентом m и вторым компонентом n; операции V и H представляются приведенными выше матрицами; применение операции к некоторой дроби моделируется умножением соответствующей матрицы на соответствующий вектор-столбец.
Возвращаемся к калькулятору. Еще раз приведем его здесь для удобства.
Калькулятор позволяет увидеть, какое рациональное число получится, если применить к единице соответствующую последовательность матриц V и H. Например, если применить к единице последовательность VHH, т. е. посчитать выражение
V(H(H(x)) = VHH(x), то получим дробь 3/4.
VHH обозначает целочисленную матрицу, являющуюся произведением входящих в последовательность VHH элементарных матриц V и H. Эта результирующая матрица вычисляется калькулятором и применяется затем к единичному вектор-столбцу.
Калькулятор будет корректно работать в браузере Internet Explorer. В поле "Программа" введите необходимую последовательность из заглавных латинских букв V и H и нажмите на кнопку "Вычислить".

Эту ситуацию можно проинтерпретировать электротехнически, т. е. рассмотреть результирующую матрицу, вычисляемую калькулятором, как матрицу взаимного четырехполюсника, записанного в А-форме. См. особенно матричное уравнение 8-8 в Разделе об этом. Условие "взаимности" четырехполюсника (соотношение 8-7 в том же Разделе), формулируется путем наложения некоторого ограничения на матрицу четырехполюсника. Понятно, что это ограничение есть ни что иное, как требование равенства единице определителя матрицы четырехполюсника.
Матрицы, определитель которых равен единице, называются унимодулярными:
http://en.wikipedia.org/wiki/Unimodular_matrix.
Легко догадаться (и при желании проверить это экспериментально), что приведенный выше калькулятор будет всегда порождать только унимодулярные матрицы. Таким образом, эти матрицы действительно можно рассматривать как матрицы взаимных четырехполюсников.
К началу данной страницы  
Картинки из квадратов \ О гармоническом \ Бинарность \ Полные бинарные деревья \