Файл: Лекция 18. Произведение карт.pdf

Лекция 18. Произведение карт
1. От квадрангуляций к взвешенным деревьям
Одну из вершин двукрашеной квадрангуляции объявим начальной и припишем ей вес 0. Каждой вершине припишем вес — ее расстояние до начальной вершины. Как выглядят веса на границе страны? Имеется четыре возможности:
q q
q q
n+1
n n+1
n q
q q
q n-1
n n+1
n
¾
½
»
¼
q q
q n-1
n+1
n
¾
½
»
¼
q q
q n
n n-1
Далее осуществляем обход каждой страны так, чтобы сама страна находилась при обходе справа. На границе каждой страны есть две вершины таких, что вес последующей вершины строго меньше. Эти две вершины соединяем дугой внутри страны.
r r
r r
c c
¾
»
½
¼
¶
µ
³
¡
¡
@
@
@
@
¡
¡
⇒
r r
r r
c c
¾
»
½
¼
¶
µ
³
¡
¡
@
@
@
@
¡
¡
0 2
1 2
2 1
⇒
r r
r r
c c
¾
»
½
¼
¶
µ
³
¡
¡
@
@
@
@
¡
¡
0 2
1 2
2 1
И получаем взвешенное дерево такое, что веса смежных вершин либо равны, либо отличаются на единицу.
Следует заметить, что веса белых и черных вершин имеют разную четность.
q q
q q
q
2 1
2 2
1 2. Построение карты по взвешенному дереву
Пусть нам дано плоское взвешенное дерево: вес каждой вершины — целое положительное число, веса смеж- ных вершин отличаются не более, чем на единицу, есть вершина (может быть не одна) веса 1.
Добавляем новую изолированную вершину и объявляем ее начальной вершиной веса 0. Производим обход дерева так, чтобы дерево было справа от пути обхода. Каждый раз, встретив вершину веса 1, соединяем ее дугой с начальной вершиной. Каждый раз, встретив вершину некоторого веса i > 1 соединяем ее дугой
(лежащей слева от пути обхода) с ближайшей в направлении обхода вершиной веса i − 1. Следим за тем,
чтобы дуги не пересекались.
r r
r r
r
2 1
2 2
1
⇒
r r
r r
r r
1 2
2 1
2 0
Удаляем ребра дерева и получаем квадрангуляцию. Если взвешенная дерево построено на взвешенной квад- рангуляции, то эта процедура дает нам исходную квадрангуляцию.
Замечание. Важно понимать, что карты нарисованы на сфере, а не на плоскости. Вот пример:
r r
r
2 1
1
¡¡
µ
@@
R
r r
r r
r r
r r
2 0
0 1
1 1
2 1
Эти квадрангуляции различны, как карты на плоскости, но одинаковы, как карты на сфере.
Замечание. Превратить квадрангуляцию в карту можно двумя способами. Можно считать белыми вершины с четными весами или наоборот. Карты, которые мы получаем, двойственны. Это означает, что взвешенное дерево кодирует не карту, но пару, взаимно-двойственных.
1

2
Замечание. Перечисление карт сводится к перечислению взвешенных деревьев, а это более простая задача.
Вот ответ: число карт с n ребрами и отмеченным направленным ребром равно
2 · 3
n
(n + 1)(n + 2)
· C
n
2n
∼
12
n
n
2
·
√
n
.
Замечание. Формула подразумевает, что карты нарисованы на сфере, и две карты с отмеченным направлен- ным ребром одинаковы, если одну можно совместить с другой движением по сфере.
3. Произведение карт
Пусть C — карта с отмеченным направленным ребром v. По карте C мы строим квадрангуляцию Q, в которой ребро v — это диагональ четырехугольника q квадрангуляции. По Q мы строим взвешенное дерево
T , причем в q будет лежать ребро e дерева T . Сделаем ребро направленным: если хотя бы одна вершина
e совпадает с вершиной v, то направим e в ту же сторону, что и v; если же у v и e нет общих вершин, то направление e выберем так, чтобы пара {v, e} былы правой. Таким образом, если C имеет направленное ребро, то направленное ребро есть и у T .
Пусть теперь у нас есть две карты C
1
и C
2
, а v
1
и v
2
— их отмеченные направленные ребра. T
1
и T
2
—
соответствующие взвешенные деревья, а e
1
и e
2
— их отмеченные направленные ребра. Построим взвешенное дерево T = T
1
◦ T
2
— "произведение"деревьев T
1
и T
2
. Для этого соединим конец ребра e
1
и начало ребра e
2
ребром e следующим образом: поворот от e
1
к e происходит по часовой стрелке и поворот от e к e
2
происходит против часовой стрелки. Вот так:
¡
@ - q
q q q q
¾
q q
q q
⇒
¡
@ - q
q q q q
¾
q q
q q
¾ »
Теперь нужно согласовать веса. А именно, у нас возникли две смежные вершины: конец e
1
и начало e
2
. Их веса должны отличаться не более, чем на единицу. Так что у нас есть три возможности построить взвешенное дерево: а) вес конца e
1
на единицу больше веса начала e
2
; б) веса конца e
1
и начала e
2
совпадают; в) вес конца e
1
на единицу меньше веса начала e
2
. Вот как это может быть реализовано:
-
- q
q q
q q
q q
q
Q
Q
Q
1 2
1 1
2 3
2 1
e
1
e
2
e
в начале
⇒
-
- q
q q
q q
q q
q
Q
Q
Q
4 5
4 4
2 3
2 1
e
1
e
2
e
случай а)
-
- q
q q
q q
q q
q
Q
Q
Q
3 4
3 3
2 3
2 1
e
1
e
2
e
случай б)
-
- q
q q
q q
q q
q
Q
Q
Q
2 3
2 2
2 3
2 1
e
1
e
2
e
случай в)
Осталось сделать ребро e вектором, направив его от T
1
к T
2
Замечание. Число ребер карты-произведения равно сумме числа ребер сомножителей плюс один.
Замечание. Три способа согласовать веса делают возможным каждую карту (с выделенным направленным ребром и начальной вершиной квадрангуляции) представить как произведение.
Пример. Пусть начальная вершина — столица внешней страны.
'
&
$
%
6
⇒
q q
q q
b b
b b
½
½
½
½
Z
Z
Z
Z
½
½
½
½
Z
Z
Z
Z
6 0
1 1
1 1
2 2
2
⇒
q q
q q
q q
q
1 2
2 2
1 1
1
¾
⇒
¾
1 2
q q
×
@
¡
µ
q q
q q
q
1 1
2 2
1
Окончательно:
'
&
$
%
=
µ´
¶³
q q
q
×
µ´
¶³
q
4. Упражнения
(1) Построить по проекции куба взвешенное дерево при различных выборах начальной вершины.
(2) Построить карту по цепочке с последовательными весами 1, 2, 3, . . ..
(3) Построить карту по "звезде"(вершина степени n и n вершин степени 1), где веса вершин степени 1
равны 1, а вес центральной вершины равен 2.
(4) Показать, что дерево, все вершины которого имеют вес 1, кодирует само себя.
(5) Найти код n-цикла, где нулевая вершина — столица внутренней страны.
(6) Построить карты по 3-цепочкам, с весами вершин 1-2-2, 2-1-2, 1-2-3.

3
(7) Проверить правильность формулы при n = 2.