1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (Котов, Сабельфельд 1991 - Теория схем программ), страница 7

2Л граф Г, содержит 4 вершины и 8 дуг. Дуга е, — входная, дуга е — выходная, дуга е, — висячая, остальные дуги — внутренние; окр (е4) = (е„е„ее, ею ем ее), окр (ее) = (е,); вершины ие и из — наследники вершины о1. Рве. 2Л. Граф Гел Путем в графе Г называется всякая последовательность ...гаер,ы... такая, что для всех ( Ф (ег) = (кп и. 1).

Путь по еершинам содержит только вхождения вершин, путь по дуеам— только вхождения дуг. маршрутом в графе Г называется всякая конечная непустая последовательность дуг е,... е„такая, что для всех ( (1 ~ ( с и) дуги е; и еяа смежны. Прн этом говорят, что е, — начало, а е„— волен маршрута, и — его длина, и что он ведет от е, к е„. Через марш (е', е) обозначим множество всех маршрутов графа, которые ведут от е' к е. Заметим, что марш(е', е) — либо пустое, либо бесконечное множество. Пример: последовательность дуг е,е,е еееее является маршрутом графа Гьм ведущим от ее к е,.

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

Болев подробно с основными понятиями теория графов можно познакомиться, например, по иниге Харари [75). (.2. Связность н изоморфиэм графов, деревьв. Подера$ам графа (У, К, Ф), порожденным некоторым подмножеством вершин У' (:; е', называется граф (У', Е', Ф'], удовлетворяющий следующим условиям: Е' ~ Е и содержит все дуги из Е, инцидвнтные вершинам для е ~ Е' Ф' (е) получается заменой на е тех элементов Ф (е), которые не принадлежат Р"; Е' не содержит висячих дуг. а рис. 2.2 изображен подграф графа Г, „порожденный мноом вершин (ип и, иа). а графа Г = (У, Е, Ф) и Г' = (У', Е', Ф') называются рфкмми, если между их вершинами, а также между их думожно установить вааимно однозначоотзетствие 1: У-» Г, 1х.

Е-»Е', аняющее отношение инцидентности, т. е. Е Уи1 иаЕ г =(и, )+о Ф'(1л (е))=(1. (и.), ю)) й ,(Ф (е) = (ы, и,) <=> Ф' (1э (е)) = (со, 1„(и,))) Ь (Ф (е) = (ю, в) ++ Ф' (1з (е)) = (е, е)) А (Ф(е) = (и„иа) воФ' (1л (е)) = (1 (и,), 1, (иа))).

иа Дзе вершины ип иа графа Г называются (резеаилмми, если и, = иа или существует марш'ут еп..., е„графа Г такой, что дуга еа Рис. 2.2. полграф цидентна вершине и, а дуга е„— вер- графа Га.и порож лезвий вершинами 3. Отношение сея ааиности вершин графа лексивно, симметрично и траизитивно, ". в. представляет собой отношение эквивалентности на множе- е вершин графа. Это означает, что множество У вершин афа Г разбивается на классы Рп..., га попарно связанных .ршин. Подграфы Г; = (Уо Е;, Фа), порожденные множествами о не имеют друг с другом общих вершин и дуг и нааываются ояектами солености графа Г. Компонентами связности гра- Г будем называть также каждый из графов (Я, (е), Ф), (е) = (ы, ю), где е — висячая дуга графа Г.

Граф называется селевым, если он содержит не более одной мпонеиты связности. Связный граф Г беа контуров называется деревом, если: (1) в Г имеется ровно одна вершина, называемая коркам де,ва, к которой не ведет ни одна иэ внутренних дуг графа Г;: (2) к каждой из остальных вершин ведет ровно одна внутрен' я дуга графа Г; (3) все входные дуги графа Г ведут к корню. Вершины, иэ которых не выходит ии одна иэ внутренних дуг рева, называются листьями этого дерева.

.су: $2. Метед раэметкв и задача глобальвМо авалваа 2Л. Неформалъное введение. Под разя«ииой мы понимаем отображение, сон оставляющее пометки вершинам илв дугам графа. Метод разметки используется для построения алгоритмов распознавания рааличных свойств размеченных графов. Понятие пометки формализует при этом интересующее нас свойство графа или его частей. В качестве анализируемого размеченного графа будет выступать обычно схема программы. Метод разметки использует тот факт, что свойства вершины графа определяются свойствами некоторых «соседей» этой вершины.

Для иллюстрации основной идеи алгоритмов разметан опипюм алгоритм такого типа для решения одной очень простой задачи: определения достижимости вершин ориентированного графа от некоторой выделепной его вершины, называемой начальной. Вершина о достялшма от начальной, если существует путь, ведущий от начальной вершины к вершине и. Множеством пометок здесь будет служить множество, составленное из двух значений, которые мы назовем «дости»кима» в «я«и«э«стао» соответственно. Начальная разметка сопоставляет пометку «достижима» началъной вершине графа и «неи«««с»лло» всем остальным аершякам.

Дальнейший процесс построения необходимой разметки будет состоять в повторном применении правила разметки: если некоторая вершина помечена пометкой «досжпжила», то пометить пометкой «достижима» все наследники этой вершвны. Процесс завершается, когда будет достигнута ста~»иоларлзл ра»- метка, т. е. такая, которая ие изменяется никаким применением правила рааметки. Отметим две особенности процесса разметки. Во-первых, сразу же возникает вопрос о том, существует лк хотя бы одна стационарная разметка. Иначе говоря, может' ли завершиться процесс разметкиу Другой вопрос связав с единственностью стационарной разметки.

Дело в том, что процесс разметки описан как педетермивированкый в том смысле, что на каждом его шаге имеется возможность выбирать, к какой из вершин применять правило разметки. Верно ли, что результирующая стационарная разметка (если она существует) не аависит от того, в каком порядке и к какам вершинам будет применятъся правило разметкиг Для нашей простой задачи положительный ответ на оба вопроса довольно очевиден. Кроме того, легко доказать, что вершина достижима от начзлъиой тогда и толъко тогда, когда она имеет пометку «ооаиил«ика» при стационарной разметке. На рис. 2.3 описанный процесс применяется к графу с патио вершинами.

На этом рисунке пометка «достиэ«ика» изображена символом «»». а пометка «к«из««сиию» — отсутствием какого бы то ни было символа. В дальнейшем нас будут интересовать преимущественно 26 такие процессы разметки, когда ответ на оба сформулирозанны>с выше вопроса поло>кителен, т. е. когда стационарная разметка существует и еднястзенна. Такие процессы будут называться алгоритмами разметки. При этом условие существования стационарной разметки достигается благодаря тому, что процесс рааметкн определяется как некоторый монотонно сходящийся процесс.

Именно, на множестве пометок вводится частичный порядок„ соответствующий умекынению «неопределепнрстиэ содержащейся в них информации, а процесс разметки организуется таким образом, что пометки одной и той же вершины в ходе этого процесса Рве. 2.3. Иллюстрация процесса раэмсткп могут только умень>иаться. Тогда для существования стационарной разметки достаточно потребовать, чтобы все строго убывающие цепи в множестве пометок были конечными. В нашем примере можно определить «веплсссп>во»» «до«жил«ил«аэ и заметить, что правило рааметки может только уменьшать неопределенность отметок вершин, но не увеличивать ее.

Кроме того, можно отказаться от некоторых «холостыхэ применений правила разметки, когда они не меняют ни одной из пометок верн>иннаследвнков, как, например, применение правнла разметки к вершние с номером $ прн разметке на рис. 2.3, 6. Для этой цели вводится понятие множества активных верши» таким ебразом, что на каждом шаге процесса разметки выбор вершины, к которой применяется правило разметка, делается нэ этого множества (применение правила разметки к каждой нэ остальных, пассивных вершин ничего не изменило бы).

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

Начальная вершина: «досжажимаэ. Остальные вершины: «ясиэс«слпцм. Множество активных вершин: начальная вершина. Правило разметки. Взять любую нз активных вершин (с удалением ее иэ множества активных). Пометить пометкой «доспшзгима» все наследники этой вершины. Если при этом пометка некоторой вершины меняется (с «неиггестно» иа «достижима»), то добавить эту вершину к множеству активных. В новой формулировке условие достижения стационарной разметки заменяется условием пустоты множества активных вершин. 2.2. Формальная постановка задачи глобального анализа. ХХояурешеткой называют множество Х с заданной на нем бинарной операцией пересечения /~, которая обладает следующими свойствами: тх,у,г~Х х/~х=х идемпотентность хну= уДх коммутатявность а' /~ (у /~, 3) = (х /~ у) /~ г ассоциативность. Частичный порядок на элементах полурешетки вводят, полагая по определению х < у Ф»х Д у = х, х( у <=> х/~ у = хо«х~~ у.