Метка - вершина
Cтраница 2
После построения Tb ( Xi U Х2) определим новые метки вершины v и всех ее предшественников, а также метки вновь построенных вершин. [16]
Для иллюстрации найдем расстояние от вершины b до вершины g в орграфе на рис. 8.12. Мы используем массив dist для хранения меток вершин в процессе решения. Окончательные метки обведены квадратиками, а жирными квадратиками выделены самые первые приписывания окончательных меток. [17]
Программная реализация алгоритма 6.1 представлена алгоритмом 6.2. Реализация близко соответствует основному алгоритму 6.1. Программа представлена тремя процедурами Init, Depth, Way-Depth, где WayDepth - основная программа поиска в глубину; Depth - рекурсивная процедура поиска, один к одному соответствующая аналогичной процедуре в алгоритме 6.1; Init - процедура контроля исходных данных и изменения меток вершин. Изменение нумерации меток вершин является существенным для алгоритма. Данная нумерация позволяет обращаться к элементам массивов, содержащих информацию о вершинах, по номерам соответствующих вершин. Такой прием позволяет очень близко подойти в программной реализацией структуры смежности Adj [ x ] к ее множественному описанию. [18]
Zn - метки вершин графа, занумерованные в той последовательности, в которой они появляются в конструкции Я, причем X Z0, Х Zn. Мы утверждаем, что после конца i - й итерации цикла while будет Zt с: Y. Предположим, что при переходе от Z - к Zi 1 применялась F-зависимость F - - W. [19]
Zn - метки вершин графа, занумерованные в той последовательности, в которой они появляются в конструкции Я, причем X Z0, X Zn. Мы утверждаем, что после конца t - й итерации цикла while будет Zt cr Y. Предположим, что при переходе от Z - к Z - 1 применялась F-зависимость V - W. [20]
Программная реализация алгоритма 6.1 представлена алгоритмом 6.2. Реализация близко соответствует основному алгоритму 6.1. Программа представлена тремя процедурами Init, Depth, Way-Depth, где WayDepth - основная программа поиска в глубину; Depth - рекурсивная процедура поиска, один к одному соответствующая аналогичной процедуре в алгоритме 6.1; Init - процедура контроля исходных данных и изменения меток вершин. Изменение нумерации меток вершин является существенным для алгоритма. Данная нумерация позволяет обращаться к элементам массивов, содержащих информацию о вершинах, по номерам соответствующих вершин. Такой прием позволяет очень близко подойти в программной реализацией структуры смежности Adj [ x ] к ее множественному описанию. [21]
Из предложения 13.7 следует, что если вершина v является предком вершины w в дереве декомпозиции G, то INT ( w) не может быть собственным подмножеством в IN Т ( v), так как в противном случае декомпозиция, ассоциированная в v, не была бы плотной. Кроме того, метки вершин, лежащих на любом пути, ведущем от корня к некоторому листу, должны образовывать невозрастающую последовательность. Если х и у - вершины G с метками R и 5, причем ни одна из этих вершин не является предком другой, то R S. Действительно, пусть z - общий предок для х я у. [22]
Из предложения 13.7 следует, что если вершина v является предком вершины w в дереве декомпозиции G, то INT ( w) не может быть собственным подмножеством в INT ( v), так как в противном случае декомпозиция, ассоциированная в v, не была бы плотной. Кроме того, метки вершин, лежащих на любом пути, ведущем от корня к некоторому листу, должны образовывать невозрастающую последовательность. Если х и у - вершины G с метками R и S, причем ни одна из этих вершин не является предком другой, то R В S. Действительно, пусть z - общий предок для х и у. [23]
Реализация жадной схемы формирования остовного дерева представлена в алгоритме 6.7. Используемые при его описании обозначения соответствуют тому, что вводилось при обосновании жадной схемы. Вектор Mark [ x ] меток вершин х е X графа поддерживает их принадлежность компонентам связности Uh из которых формируется реберный список остовного дерева. Начальные величины Mark [ Xj ] устанавливаются равными порядковым номерам соответствующих вершин jc / e X. Далее значения Mark [ Xj ] корректируются по мере слияния компонент Uh сохраняя соответствие принадлежности им вершин. [24]
 |
Простой взвешенный орграф. [25] |
Реализация рассмотренной схемы поиска кратчайшего пути представлена в алгоритме 6.11, где граф Г ( X, U, Ф) представляется матрицей весов We [ w - ], веса несуществующих ребер полагаются равными оо. Вектор Mark [ x ] меток вершин устанавливает принадлежность вершины х е постоянной ( TRUE) или временной ( FALSE) метке. Вектор Dist [ x ] в алгоритме фиксирует текущие значения меток вершин. Вектор Prev [ x ] позволяет восстановить в обратной последовательности вершины кратчайшего пути. [26]
Очевидно, для задания ( или построения) сбалансированного 2 - 3-дерева достаточно заполнить первую и вторую строки таблицы. Пятая строка имеет вспомогательный характер и используется при расстановке меток вершин, а также при реализации некоторых процедур над 2 - 3-деревьями. [27]
Пусть Н есть DDA-граф с базой С для R - U. Сходство состоит в том, что если Y есть множество меток вершин на некотором шаге построения Н, то строка, соответствующая w в некотором табло порождающей последовательности для Т к, имеет выделенные переменные во всех столбцах, входящих в Y. [28]
Для того чтобы дерево поиска стало возможно более узким вверху ( разд. С этого момента будем рассматривать только такое перенумерованное представление Gx, отбросив исходные метки вершин. Перемеченные вершины имеют полезное дополнительное свойство, состоящее в том, что вершина, для которой в данный момент ищется соответствующая, обычно смежна с вершинами, для которых соответствующие найдены раньше; этот факт ограничивает возможное число соответствий, сокращая тем самым поиск. [29]
Существует также правило перегруппировки, согласно которому мы можем применять некоторые перестановки к меткам вершин. Две нумерации графа В считаются эквивалентными, если автоморфизм графа В превращает одну нумерацию в другую. В более общем случае мы, возможно, захотим рассмотреть эквивалентность для соответствующей подгруппы aut В. Для данного правила перегруппировки реакционный граф В - это граф Г, вершины которого соответствуют различным неэквивалентным нумерациям графа В и в котором имеется направленное ребро, связывающее вершину а с вершиной 8, если и только если вершина / 3 может быть получена из а при применении правила перегруппировки только один раз. Поскольку мы имеем п различных меток, легко рассчитать число вершин графа Г: оно равно я. В, где Х обозначает число элементов в множестве X. [30]
Страницы: 1 2 3