L на R. Например, 10 - GRRR = ILRR -- 2LR = 3RRL и т. д. Если и, v и w - ребра многоугольника с w = uaLj и w = vffRj, то получим и = vjiLa и « = uaRp.

Для данной триангуляции многоугольника, стороны которого пронумерованы числами О, 1, ..., m - 1, определим (и, v) для любой пары и и и следующим образом. Пусть и = va, а Q представим в виде матрицы размера 2x2, предполагая, что L = {\ \ )kR = {\ °). Тогда {и, v) - это элемент в правом верхнем углу q. Обратите внимание на то, что матрица - это транспонированная матрица Q, так как R = . Следовательно, получим {v, и) = (и, v). Также необходимо отметить, что [и, v) = \ тогда и только тогда, когда и- и v- объединены ребром триангуляции, где и обозначает верщину между ребрами и и и - 1.

Пусть {и, и) = О для всех сторон многоугольника и. Можно доказать, что из и = иа следует

" = [ iu + l,v} (Л 1,. + 1)) « "

где U+1 и V + 1 - последователи и и и в направлении обхода по часовой стрелке. Доказательство этого утверждения выполняется с помощью метода индукции по т. Соотнощение (*) тривиально для т = 2, так как два параллельных ребра и и v связаны соотнощениями U = ие, а а = б - единичная матрица. Если произвольную триангуляцию дополнить некоторым ребром v с треугольником vvv", то из и = иа будет следовать, что v = uaL и v" = uaR. Значит, {u,v) и {u,v") в этом расширенном многоугольнике соответственно равны (и, v) и {и, v) + {u,v + l) из исходного многоугольника. Отсюда следует, что

( М {u,v") \ ( {u,v") {u,v" + l) \

\{u + l,v) {u + l,v")) \{u + l,v") {u+l,v" + l))

a (*) выполняется и для расширенного многоугольника.

Узор бордюра, который соответствует данной триангуляции, теперь определяется периодической последовательностью

(0,1) (1,2) (2,3)

(0,2) (1,3) (2,4) (m-1,2) (0,3) (1,4)

(m-1,3) (0,4) (1,5)

(m-1,0) (0,1) (1,2)

(m-1,1) (0,2) (1,3)

(m-2,1) (m-1,2) (0,3)

(m-2,2) (m-1,3) (0,4)

и T. Д , пока не будут определены m - 1 строк; последняя строка начинается с ([т/2] + 1, [т/2]) для m > 3. С помощью условия (*) можно доказать, что этот узор является бордюром, т. е что

{и, v){u+l,v + l) - (и, v+l){u+l,v) = 1, (**)

поскольку из det L = det R - 1 следует, что det а = 1. Для рассматриваемого здесь примера триангуляции получим следующее.

111111111111111111111

124215131431242151314 2177144223 11 2177144223

13 12 3337158713 12 333715 8 325582532 13 5325582532 13

532 13 5325582532 13 53255 8 37158713 12 3337158713 12 3

4223 11 2177144223 11 2177 1 513143124215131431242

111111111111111111111

Отношение {и, v) = 1 определяет ребра триангуляции, поэтому разные триангуляции позволяют получить разные бордюры. Для завершения доказательства взаимно однозначного

соответствия нужно показать, что каждый (тп - 1)-строчный узор бордюра, сложенный из положительных целых чисел, можно получить на основе некоторой триангуляции.

Расширьте заданный произвольный узор из тп -1 строк за счет вставки новой 0-й строки сверху и новой тп-й строки снизу, которые состоят только из нулей. Обозначим теперь все элементы 0-й строки символами (0,0), (1,1), (2,2) и т. д., а для всех неотрицательных целых чисел и < V < и + тп предположим, что (и, v) - это элемент, направленный на юго-восток по диагонали от (и, и) и на юго-запад по диагонали от (и, и). Предполагается, что условие (**) выполняется для всех и < v < и + тп. Действительно, его можно расширить до значительно более общего соотношения

{t,u){v,w) + {t,w){u,v) = {t,v){u,w) для t<u<v<w<t + Tn. (***)

Если утверждение (***) ложно, пусть {t,u,v,w) - контрпример с наименьшим значением (w - 1)тп + и - t + w - V. Случай 1. t + 1 < и. Тогда (***) выполняется для (t, t + 1, v, ги), {t,t + l,u,v) и (t + l,u,v,w), поэтому получим {{t,u){v,w) + (t,w){v,u))(f 4-1,1;) = {t,v){u,w){t + l,v); из этого следует, что (t + l,v) = О, т. е. получили противоречие. Случай 2. V + \ < W. Тогда (***) вьшолняется для {t,u,w - l,w), {u,v,w - l,w) и (t, u, и, w-1); снова получили аналогичное противоречие (u, w -1) =0. Случай 3. u = t + l и w = V + 1. Теперь условие (***) сводится к условию (**).

Подставив и = t + 1 и w = t + тп в (***), получим {t, v) = {v,t + тп) для t < v < t + тп, так как (t + l,t + тп) = 1 и {t,t + тп) = 0. Итак, элементы любого (тп - 1)-строчного узора являются периодичными: {и, v) = {v,u + тп) = {и + тп,у + тп) = (г) + тп,и + 2тп) = • • .

Каждый узор бордюра на основе положительных целых чисел содержит единицу во 2-й строке. Действительно, если положить t = 0, г) = и-Ь1им = г(-Ь2в (***), то в результате получим (О, и-ь1)(и, и-Ь2) = (О, и)-Ь(0, и-Ь2); следовательно (0,и-Ь2) -(0,и-ь1) > (О, и -f 1) - (О, и) тогда и только тогда, когда (и, и -Ь 2) > 2. Это свойство выполняется не для всех и в диапазоне О < и < m - 2, поскольку (0,1) - (0,0) = 1 и (О, тп) - (О, тп - 1) = -1.

Наконец, если m > 3, то во 2-й строке нельзя последовательно расположить две единицы, потому что из {и,и + 2) = {и + 1,и + 3) = 1 следует, что (и, и -Ь 3) = 0. Значит, бордюр с тп строками можно свести к другому бордюру, в котором содержится на одну строку меньше. Ниже показан пример приведения бордюра с семью строками к бордюру на основе шести строк.

- 1 1 1 1 1 1 1 ...

а b с а+1 1 е+1 у Z ...

р q с-Ьг d е и-¥у v w ... и q+v г s и q-¥v г s ... и+у V W р q с-Ьг d е ... у Z а b с d+\ 1 е-Ы .. 11111111

а b с d е

р q г S и V W ... и V W р q г S ... у Z а b с d е . 1111111

Приведенный бордюр соответствует некой триангуляции, что доказывается по индукции, а неприведенный бордюр соответствует присоединению к ней еще одного треугольника. [Math. Gazette 57 (1974), 87-94, 175-183; Conway and Guy , The Book of Numbers (New York: Copernicus, 1996), 74-76, 96-97, 101-102.]

Замечания. Это доказательство демонстрирует, что функция (и, и), определенная на некоторой триангуляции с помощью матриц размера 2x2, удовлетворяет условию (***) всякий раз, когда (t, и, v, w) являются сторонами многоугольника в порядке обхода по часовой стрелке. Каждую функцию (и, v) можно представить в виде полинома относительно чисел aj = {j - l,j + l). Эти полиномы идентичны континуантам из раздела 4.5.3, за исключением знаков отдельных членов. Действительно, (j,k) = г~*-Kk-j~i{iaj+i,iaj+2,... ,iak-i)-Таким образом, (***) эквивалентно тождеству Эйлера для континуантов в ответе к

упр. 4.5.3-32. Матрицы L и R обладают интересным свойством: любая матрица неотрицательных целых чисел размера 2 х 2 с детерминантом, равным 1, может быть представлена единственным образом в виде произведения L и R.

Существует также несколько других интересных соотношений, например числа в строке 2 целочисленного бордюра обозначают количество треугольников, которые касаются каждой вершины соответствующего триангулированного многоугольника. Общее количество случаев, когда (и. и) = 1 в основной области О < и < и - 1 < m - 1 и (и, и) 5 (О, m - 1), равно количеству диагоналей (хорд) триангуляции, а именно - тп - 3 = п - 1. Общее количество двоек также равно п - 1, поскольку {и,«) = 2 тогда и только тогда, когда и и tl- являются противоположными вершинами двух треугольников, смежных с хордой.

Еще одну интерпретацию функции (и, и) предложили Д. М. Бролин (D. М. Broline), Д. У. Кроу (D. W. Crowe) и И. М. Айзеке (I. М. Isaacs) [Geometriae Dedicata 3 (1974), 171-176]. Значение этой функции равно числу способов, с помощью которых можно установить соответствие для v - u - 1 вершин между ребрами и и v - 1 с различными треугольниками, смежными с этими вершинами.

РАЗДЕЛ 2.3.5

1. Структура Списка представляет собой ориентированный граф, в котором выходящие из вершин дуги упорядочены и некоторые вершины с нулевой степенью выхода обозначены как атомы. Более того, есть такая вершина S, что существует ориентированный путь от S к V для всех вершин V ф S. (Если обратить направления дзг, то S станет корнем.)

2. Не совсем так, поскольку связи-нити в обычном представлении ведут к узлу-родителю PARENT, который не является единственным для подСписков. Возможно, для этого можно использовать предложенную в упр. 2.3.4.2-25 идею или аналогичный ей метод (но эта идея еще не применялась во время написания настоящей книги).

3. Как уже упоминалось в этом разделе, докажем, что Р = РО по окончании выполнения алгоритма. Если нужно маркировать только узел РО, алгоритм, определенно, работает корректно. Если нужно маркировать п > 1 узлов, имеем АТОМ(РО) = 0. Тогда на шаге Е4 ALINK(PO) «-Ли алгоритм выполняется с РО, который заменяется на ALINK (РО), и с Т, который заменяется на РО. Согласно методу инд>кции (обратите внимание, что, так как MARK(PO) теперь равен 1, все связи с РО эквивалентны Л во время выполнения шагов Е4 и Е5) приходим к выводу, что в конце концов будут маркированы все узлы на путях, которые начинаются с ALINK (РО) и не проходят через РО. В таком случае при переходе к шагу Е6 получим Т = РО и Р = ALINK (РО). Теперь, поскольку АТОМ(Т) = 1, на шаге Е6 восстанавливаются значения ALINK (РО) и АТОМ(РО) и совершается переход к шагу Е5. На шаге Е5 BLINK (РО) 4- Л и т. д , причем согласно аналогичным доводам получим, что в конце концов будут маркированы все узлы на путях, которые начинаются с BLINK (РО) и не проходят через РО, или узлы, до которых можно добраться, начиная с ALINK (РО). Затем совершается переход к шагу Е6 со значениями Т = РО, Р = BLINK (РО). В конечном счете при переходе к шагу Е6 получается Т = Л, Р = РО.

4. В приведенной ниже программе используются усовершенствованные приемы ускоренной обработки атомов, которые упомянуты в этом разделе сразу после описания алгоритма Е.

На шагах Е4 и Е5 данного алгоритма необходимо проверить условие MARK(Q) =0 Если NODE(Q) = -ЬО, то этот особый случай можно соответствующим образом обработать, используя вместо него значение -О и рассматривая его так, как если бы в самом начале оно было равно -О, поскольку обе связи (ALINK и BLINK) равны Л в этом узле. Такое упрощение никак не повлияет на приведенную ниже оценку времени выполнения данной программы.