Настоящее упражнение основано на идее, которую автору сообщил В. Ч. Линч (W. С. Lynch). Можно ли, используя такое представление, обобщить алгоритмы обхода деревьев, подобные алгоритму 2.3.IS, для классов диграфов, которые не являются ориентированными деревьями?

27. Пусть Oij -сумма вероятностей р(е) для всех дуг е от Vi к V. Следует доказать, что tj = Eiij*! ДЛЯ всех j. Так как 5Zij = 1> необходимо доказать, что Ylijitj = EiJ*-Но это не так уж и трудно, поскольку обе стороны равенства представляют сумму всех произведений p(ei). . .р(е„), взятую по всем подграфам {ei,..., е„} такого графа G, что init(ei) = Vi и в нем существует единственный ориентированный цикл, который содержится в {ei,..., е„} и включает вершину Vj. Удалив любую дугу этого цикла, можно получить ориентированное дерево. Левую сторону равенства можно получить, разложив по дугам, выходящим из вершины Vj, тогда как правая сторона равенства соответствует разложению по дугам, входящим в Vj.

В некотором смысле это упражнение является комбинацией упр. 19 и 26.

28. Каждый член этого разложения имеет вид произведения aipj ... Птрт biqi hnq , где О < Pi < п для 1 < г < m и О < д> < т для I < j < п, которое умножено на некоторый целочисленный коэффициент. Представьте это произведение в виде ориентированного графа с вершинами {0,ui,... ,Um,vi,... ,Vn} и дугами от щ к Vp. и от Vj к Uq-, где uo = Vo = 0.

Если этот диграф содержит цикл, целочисленный коэффициент будет равен нулю. Каждому такому циклу соответствует множитель вида

где индексы {io,ii,... ,ik-i) различны и также различны индексы {jo,ji, ,jk-i)- Сумма всех членов, содержащих (*) в качестве множителя, является детерминантом, который получается при условии, что o,,j <~ [j=ji] для О < j < п и bjii 4- [г = J(i+i) mod fc] Для О < г < m при О < / < fc, тогда как переменные в других т + п - 2к строках остаются неизменными. Этот детерминант тождественно равен нулю, потому что сумма строк to, il, ..., ik-i в верхней части равна сумме строк jo, ji, . , jk-i в нижней части.

С другой стороны, если ориентированный граф не содержит циклов, то целый коэффициент будет равен 4-1. Это следует из того, что все множители а,р. и fej, должны находиться на диагонали детерминанта: если любой недиагональный элемент aij выбран в строке го в верхней части, то необходимо выбрать некоторый недиагональный элемент bjoii из столбца jo в левой части. Следовательно, затем необходимо выбрать некоторый недиагональный элемент djijj из строки п в верхней части и т. д., образуя замкнутый цикл.

Таким образом, коэффициент равен 4-1 тогда и только тогда, когда соответствующий диграф является ориентированным деревом с корнем 0. Количество таких членов (а значит, и количество таких ориентированных деревьев) получается за счет установки каждого Uij и bji равным 1, например

/4 О 1 1 1\

О 1 1 \1

1 О

1 1 О О

= det

1 0 0 3/

/40 -4 4 1 1

0 0-3

1 1 1\

ООО 3 0 0

4 0 0 -3 0 3/

= det

= det

/4 О 3 1 1\

0 4 0 0 0

2 13 0 0

0 0 0 3 0

Vo О О О з/

4 3

2 3

•4-3-3.

В общем, получим det() • (n 4- l)""" • (ш 4-1)"-.

Замечания. Дж. Дж. Сильвестр (J. J. Sylvester) рассмотрел особый случай, когда

О [Quarteriy J. of Pure and Applied Math. 1 (1857), 42-56], и справедливо предположил, что общее количество членов равно п"(п + 1)"". Он также утверждает без доказательства, что количество ненулевых членов равно (п 4- 1)"~\ если aij = Sij соответствуют всем связным графам без циклов с верщинами {0,1,..., п}. В этом особом случае он свел детерминант к виду, рассмотренному в теореме о дереве матрицы из упр. 19, например

/ Ью + fel2 + bi3

-Ь21

-Ьз1

Ьго +b2i + Ьгз

-Ьз2

-bia \

-623

бзо 4- Ьз1 + Ьз2 /

Кэли (Cayley) цитирует этот результат [Creiie 52 (1856), 279], приписывая его Сильвестру; таким образом, по иронии судьбы теорема о количестве таких графов часто приписывается Кэли.

Меняя знак элементов первых т строк данного детерминанта на противоположный, а затем меняя знак элементов первых т столбцов, можно свести данное упражнение к теореме о матрице дерева.

[Рассмотренные в настоящем упражнении матрицы общего вида имеют большое значение для итеративных методов решения уравнений в частных производных. Их часто называют матрицами, обладающими свойством А (property Л) [см., например, Louis А. Hageman and David М. Young, Applied Iterative Methods (Academic Press, 1981), Chapter 9.]

РАЗДЕЛ 2.3.4.3

1. Корнем является пустая последовательность, а дуги проходят от {xi,...,x„) к (Х1,... ,a;„ i).

2. Возьмем один тетрадный тип и повернем его на 180°, чтобы получить другой тетрадный тип. Очевидно, что эти два тетрадных типа позволяют полностью покрыть плоскость (без дальнейших вращений), копируя фрагменты размером 2x2.

3. Рассмотрим множество тетрадных типов IZ для всех положительных целых

чисел j. Правую половину плоскости можно покрыть несчетным числом способов, но при размещении любого квадрата в ее центре устанавливается конечный предел расстояния, на которое это покрытие может быть продолжено влево.

4. Необходимо последовательно перебрать все возможные варианты покрытия с помощью блоков размером п х п для п = 1,2,..., проводя поиск тороидальных решений внутри блоков. Если покрыть плоскость нельзя, то согласно лемме о бесконечном дереве существует такое п, для которого нет решений размером п х п. А если есть способ покрытия плоскости, то согласно этому предположению существует такое п, для которого есть решение размером п х п, содержащее прямоугольник тороидального решения. Следовательно, в любом случае алгоритм прекратит работу за конечное число шагов. (Но, как будет показано в следующем упражнении, это утверждение ложно: на самом деле нет алгоритма, который позволяет за конечное число шагов определить, существует ли споеоб покрытия плоскости с помощью заданного множества тетрадных типов.)

5. Начнем с того, что фрагменты ° должны присутствовать в любом решении в виде групп 2x2. Тогда необходимо выполнить следующие действия. Этап 1: рассмотрим только

Q-тетрады и покажем, что фрагмент ° J должен повторяться в а-тетрадах в виде групп 2x2. Этапы п > 1: определим фрагмент, который должен находиться в крестообразной области с высотой и шириной 2" - 1, причем внутренняя часть крестов содержит фрагмент вида , который повторяется по всей плоскости.

Например, после этапа 3 содержимое блоков 7 х 7 по всей плоскости будет отделяться друг от друга полосами единичной ширины через каждые восемь единиц. Блоки 7 х 7 с Ла-тетрадой в центре имеют вид

"Крест" образуют средний столбец и средняя строка, которые заполняются на этапе 3; другие четыре квадрата 3x3 заполняются на этапе 2; квадраты справа и снизу от этого квадрата 7x7 являются частью креста размером 15 х 15, который заполняется на этапе 4.

Аналогичное построение, которое приводит к набору только из 35 тетрадных типов и содержит только тороидальные решения, можно найти в работе R. М. Robinson, Jnventiones Math. 12 (1971), 177-209. Робинсон также продемонстрировал набор из шести квадрато-образных форм, которые покрывают плоскость только нетороидальным образом, даже с использованием вращений и зеркальных отображений. В 1974 году Роджер Пенроуз (Roger Penrose) обнаружил набор из двух многоугольников, которые основываются не на квадратной решетке, а на "золотом" отношении и покрывают всю плоскость только апериодически. Это приводит к множеству всего 16 тетрадных типов лишь с нетороидальными решениями [см. В. Griinbaum and G. С. Siiepiiard, Tilings and Patterns (Freeman, 1987), Chapters 10-11; Martin Gardner, Penrose Tiles to Trapdoor Ciphers (Freeman, 1989), Chapters 1-2].

6. Пусть кит фиксированы. Рассмотрим ориентированное дерево, каждая вершина которого представляет для некоторого п одно из разбиений {1,...,п} на к частей, не содержащих арифметических прогрессий длины т. Узел, который представляет разбиение {1,...,п4-1}, является ребенком одного из разбиений {1,..., п}, если оба они совпадают в части {1,..., п}. Если бы существовал бесконечный путь от корня этого дерева, можно было бы разделить все целые числа на к множеств без арифметических прогрессий длины т. Следовательно, согласно лемме о бесконечном дереве и теореме Ван дер Вардена это дерево конечно. (Если /с = 2 и m = 3, его структуру можно достаточно быстро определить вручную и наименьшим значением Л будет 9.)

7. Положительные целые числа можно разбить на два таких множества So и Si, которые не содержат бесконечной вычислимой последовательности (см. упр. 3.5-32). Так, в частности, они не содержат бесконечной арифметической прогрессии. Теорема К здесь неприменима, потому что не существует способа включения частичных решений в дереве с конечными степенями в каждой вершине.

8. Назовем контрпримером последовательности бесконечную последовательность деревьев, для которой нарушается теорема Крускала, если таковые последовательности вообще существуют. Предположим, что данная теорема неверна, и в этом случае пусть Ti - такое дерево с минимально возможным количеством узлов, что Ti может быть первым