Ребро - дерево
Cтраница 4
 |
Граф, его остовное дерево и фундаментальное множество. [46] |
При порождении фундаментального множества циклов удобно использовать метод поиска в глубину; он строит остовное дерево и каждое обратное ребро порождает цикл относительно этого дерева. Для того чтобы следить за ребрами дерева, используется поиск в глубину со стеком, в котором хранятся все текущие вершины пройденного пути в данный момент. Когда попадаем на обратное ребро, обнаруженный цикл будет состоять из этого ребра и ребер, соединяющих вершины из верха стека. [47]
Поиск в глубину является естественным подходом, используемым при порождении фундаментального множества циклов; он строит остовное дерево ( DFS-дерево), и каждое обратное ребро порождает цикл относительно этого дерева. Для того чтобы следить за ребрами дерева, мы применяем поиск в глубину со стеком, в котором хранятся все вершины из пути, идущего от корня к вершине, которая проходится в данный момент. Когда попадаем на обратное ребро, сформированный цикл будет состоять из этого ребра и ребер, соединяющих вершины из верха стека. [48]
Каждая вершина дерева соединяется с корнем единственным путем, число ребер в котором называется высотой этой вершины. Мы будем предполагать, что все ребра дерева ориентированы в направлении от корня, и назовем степенью вершины число выходящих из нее ребер. [49]
 |
Продублировав все ребра ЕМ. ОД, получаем граф с эйлеровым циклом. [50] |
Пусть Т обозначает евклидово минимальное остовное дерево заданного множества точек S, а Ф - оптимальный маршрут коммивояжера. Начнем с того, что заменим каждое ребро дерева Т парой ребер. Граф W является связным эйлеровым графом. [51]
Выходим теперь из z и начинаем путь по следующему ребру, исходящему из г. Каждый раз, когда мы проходим ребро дерева, мы продолжаем построение пути; когда мы проходим обратное ребро, оно становится последним ребром текущего пути. Таким образом, каждый путь состоит из последовательности ребер дерева ( их число 0), за которыми следует одно обратное ребро. Новый путь начинается из начальной вершины последнего обратного ребра; если в этой вершине неисследованных ребер больше нет, возвращаемся к предыдущей вершине на последнем пути. Процесс продолжается до тех пор, пока в графе G не исчерпаются непройденные ребра. Алгоритм 8.14 осуществляет это разложение орграфа на пути и цикл. [52]
 |
Граф и его клики. [53] |
При алгоритмическом подходе к выделению клик в графе применяют метод поиска с возвращением по специальному дереву поиска, устроенному следующим образом. Каждый узел в дереве поиска соответствует полному подграфу исходного графа, и каждое ребро дерева поиска соответствует вершине исходного дерева. Вершины ( множества) дерева поиска определим рекурсивно. [54]
 |
Иллюстрация к получению нижней оценки сложности решения задачи ТРИАНГУЛЯЦИЯ. [55] |
В получившемся ЕМОД вершины, соответствующие числам я - и Xj, соединены ребром тогда и только тогда, когда xi и х - образуют пару последовательных чисел в упорядоченном множестве. Решением задачи ЕМОД является список, содержащий N - 1 пар ( i, /), каждая из которых определяет ребро дерева. Читателю предоставляется сделать это в качестве простого упражнения. [56]
Другое важное свойство этого растущего дерева А заключается в том, что ни одно ребро из множества E ( D) - Е ( А) не может, выходя из какой-то вершины дерева А, заходить при этом в какую-нибудь вершину, являющуюся ее потомком. В случае неориентированных графов ( с точки зрения процедуры поиска их можно рассматривать как ориентированные графы, у которых каждое ребро имеет противоположно ориентированное), дерево поиска в ширину обладает следующим свойством: каждое ребро неориентированного графа G, не являющееся ребром дерева А, соединяет две вершины, принадлежащие разным ветвям дерева А. [57]
 |
Примеры деревьев упорядочения массива из 14 элементов. [58] |
Для первого оператора сумма весов выходящих ребер равна весу входящего ребра, а для второго оператора она на единицу меньше. Для примера на рис. 5.8 показаны деревья некоторых процессов упорядочения исходного массива из 14 элементов первым ( 5.8, а) и вторым ( 5.8 6) операторами. Все конечные ребра дерева должны иметь вес, равный единице или нулю. [59]
На рис. 8.10 показан поиск в глубину на орграфе и получающееся в результате разбиение ребер на четыре подмножества. Предполагается, что орграф представлен структурой смежности, показанной на рисунке и поиск в прямом порядке начинается из произвольно выбранной вершины а. Жирные линии означают ребра дерева, тонкими линиями обозначены обратные ребра, перечеркнутыми - поперечные ребра и пунктирными линиями - ребра, направленные вперед. [60]
Страницы: 1 2 3 4 5