AOP_Tom1 (1021736), страница 109
Текст из файла (страница 109)
о) Вероятность того, что случайный путь, начинаясь в вершине 1'з, никогда вновь не пройдет через вершину Гтт, равна Ь = т)ес (! — А)/соГасгогВ(1 — А). е) Вероятность того, что вершина Гтт входит в точности )т раз в этот путь, равна о,(1 — Ьз)~ Ьт для Ь ) 1, 1 < 1 < и. 27. [МЯО] (Устлойчиеме состояния,) Пусть С вЂ” ориентированный граф с вершинами *тц..., 1'„, дуги которого имеют вероятности р(е) согласно определениям нз упр. 26. Однако предположим, что вместо указания вершин 'Начало" и "Конец" используется условие строгой связности графа С. Таким образом, каждая вершина 1'„является корнем, а веРоатности Р(е) положительны и УдовлетвоРЯют Угловию ~,внтй1 к Р(е) = 1 длЯ всех /.
Тогда случайный процесс, подобный описанному в упр. 2б, называется устойчивым СОСтОяНИЕМ (чЗГЕат(у ВтаГЕ") (Хц...,Х ), ЕСЛИ х; = ~ р(е) х,„щм, 1</<и. Я Г Ьпб пусть 11 — это сумма произведений П . р(е), взятая по всем ориентированным поддеретет, вьям Т, графа С с корнем в вершине Ъ;. Докажите, что (Гм, Гз) является устойчивым состоянием случайного процесса. О 1 О О О 2 О О О О $ О О 3 О О О О О О О -' О т 1 О О О 1 1 4 4 О О О О О зз ы О ага+ агз + агг + агз агз агг агз Ьм Ьы Ьзе+Ьп +Ьы О О Ьм Ь22 О Ьге+Ьгз+Ьм О Ьм Ьзг О О Ьзо + Ьзз + Ьзг с1ез Покажите, что при его разложении по степеням а и Ь каждый ненулевой член будет иметь коэфФициент +1.
Сколько членов будет содержать такое разложение? Предложите праввло для ориентированных деревьев, которое точно описывает, какие члены будут присутствовать в этом разложении. е2.3.4.3. Лемма о бесконечном дереве. До сих пор. в основном, рассматривались деревья только с конечным количеством вершин (узлов), но определения, данные для свободных и ориентированных деревьев, можно также применить для бесконечных графов.
Бесконечные упорядоченные деревья можно определить несколькими способами. Можно, например, расширить понятие десятичной системы обозначений Дьюи до бесконечных. совокупностей чисел так, как зто сделано в упр. 2.3 — 14. Даже при изучении компьютерных алгоритмов иногда возникает необходилюсть исследовать свойства бесконечных алгоритмов, яапрнмер, для доказательства от противного того, что некоторое дерево не лвллетсл бесконечным.
Одно из наиболее фундаментальных свойств бесконечных деревьев, впервые сформулированное в довольно общей форме Д. Кенигом (зг. Коп1к), выглядит так. Теорема К (Лемгаа о бесконечном дереве). В каждом бесконечном орггеитироваииом дереве, в котором квжд я вершина имеет конечную степень, имеется бесконечный путь к корню, т. е. бескоиечивл последовательность вершин 1в, 1 ы Ъг, ..., в которой 1'о — корень и бп(еЯэг1) = Ъ~ для всех у > О. Доказательство.
Определим этот путь, начиная с вершины 1в, которая является корнем ориентированного дерева. Предположим, что для некоторого у > О выбрана такаЯ веРшина гз, котоРаЯ имеет бесконечно много наслеДников. ПРеДполагается, что степень узла $' конечна, а потому 1' имеет конечное количество детей ПП...,Ь'„. По крайней мере один такой ребенок должен иметь бесконечное количество наслеДников.
ПРедположим, напРимеР, что веРшина $1ез ЯвлЯетсЯ таким ребенком вершины Ъ~. Тогда получим, что Ъш 1'з, Ъгг, ... — это бесконечный путь с началом в указанном корне. $ Студенты, изучающие математический анализ, могут легко узнать, что здесь используется такой же аргумент, как н при доказательстве классической теоремы Больцано-Вейерштрасса о том, что "ограниченное бесконечное множество действительных чисел имеет предельную точку". Другая формулировка теоремы К принадлежит Кенигу: "Если человечество никогда не вымрет, то некто из ныне живущих принадлежит роду, который никогда не вымрет".
При первом знакомстве с теоремой К складывается впечатление, что она абсолютно очевидна. Но после более внимательного обдумывания и изучения примеров ее использования становится ясно, что она имеет гораздо более глубокий смысл. ь 28.
[Муб] Рассмотрим детерминант матрицы размера (га+ п) х (га+ о), который показан ниже, для случая, когда га = 2 и п = 3: а + + Ф О а а а Хотя степень каждого узла данного дерева конечна, не предполагается, что степени ограничены (т. е. степень каждой вершины меньше некоторого д'). Поэтому могут существовать узлы со все-более и более высокими степенями. Теперь, по крайней мере, ясно, что несмотря на то, что, в конце концов, потомки всех современников вымрут, есть семьи, которые будут продолжать свой род в миллионах, миллиардах и т.
д. поколений. Действительно, Г В. Ватсон (Н. %'. %а1воп) опубликовал "доказательство" того, что если некоторые законы биологической вероятности выполняются бесконечно долго, то в будущем родится бесконечное количество людей, но каждый род вымрет с вероятностью "единица". Несмотря на небольшую ошибку, которая привела его к такому ложному выводу (интересно отметить, что он не посчитал свои выводы логически противоречивыми), в его статье, Х Апйгоро!о81са1 Епэк Сй ВНВшп ап6 1ге)ап6 4 (1874), 138 — 144, содержатся очень важные и глубокие теоремы. Противопоставленное для теоремы К утверждение непосредственно применимо для компьютерных алгоритмов: если некий алгоритм периодически делится на некоторое ограниченное подмножество подалгорнтмов, причем каждая цепь подалгоритмов конечна, го будет конечным н сам алгоритм. Иначе говоря, пусть существует такое конечное или бесконечное множество 5, что каждый его элемент является последовательностью (ям яз,..., я„) положительных целых чисел с конечной длиной и ) О.
Если выполняются условия 1) если (хы...,я„) принадлежит Я, то (яы...,яь) также принадлежит Я для 0<Й<п; й) если (яы...,х„) принадлежит 5, то существует только конечное множество таких значений х„+~, для которых (яы..., я„,я„+~) также принадлежит Я; 1й) ве существует такой бесконечной последовательности (хы хг,... ), для которой все ее начальные подпоследовательности (яы ят,..., я„) принадлежат 5, то множество 5 является, по существу, ориентированным деревом, обозначение кото1юго записано в десятичной системе обозначений Дьюи, и согласно теореме К множество 5 конечно. Некоторые наиболее убедительные примеры демонстрации потенциальных возможностей теоремы К относятся к целому ряду интересных задач о покрытиях плоскости, предложенных Хво Вангом (Нво Ч~апй). Тегпраднмй тиип (1е1га6 1уре)— это квадрат (или тетрада), разделенный на четыре части, в каждой из которых указан некоторый номер, например так, как схематически показано ниже: з 1О 2 5 Задача покрмгпил плоскости (Ыту йе р1апе) заключается в следующем.
Пусть имеется некоторое конечное множество тетрадных типов с неограниченным количеством тетрад каждого типа. Требуется предчожить способ покрытия бесконечной плоскости тетрэдами (без вращения или зеркального отображения тетрадных типов) таким образом, чтобы две тетрады были смежными, только если они соприкасаются сторонами с одинаковыми числами на них. Например, плоскость можно покрыть шестью тетрадными типами 22 12 12 21 г 12 И 1 1г И 12 и 1 з 2 и 1 2 12 г1 г з 22 (2) только одним способом, а именно — повторив прямоутольник бесконечное количество раз. Читатель может убедиться в том, что нельзя покрыть плоскость такими тремя тетрадными типами; Е г з (4) УПРАЖНЕНИЯ 1.
[М!0] В этом разделе идет речь а множестве З', которое содержит конечные последовательности положительных целых чисел, а также приводится утверждение о том, что Ванг заметил [Яс1епссбс Ашегссап 213,5 (г1очешЬег, 1985), 98-10б], что если можно покрыть верхний правый квадрант плоскости, то можно покрыть и всю плоскость. Это совершенно неожиданный результат, так как в методе покрытия верхнего правого квадранта подразумевается наличие "границы" по осям х и у, причем нет никакого намека на то, как можно покрыть верхний левый квадрант плоскости (поскольку тетрадные типы нельзя вращать или зеркально отображать).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
