► 28. [М35] Рассмотрим детфминант матрицы размера (т + п) х (т + п), который показан ниже, для случая, когда m = 2 и п = 3:

/ аю + ац + ai2\ai3 О ац ai2 ais

О 0,20 + 0,21 + 22 + 0,23 0,21 0,22 423

det fill bi2 bio-f-611+612 0 0

621 622 0 620+621+622 0

Л 631 632 О О Ьзо + 631 + 6з2 /

Покажите, что при его разложении по степеням а и 6 каждый ненулевой член будет иметь коэффициент +1. Сколько членов будет содержать такое разложение? Предложите правило для ориентированных деревьев, которое тОчно описывает, какие члены будут присутствовать в этом разложении.

*2.3.4.3. Лемма о бесконечном дереве. До сих пор, в основном, рассматривались деревья только с конечным количеством вершин (узлов), но определения, данные для свободных и ориентированных деревьев, можно также применить для бесконечных графов. Бесконечные упорядоченные деревья можно определить несколькими способами. Можно, например, расширить понятие десятичной системы обозначений Дьюи до бесконечных совокупностей чисел так, как это сделано в упр. 2.3-14. Даже при изучении компьютерных алгоритмов иногда возникает необходимость исследовать свойства бесконечных алгоритмов, например, для доказательства от противного того, что некоторое дерево не является бесконечным. Одно из наиболее фундаментальных свойств бесконечных деревьев, впервые сформулированное в довольно общей форме Д. Кенигом (D. Konig), выглядит так.

Теорема К {Лемма о бесконечном дереве). В каждом бесконечном ориентированном дереве, в котором каждая вершина имеет конечную степень, имеется бесконечный путь к корню, т. е. бесконечная последовательность вершин Vq, Vi, Va, • • •, в которой Vo -корень и йп(е[У+1]) = Vj для всех j > 0.

Доказательство. Определим этот путь, начиная с вершины Vq, которая является корнем ориентированного дерева. Предположим, что для некоторого j > О выбрана такая вершина Vj, которая имеет бесконечно много наследников. Предполагается, что степень узла Vj конечна, а потому Vj имеет конечное количество детей U\,... ,Un- По крайней мере один такой ребенок должен иметь бесконечное количество наследников. Предположим, например, что вершина Vj+i является таким ребенком вершины Vj.

Тогда получим, что Vq, Vi, V, ... -это бесконечный путь с началом в указанном корне. I

Студенты, изучающие математический анализ, могут легко узнать, что здесь используется такой же аргумент, как и при доказательстве классической теоремы Больцано-Вейерштрасса о том, что "ограниченное бесконечное множество действительных чисел имеет предельную точку". Другая формулировка теоремы К принадлежит Кенигу: "Если человечество никогда не вымрет, то некто из ныне живущих принадлежит роду, который никогда не вымрет".

При первом знакомстве с теоремой К складывается впечатление, что она абсолютно очевидна. Но после более внимательного обдумывания и изучения примеров ее использования становится ясно, что она имеет гораздо более глубокий смысл.

Хотя степень каждого узл данного дерева конечна, не предполагается, что степени ограничены (т. е. степень каждой вершины меньше некоторого N). Поэтому могут существовать узлы со все-олее и более высокими степенями. Теперь, по крайней мере, ясно, что несмотря на то, что, в конце концов, потомки всех современников вымрут, есть семьи, которые будут продолжать свой род в миллионах, миллиардах и т. д. поколений. Действительно, Г. В. Ватсон (Н. W. Watson) опубликовал "доказательство" того, что если некоторые законы биологической вероятности выполняются бесконечно долго, то в будущем родится бесконечное количество людей, но каждый род вымрет с вероятностью "единица". Несмотря на небольшую ошибку, которая привела его к такому ложному выводу (интересно отметить, что он не посчитал свои выводы логически противоречивыми), в его статье, J. Anthropoiogicai Inst. Gt. Britain and Ireland 4 (1874), 138-144, содержатся очень важные и глубокие теоремы.

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

Иначе говоря, пусть существует такое конечное или бесконечное множество 5, что каждый его элемент является последовательностью {xi,X2, ,х„) положительных целых чисел с конечной длиной п > 0. Если выполняются условия

i) если {х\,... ,Хп) принадлежит 5, то {xi,... ,Xk) также принадлежит 5 для О < А: < п;

ii) если (xi,... ,Хп) принадлежит 5, то существует только конечное множество таких значений Xn+i, для которых (a;i,..., Xn,Xn+i) также принадлежит 5;

iii) не существует такой бесконечной последовательности (xi,X2, ), для которой все ее начальные подпоследовательности {xi,X2, , Хп) принадлежат 5,

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

Некоторые наиболее убедительные примеры демонстрации потенциальных возможностей теоремы К относятся к целому ряду интересных задач о покрытиях плоскости, предложенных Хао Вангом (Нао Wang). Тетрадный тип {tetrad type) - это квадрат (или тетрада), разделенный на четыре части, в каждой из которых указан некоторый номер, например так, как схематически показано ниже:

Задача покрытия плоскости {tiling the plane) заключается в следующем. Пусть имеется некоторое конечное множество тетрадных типов с неограниченным количеством тетрад каждого типа. Требуется предложить способ покрытия бесконечной плоскости тетрадами (без вращения или зеркального отображения тетрадных типов) таким образом, чтобы две тетрады были смежными, только если они соприкасаются сторонами с одинаковыми числами на них. Например, плоскость можно покрыть

шестью тетрадными типами

только одним способом, а именно - повторив прямоугольник

бесконечное количество раз. Читатель может убедиться в том, что нельзя покрыть плоскость такими тремя тетрадными типами:

Ванг заметил [Sdentific American 213,5 (November, 1965), 98-106], что если можно покрыть верхний правый квадрант плоскости, то можно покрыть и всю плоскость. Это совершенно неожиданный результат, так как в методе покрытия верхнего правого квадранта подразумевается наличие "границы" по осям х и у, причем нет никакого намека на то, как можно покрыть верхний левый квадрант плоскости (поскольку тетрадные типы нельзя вращать или зеркально отображать). При этом нельзя отделаться от границы просто за счет сдвига верхнего правого квадранта вниз и влево, так как сдвиг имеет смысл вьшолнять только на конечную величину. Вот как выглядит доказательство Ванга. Из существования решения для покрытия правого верхнего квадранта следует, что для любого п существует способ покрытия квадрата 2п х 2п. Множество всех решений задачи покрытия квадратов с четной длиной сторон образует ориентированное дерево, если дети каждого решения х размера 2п х 2п являются решениями размера (2п + 2) х (2п + 2), которые могут быть получены путем окаймления решения х. Корнем такого дерева является решение размера 0x0, его детьми - решение размера 2 х 2 и т. д. Каждый узел имеет только ограниченное количество детей, так как в задаче покрытия плоскости предполагается, что для покрытия может использоваться только конечное множество тетрадных типов. Следовательно, согласно лемме о бесконечном дереве существует бесконечный путь к корню. Это значит, что существует способ покрытия всей плоскости (хотя, возможно, его не так уж просто будет найти!).

Описание дальнейшего развития исследований в области тетрадного покрытия плоскости можно найти в прекрасной книге Б. Грюнбаума и Дж. К. Шепарда [Tilings and Patterns by В. Griinbaum and G. C. Shephard (Freeman, 1987), Chapter 11].

УПРАЖНЕНИЯ

1. [MIO] в этом разделе идет речь о множестве 5, которое содержит конечные последовательности положительных целых чисел, а также приводится утверждение о том, что