Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[33]

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

Пусть (ni,n2) G P. Пусть для i = 1,2 дуга щ является дугой итеранта C (допускается равенство C1 = C2). Тогда будем говорить, что итеранты 1 и 2 сцеплены. Итерант C, сцепленный с C1 (или C2), считаем сцепленным с C2 (с C1 соответственно).

Таким образом, на множестве итерантов Dграфа определяется рефлексивное, симметричное и транзитивное отношение сцепленности.

Пример 8. Пусть для Dграфа, представленного следующим рисунком,

P = {(1, 4), (2, 3), (5, 6), (5,10), (1, 7), (9, 8)}.

146 10 8

-о- о-о-о-

Тогда его три сильно связные компоненты сцеплены друг с другом.

Здесь дуги 1, 5 парны соответственно линейным дугам 7,10. Однако они являются дугами итерантов, так как парны соответственно дугам 4, 6 сильно связной компоненты, не имеющей линейных в данном D графе дуг. Правда маршрутов, в которых дуги 1 и 4 образуют гнезда, не существует. В самом деле, единственный путь из end(1) в beg(4) состоит из дуги 2, т.е. не является нейтральным маршрутом.

3.2.3. Расширение понятия форманта

Рассматриваемое расширение позволит при обработке Dграфа обходиться более короткими маршрутами на итерантах. В число формантов будут включены и некоторые нейтральные маршруты. Для построения ненейтрального форманта, достижимого из некоторой фиксированной вершины итеранта, требуется "прой ти", вообще говоря, более короткий маршрут, чем в случае, когда нейтральность форманта была обязательна.

3.2.3.1. Вставки и схемы. В определении вставки фиксируется наблюдение о том, что для разрастания маршрутов можно использовать и некоторые неней тральные циклы.

Схемы определяются в терминах вставок. Они родственны канонам весьма частного вида.

Пусть T - цикл, p(T) = T1T2, T1 G Right(V)*, T2 G Left(P)*, MT2T1) = Л. Тогда назовем цикл T Rbctsbkou .

Заметим, что Tk,k > 1, является циклическим маршрутом и ц(Тk) = (T). Является маршрутом и путь T3T4, если T3TT4 - маршрут, в котором T есть R-вставка. Таким образом, замена R вставки любой ее степенью (в том числе и нулевой) оставляет маршрут маршрутом. Это оправдывает употребление в тер мине слова "вставка".

Указанный класс маршрутов напоминает о регулярных языках, чем и объясня -ется приставка "R".

Нейтральный цикл есть частный случай Rвставки.


Пусть тройка (Ti,T2,T3) такова, что TiT2T3 - маршрут, Ti и T3 - циклы, \i{Tx) = TnTi2Ti3, ц(Т2) = TnT33, р(Тз) = T3iT32T33, T2 и T32 не пусты, ц(Т12Тз2) = Л, p.(Ti3Tii) = ii,(T33T3i) = Л. Тогда будем говорить, что данная тройка указывает повторяемые (точнее, согласованно повторяемые) циклы Ti и T3. Маршрут TiT2T3 назовем S-вставкой.

Заметим, что Tf T2T3k, k > 0, является маршрутом с зарядом TiiT33. Парные циклы - частный случай повторяемых циклов.

Понятие Sвставки вызывает ассоциации с понятием самовставляющегося символа грамматики, отсюда приставка "S".

Пример 9. Dc})

-0-0 о-

с Dмножеством

{(1, 2), (3, 2)}

определяет Рвставку 23, которая удовлетворяет определению элементарной схемы (см. ниже). Элементарной схемой является и предложение 1232. Пример 10. DcC

-0-0-о 0 0 0

с D множеством

{(1,10), (2, 3), (4, 8), (5, 3), (6, 7), (9, 7)}

определяет S вставку

T = 34536789,

которая является участком элементарной схемы предложения

(1, 2,T, 7,10).

Здесь повторяемы ненейтральные циклы 345 и 789.

Примеры показывают, что сформулированные в настоящей работе определе -ния Р и S вставок позволяют обнаружить явления итерации и согласованной итерации подцепочек в цепочках заданного Dграфом языка, минимально "прокручиваясь" по сильно связным компонентам.

Маршрут, который является Р вставкой или S вставкой, будем называть вставкой.

Формант - это вставка, любой собственный участок которой не является встав -кой.

Схема - маршрут, все вставки которого являются формантами.

Собственный участок вставки T, входящей в некоторую схему, не может сам быть вставкой: иначе T не была бы формантом. Однако различные вставки одной схемы могут иметь общий участок.


Пусть в схеме T любые две вставки имеют непустой общий участок. Тогда назовем T элементарной схемой.

Итак, понятие элементарной схемы расширено по сравнению с [Вылиток 98] не только за счет более емкого понятия вставки, но и за счет разрешения нескольких определенным образом "пересекающихся"вставок.

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

T1T2T3T4T5T6T7,

где Tj - нейтральный маршрут для 1 < i < 7, начальные вершины маршрутов T1, T2, T3 и T4 попарно различны, T1T2T3T4, T2T3T4T5, T3T4T5T и T4T5T3T7 являются Rвставками.

Лемма 21. Пусть T - нейтральный участок элементарной схемы. Тогда справедливы неравенства

width(T) < mm(\V + 1,

depth(T) < mm(\V2, P + 1).

Доказательство. Первое из неравенств доказывается аналогично лемме 2 из [Вылиток 98], а второе - аналогично лемме 3, оттуда же □

Лемма 22. Пусть T - нейтральный участок элементарной схемы T, m = V,

pn gmjn(m+1,p),mjn(m2,p+1). Тогда

T < n, \T < n((T) + 1).

Доказательство. Доказательство первого неравенства аналогично доказатель ству леммы 4 из [Вылиток 98]. Второе неравенство следует из представления элементарной схемы T последовательностью

Ton1T1...nKT )TKT )>

где p(T) = п1...пм(т), Tj - нейтральный участок для 0 < i < p(T) □ Из леммы 22 следует

Теорема 9. Множество элементарных схем, имеющих одни и те же заряд и пару концов, конечно □

3.2.3.2. Отношение развития маршрутов. Развитие (по другому можно сказать "разрастание") сводится к последовательности замен так называемых атомов формантами. Как видно из следующих определений, атом всегда присутствует во вставке, в частности, в форманте, и может встречаться в маршрутах, которые не содержат вставок.

Пусть T - это Rвставка. Тогда назовем R-атомом (вставки T) пустой маршрут с вершиной beg(T).

Пусть тройка (T1, T2, T3) указывает согласованно повторяемые циклы T1 и T3. Тогда назовем T2 S - атомом (вставки T1T2T3).

Маршрут, который является R атомом или S атомом, будем называть атомом.



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49]