выхода. Пусть G - регулярный диграф с п + 1 вершинами Vo, Vi,..., Vn, каждая вершина которого имеет степень входа и выхода, равную т. (Следовательно, в общем, существует (п + \)т дуг.) Пусть С-ггграф с (п + \)т вершинами, которые соответствуют дугам графа G, и пусть Vjk - вершина графа G, соответствующая дуге от V к Vt в графе G. Дуга проходит от Vjk к Vjiy в графе G тогда и только тогда, когда к = /. Например, если G - ориентированный граф, показанный на рис. 36, то граф G* представлен на рис. 37. Цепь Эйлера в графе G является цепью Гамильтона в графе G*, и наоборот.

Докажите, что количество ориентированных поддеревьев графа G* в тп""*""*" раз больше количества ориентированных поддеревьев графа G. [Указание. Используйте результат упр. 19.]

Рис. 37. Диграф с датами, который соответствует рис. 36 (см. упр. 21).

► 22. [М26] Пусть G - сбалансированный, ориентированный граф с вершинами Vi, V2, ..., V„ без изолированных вершин. Пусть Oj равно степени выхода вершины Vj. Покажите, что количество цепей Эйлера для графа G равно

(ffi -Ь (Т2 + • + (Тп) Г Y[{<i - 1)!,

где Г - количество ориентированных поддеревьев графа G с корнем Vi. Замечание. Множитель ((Tl -t- • • -I- (Tn), который равен количеству дуг графа G, можно опустить, если цепь Эйлера (ei,... ,ет) считается равной (e/t,... ,em,ei,..., ек-\)] ► 23. [МЗЗ] (Задача Н. Г. де Брейна.) Для каждой последовательности неотрицательных целых чисел х\,...,Хк, меньших, чем тп, допустим, что f(xi,... ,Xk)-неотрицательное

целое число, меньшее, чем щ. Определим бесконечную последовательность таким образом: Х\ = Х2 = - Xk = 0; Хп+к+\ = f(Xn+k,- ,Xn+i), где п > 0. Для какого количества из этих т*" возможных функ1й / последовательность будет периодичной с максимальным периодом тп*? [Указание. Постройте ориентированный граф с вершинами (xi,... ,Xk-i) для всех О < Xj < т и с дугами от (xi,X2, , Xk-i) к (х2,. ,Xk-i,Xk); примените результаты упр. 21 и 22.]

► 24. [М20] Пусть G - связный диграф с дугами во, ei,..., е. Пусть Eo,Ei,... ,Ет - множество положительных целых чисел, которые удовлетворяют закону Кирхгофа для графа G, т. е. для каждой вершины V,

Е Е

init(ej) = V fin(e,)=V

Также предположим, что Ео = 1- Докажите, что в графе G существует такой ориентированный путь от fin(eo) к init(eo), что ребро в; содержится в нем Ej раз для 1 < j < т, тогда как ребро во не входит в него вообще. [Указание. Примените теорему G к соответствующему ориентированному графу.]

25. [26] Создайте ко.мпьютерное представление ориентированных графов, которые обобщают представление дерева в виде правопрошитого бинарного дерева. Используйте два поля связи ALINK, BLINK и два однобитовых поля ATAG, BTAG так, чтобы это представление обладало следующими свойствами: (i) для каждой дуги (а не каждой вершины) ориентированного графа существует один узел; (ii) если ориентированный граф является ориентированным деревом с корнем Я и если добавить дугу от Я к новой вершине Н, то представление ориентированного графа будет точно таким же, как представление этого ориентированного дерева в виде правопрошитого бинарного дерева (с некоторым порядком, накладываемым на детей каждой семьи) в том смысле, что поля ALINK, BLINK, BTAG соответствуют полям LLINK, RLINK, RTAG из раздела 2.3 2; (iii) представление является симметричным в том смысле, что обмен полей ALINK и ATAG с BLINK и BTAG эквивалентен изменению направления всех дуг ориентированного графа.

► 26. [НМ39] (Анализ случайного алгоритма.) Пусть G - ориентированный граф с вершинами Vi,V2, . ,Vn- Допустим, что G представляет блок-схему алгоритма, где Vi - вершина блока "Начало" и Vn-вершина блока "Конец". (Следовательно, вершина V„ - корень графа G.) Предположим, что каждой дуге е графа G приписана вероятность р(е), которая удовлетворяет условиям

О < р(е) < 1; р(е) = 1 для 1 < j < 71.

in.t(e) = Vj

Рассмотрим случайный путь, который начинается в вершине Vi, а дуги е графа G последовательно выбираются с вероятностью р(е) до тех пор, пока не будет достигнута вершина V„; причем выбор дуги на каждом этапе не зависит от сделанных ранее выборов.

Рассмотрим, например, граф из упр. 2.3.4.1-7 и присвоим вероятности 1, , j, 5, 1, , , i, I дугам 61,62,... ,69. Тогда путь "Начало-А-5-С-А-/?-В-С-Конец" будет выбран с вероятностью 1 • 1 \ =

Такие случайные пути называются цепями Маркова (Markov chains) в честь русского математика Андрея Андреевича Маркова, который первым провел интенсивные исследования подобных стохастических процессов. Эту ситуацию можно применять для моделирования некоторых алгоритмов, хотя используемое условие выбора каждой дуги независимо от предыдущего пути является чрезвычайно сильным предположением. Назначение данного упражнения заключается в анализе времени вычисления алгоритмов такого типа.

Этот анализ можно упростить, если рассмотреть матрицу А = (aij) размера пх п, где aij = р{е) и сумма вычисляется по всем таким дугам е, которые проходят от вершины V; к вершине Vj. Если таких дуг -нет, то aij = 0. В рассмотренном выше примере матрица А выглядит так:

/О 1 О О О 0> О О i О i О 0 0 0 1 0 0 О i О О i i О О f О О i

\о о о о О о/

Отсюда сразу же следует, что {A)ij -это вероятность того, что путь, который начинается в вершине Vi, закончится в вершине Vj после к шагов.

Докажите справедливость приведенных ниже утверждений для произвольного ориентированного графа G указанного типа.

a) Матрица (/ - А) не является сингулярной. [Указание. Покажите, что не существует такого ненулевого вектора х, для которого хА" = х.]

b) Среднее количество появлений вершины Vj в этом пути равно

(/ - Л)Г/ = cofactoiji(/ - A)/det{I - А) для 1 < j < п,

где cofactor;)s (I-A) - принятое здесь и далее обозначение алгебраического дополнения элемента в 1-й строке и к-м столбце матрицы {I - А). [Таким образом, в рассмотренном примере показано, что вершины А, В, С, D в среднем проходятся , , раз.]

c) Вероятность того, что вершина Vj встречается в этом пути, равна

Qj = cofactoij 1 (/ - .4)/cofactor ,j (/ - А);

причем On = 1, а потому данный путь с вероятностью "единица" прекращается спустя конечное количество шагов.

d) Вероятность того, что случайный путь, начинаясь в вершине Vj, никогда вновь не пройдет через вершину Vj, равна bj = det (/ - A)/cofactor , , (/ - А).

e) Вероятность того, что вершина Vj входит в точности к раз в этот путь, равна aj(l - bjf-bj для > 1, 1 < J < п.

27. [МЗО] [Устойчивые состояния.) Пусть G - ориентированный граф с вершинами Vi,...,Vn, дуги которого имеют вероятности р[е) согласно определениям из упр. 26. Однако предположим, что вместо указания вершин "Начало" и "Конец" используется условие строгой связности графа G. Таким образом, каждая вершина Vj является корнем, а вероятности р[е) положительны и удовлетворяют условию ]Cinit(e)=rj Р[) - всех j. Тогда случайный процесс, подобный описанному в упр. 26, называется устойчивым состоянием ("steady state") [х\,... ,Хп), если

Xj = p(e)xinit(e), l<i<n.

fin(e) = \/y

Пусть tj -это сумма произведений Пеет f () взятая по всем ориентированным поддеревьям Tj графа G с корнем в вершине Vj. Докажите, что [ti,... ,tn) является устойчивым состоянием случайного процесса.