1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 20
Текст из файла (страница 20)
Мы можем быть уверены, что нашли транзнтнвпое замыкание Тг (Г) ориентированного графа (А, Г), если для каждой вершины а ~ А укажем множество Тг (а) = (х) таких х, для которых пара (а, л) удовлетворяет отношению Тг (Г). Назовем Тг (а) >прапзитивным образом вершины а. Для этого мы введем для каждой вершины а стартовое множество Я и попслнясмое множество Т.
В начальный нулевой момент полон им Я<«>=(а) и Т<»> = Я. После этого определим рекуррентный процесс, определяемый следующим соотношением: Т<.»» = Ты> () Г(В>.>), В>'» = Т< +~>",Т<.>. Гл. 3. Алгогитмиэьция Г(Я) обозначает множество преемников вершин из Я. Применение соотношения продолжается до минимального п = >>Г, такого;.что У"+'> = Е>.
В этом случае Т = Т>~>. Поскольку Т<" > ие может расширяться неограниченно, очевидно, что такой момент наступит. Остается доказать лемму: Л е м м а. Т = Тг(а). Д о к а з а т е л ь с т в о. Повал«ем, что Тг(а) ~ Т. Действительно,' если вершина а' еи Тг (а), то в графе существует путь аа>.; .
а„а', что мол«но также выразить отношениями а, е Г(а), а„ен Г(а„>), а' я Г(а„). Этот путь всегда можно выбрать так, чтобы а, а„..., аа были бы все разными. Из соотношения для У"> очевидно, что а ен У»>, а> еп Г(У»>), а б= У'>, а„ен Г (У" — '>), а„еи У"> а' е= Г (У">), откуда следует, что а' еп Т<"+» а, стало быть, а' ен Т. Покажем, что Т с Тг (а). Пусть а' ~ Т. Это значит, что для некоторого и ) 0 а' ен Г (У ">).
Покажем по индукции, что для любой вершины Ь иа У"> имеет место включение Ь ен Тг(а). Для п = 1 это очевидно: У'> = Г(а)'~(а). При выполнении условия индукции У" '> с: Тг(а), а стало быть, и любой преемник любой вершины иа У" » также будет принадлежать Тг (а). т7 Мы позволили себе подробно остановиться на этом очень простом доказательстве, которое кажется настолько очевидным, что любая его формализация выглядит неуклюже. Тем не менее атот рекуррентный способ нахождения транзитизнь>х замыканий имеет настолько большое значение в различных алгоритмах на графах, что умение строго доказывать такие и аналогичные соотношения должно даваться читателю без труда.
В некоторых случаях, кроме такого рода «свободных» транзитивных замыканий, рассматривают ограниченные транзитивные замыкания, когда при движении по путям появляются «непроходимые» вершины, которые не могут принадлежать путям, соединяющим вершины, связанные транзитивным замыканием такого рода. Если Х. — множество таких непроходимых вершин, то тогда 93 : з зл. инеогмлционнын геле построение, как мы скажем, ограниченного транэитивного образа ,Тг(а!Х) выглядит следующим образом: Я(«> = Г Т(«( = Я T(и-~-!( — т'(ю () Г (я(ю) 8(ч+1) 'г(»+(]~ т(ю'~ Х Нахождение компонент связности.
В начале параграфа мы высказали ряд догадок о том, как строить информационный граф и его компоненты связности. В свете сделанных определений и описанных рекуррентных процедур мы можем теперь свести эти догадки вместе следующим образом. Введем понятие «текущей» компоненты связности.
Под словом «текущая» мы понимаем «на какой-то момент построения информационного графа». Пусть дана схема 6 = (Я, Х, Ь). В начальный момент у нас будет столько текущих компонент, сколько полюсов„ так что каждый полюс принадлежит «своей» компоненте. Пусть г — некоторый результат, (((г) — его текущая компонеята. Пусть оператор р = '»'(г), величина х = Ь(г) и я(х) — множество оператороэ схемы, вырабатывающих х. Будем строить для Р его ограниченный транзитивный образ Тг(Р(г((х)), которое обозначим короче, Е(г).
Пусть а(„...,а;„— аргументы операторов из Е(г), для которых Ь(а(,) = ... =Ь(а(„) =х, а ()(а(,), ...,()(а(„)— их текущие компоненты. Тогда информационный граф пополняется информационными связями (г, а;,), ..., (г, а, ), а всем полюсам г, а;„, ..., а; сопоставляется общая новая текущая компонента((' =(((г) () (((а(() () ... () ()(а(„). Это построение делается для каждого результата схемы.
В итоге мы получим некоторое множество М информационных связей и некоторое количество подмножеств полюсов: Р = (((,..., (((). Утверждается, что граф (Р, М) будет информационным графом»' схемы С, а Р— искомым разбиением ее полюсоз по компонентам связности графа Х. Нижеследующее доказательство только что сделанного утверждения читатель может пропустить, но только при условии, что он будет в состоянии самостоятельно провести соответствующее рассу»пление. Мы же проведем доказательство хотя бы для того, чтобы дать возможность менее опытному читателю проконтролировать себя. Сначала опишем процедуру построения болев точно, так чтобы это описание действительно напоминало алгоритм. Будем использовать стандартные обозначения операторной схемы, введенные в пррдыдущей главе. Полол(им в' начальный момент ((( = (я,), ..., ((, = (я„), М' = Я.' Для каждого ( = 1, ..., д рассмотрим результат.г,.
Найдем в ааданной схеме следующие объекты и множества; х = Цг,); Р = »г(г(); Л(х) — множество операторов, вырабатывающих. х. гл. 3. Алгогитыиза>п>я Построим по индукции следующие множества: с>з> (Р) Гю> т>- >=Г>->() Г(Е «) Е>- » =т~--»'~Г> ~,Л(х) В процессе построения для кая<дого а;, такого, что Ца,) = х, а У(а>) е= Г(Я>">), образуем д' = г(> () д;, н заменяем им как >>>, так и дт, и вносим пару (ги а;) в М'. Условием окончания работы с г> является достижение такого и, что Я>"+» = Я. Пусть М' — результирующее множество пар, »'„..., »>— результирующие различные множества среди текущих компонент д„..., Ы„. Пусть 1 = (Р, М) — информационный граф и Р> = = (Р;, М;) — его компонента связности (> = 1,..., >).
Покажем, что М = — ЛХ', ) = У н (>(>...,,с(>) = (Р„..., Р,). Доказательство разобъем на несколько лемм. а) М ~ М'. По определению информационной пары (г>, а ) существует маршрут (г,, а>) Р;, ... Р>, в котором Ь (г,) = Ь (и;) = х; Р;, = У(г>), Р;„= У (а>), и ни один из Рн ...Р,, не вырабатывает х. Тогда из определения транзитивного обрааа Тг (У(г>)>Р> (х)) вытекает, что оператор Р>депЕ(г>), а стало быть, существует и, для которого Р>„ел Г(Я").
По построес пию пара (ги а;) в таком случае вносится в множество пар. « б) М' с: М. Рассмотрим пару (го а;), внесенную в М'. По построению это произошло при некотором значении и при нахождении множеств Т>"+» и Г(Я>">). Другими словами, У(а;) = Г(Я>">), при этом Ь(а>) = Ь(г>) = х. По построению Я>"> существует цепочка операторов Л>„..., Р,„такая, что Р;, = — У(г>), Р> енГ(Р»)(1(~и<~ и); при этом ни одни из Р, не вырабатывает х. Но в таком случае конструкция (г,, а>) Р;„... Р,„У (ат) удовлетворяет определению маршрута, откуда следует, что (гм а;)~М.
т7 в) Для каждого»> при фиксированном порядке рассмотрения результатов г„..., гч построение аадает некотору>о единственную последовательность объединений его элементов в результирующее множество. Докажем интересующие нас свойства множеств 4 индукцпей по порядковым номерам этой последовательности. В начальный момент, очевидно, все неравные друг другу текущие компоненты: а) попарно не пересекаются, р) в сумме составляют все мноя<ества полюсов, % хь пнФОРкапионнын ГРАю у) каждое множество полностью входит в одно из Рь (л = 1,..., ().
Рассмотрим теперь любой шаг объединения некоторых текущих компонент г(; и г(з в (гГ = и; () И~). Остальные множества при етом остались без изменений. Очевидно, что гу в совокупности с остальными множествами будет по-прежнему удовлетворять свойствам а) и р). Пусть й; с Рч и дт с: Р, (1 С и, и( 1). По построению имеется г;Ы; п а,И., образующие в схеме информационную пару. В силу транзитивности связности (лемма из теоремы 1, $2.2), мы сразу получаем, что и г(~ и Ия а, стало быть, и пх объединение гГ принадлежат одному и тому же множеству вершин Р„компонент свяаности 0„. ~ г) Нам осталось показать, что 1 = Г по окоячании построения Е(гт) для всех результатов схемы.
Предоставив читателю догадаться, почему Г не может быть меньше (, предполоягим, что 1 < Г. Это значит, что есть хотя бы две различные текущие компоненты П; и И;, каждая из которых содержится в некотором Р . Из этого факта, а также из свойства а) следует, что в 4 и г(,' есть по одному полюсу, которые образуют пару (г, а), являющуюся дугой в компоненте связности Р„информационного графа схемы. В силу леммы а) (г, а)яМ', а это значит, что по построению М' существует некоторое и, при котором оператор У(а) принадлежит Г(Я< ">), пара (г, а) внесена в М', а И(г) и И(а) объединены в новую текущую компоненту, общую как для г, так и для о, что противоречит допущению о различности г('; и Ы~ ту Последние две леммы позволягот заключить, что (Контрольный вопрос читателю: почему последнее заключение мы не пишем в форме 4 = Р; '(~ = 1,..., () г) Для лучшего освоения описанного алгоритма построения информационного графа и выделения его компонент связности мы рекомендуем читателю проверить его.работу на примерах хотя бы нз первой главы.
Для ориентации и подсказки, как разместить данные на бумаге, мы воспроизведем результаты работы алгоритма для примера 11 (алгольная программа с процедурой). На рис. 3.1 перерисована операторная схема, в которой для операторов и полюсов в качестве обозначений взяты просто их порядковые номера. Поскольку как на картинке, так и в таблице в каждой позиции понятно, номером чего является стоящее в позиции число, мы не употребляем буквенных обозначений элементов схемы, за исключением имен величин из памяти. Это поможет читателю более формально проверить работу алгоритма, а кроме того, г- ! ~- се! со , 'ос~ ! ю1 )О3 ссс! ф сс со с ! сч сс е'! сс! х а'о оЗо й:о.О хй ° с .о о.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
