Cтраница 4
Для ориентированного графа G можно построить ориентированный граф G, вершинами которого являются листовые множества G. Два листовых множества L и L2 соединяются ориентированным ребром ( L (, L2) в G есдп имеются ориентированные ребра от L к L % в G, Этот граф называется листовой композицией графа G. G является ациклическим графом, так как любой ориентированный цикл в нем дал бы ориентированный цикл в G, проходящий через несколько листов. [46]
В виде задачи (8.52), (8.53) представляются известные задачи о кратчайшем связывающем дереве в неориентированном и ориентированном графах. Трудоемкость этих алгоритмов не превышает О ( га3) - число вершин графа. Задача формулируется следующим образом: задан взвешенный ациклический граф. Его разрезом, порожденным подмножеством вершин V, называется подмножество дуг, исходящих из V, но не входящих в V. Требуется найти максимальное множество попарно непересекающихся по дугам разрезов. [47]
Как правило, фреймы организованы в виде ослабленной иерархии ( или гетерархии), в которой фреймы, расположенные ниже в сети, могут наследовать значения слотов разных фреймов, расположенных выше. Гетерархия - это запутанная иерархия, т.е. ациклический граф, в котором узлы могут иметь более одного предшественника. [48]
Если, например, путь Р состоит из пяти ребер с общим весом 24, а путь Р - из трех ребер с общим весом 36, то путь Р считается более коротким. Граф или орграф называется связным, если всякую пару узлов можно соединить по крайней мере одним путем. Цикл - это путь, который начинается и кончается в одной и той же вершине. В ациклическом графе или орграфе циклы отсутствуют. Связный ациклический граф называется ( неукорененным) деревом. Структура неукорененного дерева такая же, что и у дерева, только в нем не выделен корень. Однако каждая вершина неукорененного дерева может служить его корнем. [49]
Для ориентированного графа G можно построить ориентированный граф G, вершинами которого являются листовые множества G. Два листовых множества LI и Z-2 соединяются ориентированным ребром ( L4, L2) в G, если имеются ориентированные ребра от Lt к L, в G. Этот граф называется листовой композицией графа G. G является ациклическим графом, так как любой ориентированный цикл в нем дал бы ориентированный цикл в G, проходящий через несколько листов. [50]
В обоих случаях структура изображения представлена в виде графа, причем так, что его вершины обозначают сегменты или элементы сегмента, а ребра представляют взаимосвязи между ними. Взаимосвязь может быть типа предок - потомок ( как в дереве), или она может выражать связанность эквивалентных объектов. В обоих случаях эти отношения не рефлексивны. Изображение на рис. 3.3, а можно представить в виде дерева, а изображение на рис. 3.3 6 имеет структуру, которая является более общим ациклическим графом. [51]