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