AOP_Tom1 (1021736), страница 170
Текст из файла (страница 170)
Для завершения доказательства взаимно однозначного где и+ 1 и е+ 1 — последователи и и е в направлении обхода по часовой стрелке. Доказательство этого утверждения выполняется с помощью метода индукции по гп. Соотношение (ь) тривиально для т = 2, так как два параллельных ребра и и е связаны соотношениями и = ее, а а ы е — единичная матрица. Если произвольную триангуляцию дополнить некоторым ребром е с треугольником ее'е", то из е = иа будет следовать, что е = иау и е" = иаН. Значит, (и,е') и (и,е") в этом расширенном многоугольнике соответственно равны (и,е) и (и,е) + (и,е + 1) из исходного многоугольника.
Отсюда следует, что соответствия нужно показать, что каждый (т — 1)-строчный узор бордюра, сложенный из положительных целых чисел, можно подучить на основе некоторой триангуляции. Расширьте заданный произвольный узор из т-1 строк за счет вставки новой О-й страки сверху н новой т-й строки снизу,которые состоят только из нулей.
Обозначим теперь все элементы О-й строки символамн (О.О),(1,1),(2,2) и т. д., а для всех неотрицательных целых чисел и < о < и + т предположим, что (и, о) — это элемент, направленный на юговосток по диагонали от (и, и) и на юго-запад по диагонали от (о, о). Предполагается, что условие (««) выполняется для всех и < и < и+ т. Действительно, его можно расширить до значительно более общего соотношения (»,и)(о,ш) + (»,и)(и,о) = (»,и)(и,ш) для» < и < е < ш <»+ т.
(«««) 1 1 1 1 1 1 1 1 а Ь с 4+1 1 е+1 у р Ч с+г »» е и+у о ш и Ч+о г э и Ч+и г и+у о ш р Ч с+г 4 у с а Ь с»»+1 1 1 1 1 1 1 1 1 1 1 1 1 1 а Ь с 4 е у Ч г э и о ю Р Ч у з а Ь с»» е 1 1 1 1 1 1 1 е 1 е+1 1 1 Приведенный бордюр соответствует некой триангуляции, что доказывается по индукции, а неприведенный бордюр соответствует присоединению к ней еще одного треугольника. (Ма»Л. Сазе»»е 37 (1974), В7 — 94, 175-1В3; Сопиау авб Спу, ТЛе Воой ог" МишЬегэ ((Чек Уогус Сорога(спэ, 1996), 74 — 76, 96 — 97, 101-102.] Замечания.
Это доказательство делюнстрирует, что функция (и, и), определенная на некоторой триангуляции с помощью матриц размера 2 х 2, удовлетворяет условию (**«) всякий раз, когда (», и, о, и) являются сторонами многоугольника в порядке обхода по часовой стрелке. Каждую функцию (и, е) можно представить в виде полинома относительно чисел аз = (1 — 1, 1+ 1). Эти полиномы идентичны контннуантам из раздела 4.3.3, за исключением знаков отдельнгах членов.
Действительно, (1,Ь) = »' ~~~Кь, »(»а,+м»аз м...,»аь-») Таким образом, («««) эквивалентно тождеству Эйлера для континуантов в ответе к Если утверждение («««) ложно, пусть (», и, в, ш) — контрпример с наименьшим значением (ш — »)т+ и — » -ь ш — о. случай 1. » ч-1 < и, тогда («««) выполняется для (»,»+ 1, е,и), (»,» + 1,и,о) и (» + 1,и,о,ш), поэтому получим ((»,и)(и,ш) + (»,ш)(о,и))(» + 1,о) (»,и)(и,ш)(» + 1,е); из этого следует, что (» + 1,о) = О, т.
е. получили противоречие. Случай й е+ 1 < ш. Тогда («««) выполняется для (»,и,ш — 1,ш), (и,о,ш — 1,ш) и (», и, о, ш — 1); снова получили аналогичное противоречие (и, ш — 1) = О. Случаи 3. и = »+ 1 и ш = о+ 1. Теперь условие («««) сводится к условию (««). Подставив и = » + 1 и ш = » Ч- т в (««*), получим (», и) = (и, » + тл) для» < в <» + т, так как (»+ 1, » 4- т) = 1 и (»,»+ т) = О. Итак, элементы любого (т — 1)-строчного узора являются пернодичными: (и, о) = (о, и + т) = (и + т, о + т) = (е + т, и + 2т) = Каждый узор бордюра на основе положительных целых чисел содержит единицу во 2-й строке.
Действительно, если положить» = О, и = и+ 1 и ш = и+ 2 в («««), то в результате получим (О, и+ 1) (и, и+ 2) = (О, и) + (О, и+2); следовательно (О, и+ 2) — (О, и 4-1) > (О, и + 1) — (О, и) тогда и только тогда, когда (и, и + 2) > 2. Это свойство выполняется не для всех и в диапазоне 0 < и <»и — 2, поскольку (О, 1) — (О, 0) = 1 и (О, т) — (О, т — 1) = — 1. Наконец, если т > 3, то во 2-й строке нельзя последовательно расположить две единицы, потому что из (и, и+ 2) = (и+ 1, и + 3) = 1 следует, что (и, и+ 3) = О. Значит, бордюр с т строками можно свести к другому бордюру, в котором содержится на одну строку меньше.
Ниже показан пример приведения бордюра с семью строками к бордюру на основе шести строк. упр. 4.5.3-32. Матрицы Ь и )7 обладают интересным свойством: любая матрица неотрицательных целых чисел размера 2 х 2 с детерминантом, равным 1, может быть представлена единственным образом в виде произведения Ь и Я, Существует также несколько других интересных соотношений, например числа в строке 2 целочисленного бордюра обозначают количество треугольников, которые касаются каждой вершины соответствующего триангулированного многоугольника. Общее количество случаев, когда (и.
с) = 1 в основной области О < и < п — 1 < гп — 1 и (и, и) Ф (О, гп — 1), равно количеству диагоналей (хорд) триангуляции, а именно — гл — 3 = и — 1. Общее количество двоек также равно п — 1, поскольку (и, с) = 2 тогда и только тогда, когда и и п являются противоположными вершинами двух треугольников, смежных с хордой. Еще одну интерпретацию функции (и, и) предложили Д.
М. Бролин (П. М. Вго!ше), Д. У. Кроу (1). ЪЧ. Сгоне) и И. М. Айзеке (1. М. 1эаасэ) [Сеошеглж Ресбсаса 3 (1974), 171 — 17б]. Значение этой функции равно числу способов, с помощью которых можно установить соответствие для е — и — 1 вершин между ребрами и и с — 1 с различными треугольниками, смежными с этими вершинами. РАЗДЕЛ 2.3.5 1.
Структура Списка представляет собой ориентированный граф, в котором выходящие из вершин дуги упорядочены и некоторые вершины с нулевой степенью выхода обозначены как атомы. Более того, есть такая вершина Я, что существует ориентированный путь от 5 к 1' для всех вершин 1г ~ Я. (Если обратить направления дуг, то 5 станет корнем.) 2.
Не совсем так, поскольку связи-нити в обычном представлении ведут к узлу-родителю РАВЕМТ, который не является единственным для подСписков. Возможно, для этого можно использовать предложенную в упр. 2,3,4.2-25 идею или аналогичный ей метод (но эта идея еще не применялась во время написания настоящей книги). 3. Как уже упоминалось в этом разделе, докажем, что Р = РО по окончании выполнения алгоритма.
Если нужно маркировать только узел РО, алгоритм, определенно, работает корректно. Если нужно маркировать и > 1 узлов, имеем АТОМ(РО) = О. Тогда на шаге Е4 АЫМК(РО) ~- Л и алгоритм выполняется с РО, который заменяется на А11ИК(РО), и с Т, который заменяется на РО. Согласно методу индукции (обратите внимание, что, так как ИАВК(РО) теперь равен 1, все связи с РО эквивалентны Л во время выполнения шагов Е4 и Е5) приходим к выводу, что в конце концов будут маркированы все узлы на путях, которые начинаются с А11МК(РО) и не проходят через РО. В таком случае при переходе к шагу Еб получим Т = РО и Р = А1.1МК(РО). Теперь, поскольку АТОИ(Т) = 1, на шаге Еб восстанавливаются значения А11ИК(РО) и АТОМ(РО) и совершается переход к шагу Е5. На шаге Е5 В51ИК(РО) ь- Л и т. д, причем согласно аналогичным доводам получим, что в конце концов будут маркированы все узлы на путях, которые начинаются с В(.ТИК(РО) и не проходят через РО, или узлы, до которых можно добраться, начиная с А51МК(РО).
Затем совершается переход к шагу Еб со значениями Т = РО, Р = ВВТМК(РО) . В конечном счете при переходе к шагу Еб получается Т = Л, Р = РО. 4. В приведенной ниже программе используются усовершенствованные приемы ускоренной обработки атомов, которые упомянуты в этом разделе сразу после описания алгоритма Е. На шагах Е4 и Е5 данного алгоритма необходимо проверить условие ИАВК(О) = О Если МОВЕ(О) = +О, то этот особый случай можно соответствующим образом обработать, используя вместо него значение — О и рассматривая его так, как если бы в самом начале оно было равно -О, поскольку обе связи (А51МК и ВНИК) равны Л в этом узле. Такое упрощение никак не повлияет на приведенную ниже оценку времени выполнения данной программы.
(для установки маркировочных битов НАВК). г11 = Р, г12 гя Т, г13 гя Ц и гХ = -1 г~. и . ~о. Т с-Л. гХ с- — 1. ~г. н . а~< ) ЕЗ. Атому Выполнить переход, если АТОИ(Р) = О. Еб. Вввеою Ц -Т, и — 1 и — 1 и — 1 ст сз сз се 11 с Выполнить переход, если АТОИ(Т) = 1, Т с — ВПИК 02) . ВПИК(Ц) с- Р. Р+- Ц. АТОН(Т) +- О. Т +- А1.1ИК(Ц). А1.1ИК(Ц) +- Р. Р с- Ц. Е5. Вниз по связям ВЬТИК. Ц С- В1 ТИК(Р) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
