Построенный граф
Cтраница 3
Изложенные принципы дают исчерпывающие пра. Построенному графу придается, по возможности, наглядная форма. В частности, когда можно выделить узел-источник и узел-сток, iBce смешанные узлы удобно располагать между источником и стоком. [31]
Для оптимального распределения базы данных по устройствам прямого доступа строится граф, каждой вершине которого взаимно однозначно соответствует файл и две вершины смежны, если оба соответствующих файла необходимы для ответа на запрос некоторого типа. Если построенный граф является Лраскрашиваемым, то файлы распределяются по дисковым устройствам в соответствии с раскраской приписанных им вершин. [32]
Любые две вершины, отличные от вершины а, соединяются в этом графе маршрутом, который является объединением двух простых цепей, соединяющих вершину а с этими двумя вершинами. Следовательно, построенный граф является связным, а число его ребер на единицу меньше числа его вершин. Отсюда вытекает ( см. [10]), что построенный граф является деревом. [33]
Описанный в данном разделе алгоритм вычисляет пропускные способности ребер дерева Т за п - 1 этапов. Каждый этап состоит в вычислении потока в графе, получаемом последовательно из ранее построенного графа с помощью конденсации, как об этом говорилось выше в разд. [34]
Описанный в данном разделе алгоритм вычисляет пропускные способности ребер дерева Т аа га - 1 этапов. Каждый этап состоит в вычислении потока в графе, получаемом последовательно из ранее построенного графа с помощью конденсации, как об этом говорилось выше в разд. [35]
 |
Преобразование вершин гиперсети в клики слабой инциденции. [36] |
На множестве Y ( x) строится полный граф. В построенном графе G ( S) между любой парой вершин z ( и г3 любому множеству непересекающихся цепей взаимно однозначно соответствует множество слабых внутренне независимых маршрутов между соответствующими вершинами в гиперсети S. Следовательно, по графу G ( S) за полиномиальное время можно вычислить слабую внутреннюю - соединимость пары вершин в гиперсети S. [37]
Любые две вершины, отличные от вершины а, соединяются в этом графе маршрутом, который является объединением двух простых цепей, соединяющих вершину а с этими двумя вершинами. Следовательно, построенный граф является связным, а число его ребер на единицу меньше числа его вершин. Отсюда вытекает ( см. [10]), что построенный граф является деревом. [38]
При этом сумма не изменится, но г - граф перестанет быть г - графом. Наконец, могут еще быть точки ij, из которых все еще исходит по две стрелки. Выбросим в этом случае старые стрелки; при этом сумма не увеличится, а построенный граф будет г - графом. [39]
Для доказательства того, что алгоритм 2.3 корректно строит стягивающее дерево произвольного связного графа, достаточно отметить следующие три факта. Таким образом алгоритм строит связный граф. Отсюда следует, что построенный граф F, Ту не содержит циклов. Действительно, последняя ветвь, замыкающая цикл, должна была бы соединить две уже рассмотренные вершины. И наконец, в-третьих, из свойства поиска в глубину следует, что процедура WGD просматривает все вершины связного графа. Следовательно, граф F, Г, построенный нашим алгоритмом, есть стягивающее дерево графа G. Вычислительная сложность алгоритма есть, очевидно, O ( n m), а:, е, того же порядка, что и поиск в глубину. [40]
Ясно, что из вершин а [ / ] и ю [ у ] только одна может быть нижней. Поэтому вторую из этих вершин мы будем называть верхней. Заметим, что нижней одна и та же вершина может быть и у нескольких ребер. Вершину, которая не является нижней ни у одного ребра, мы будем называть концевой вершиной построенного графа. [41]
Если известно словесное описание принципа функционирования и восстановления системы, то можно определить множество всех возможных состояний системы, причем, задав определенный критерий отказа, все состояния можно разделить на два класса: работоспособности и отказа. Если известны интенсивности отказов и восстановления отдельных элементов системы, то может быть построен граф переходов, у которого вершинами будут возможные состояния системы, а ребрами - возможные переходы с интенсивностями, определяемыми соответствующими характеристиками надежности и ремонтопригодности элементов. Например, если известно, что система находится в некотором состоянии Hi и для перехода ее в состояние Н ] необходимо, чтобы произошло определенное событие ( отказ какого-либо элемента или восстановление), то от состояния HI к состоянию Hj проводится стрелка, у которой указывается интенсивность реализации данного события. Заметим, что не все события ( переходы) могут оказаться разрешенными при построении подобных графов. Так, если, например, имеется всего одна ремонтная бригада ( полностью ограниченное восстановление) и восстановление производится в порядке поступления отказавших элементов, то в случае очереди отказавших элементов не может произойти прямой переход из данного состояния в состояние, где восстановленным окажется не тот элемент, который находится в процессе восстановления. На основании построенного графа переходов легко выписать необходимую систему уравнений, решение которой позволяет получить требуемый показатель надежности. [42]
Страницы: 1 2 3