Cтраница 3
Так как каждая такая функция / представляет орграф, скажем, с q ориентированными ребрами и г симметричными парами дуг, то / можно также трактовать как смешанный граф с q ориентированными и г неориентированными ребрами. Очевидно, что любые две функции из множества Yxl2 принадлежат одной и той же орбите степенной группы тогда и только тогда, когда соответствующие им смешанные графы изоморфны. [31]
Кроме того, в графе G ( A) нет неориентированных ребер, соединяющих вершины из одного множества Ji или У2, и в то же время любое ориентированное ребро соединяет вершины из одного множества, иначе бы обнаружился цикл с нечетным числом неориентированных ребер. [32]
ИПМ; г2 / - локальная степень смешанного ИПМ; r j - определяет число дуг, которые выходят из / - ой вершины, появляющихся в процессе ориентации ребер смешанного ИПМ на каждом шаге алгоритма; r j ( г3 / - - г4 /) - характеризует число неориентированных ребер, которые инцидентны / - ой вершине, появляющихся в процессе ориентации ребер смешанного ИПМ на каждом шаге алгоритма; г3 / - степень вершин смешанного ИПМ. [33]
Обобщением введенного понятия является конструкция древесного произведения. Пусть каждому неориентированному ребру е е Т между Ga и Gp соответствует общая подгруппа Ае Ga, Gp ( или пара отождествленных изоморфных подгрупп АО, : Лр, АО. [34]
Каждая пара (, Xj) называется ребром графа, а все семейство пар образует граф Т ( Х) на множестве X. Если порядок в парах несуществен, то такая пара образует неориентированное ребро; если же порядок в паре определен, то такая пара называется ориентированным ребром или дугой. [35]
Пусть S - произвольная частично ориентированная сеть, каждому ребру и которой приписано неотрицательное число с ( и) - пропускная способность. Потоком в сети S называется пара ( /, со), где со - некоторая ориентация всех неориентированных ребер сети, а / ( и) - заданная на множестве всех ребер функция с неотрицательными значениями, не превосходящими пропускных способностей, и такая, что в каждой внутренней вершине а выполняется закон Кирхгофа, согласно которому сумма значений потока по ребрам, входящим в вершину, равна сумме значений потока по ребрам, исходящим из вершины. [36]
Установить направленность связей, их причинный характер можно только лишь на основе содержательного анализа изучаемых связей, в ходе которого формулируются гипотезы о структуре влияний и корреляции. Как уже отмечалось, систему причинных гипотез удобно изображать в виде графа связей, вершинами которого являются переменные - причины или следствия; дуги ( ориентированные ребра) соответствуют постулируемым причинным отношениям, а неориентированные ребра - отношениям координированного изменения, не структурируемым в данной схеме. [37]
Если две вершины графа соединить более чем одним ребром, то каждое такое ребро называется кратным. Ребро называется ориентированным, если показано стрелкой направление связи вершин. На неориентированном ребре отсутствует стрелка направления связи. [38]
Граф, в котором указаны направления всех его ребер, называется ориентированным. В неориентированном графе отсутствуют направления ребер. В смешанном графе имеются как ориентированные, так и неориентированные ребра. [39]
В этом разделе мы рассмотрим алгоритмы, отвечающие на вопрос о расстоянии между узлами в простом орграфе с неотрицательными весами. К таким орграфам сводятся многие типы графов; так, если данный орграф не является простым, его можно сделать таковым, отбрасывая все петли и заменяя каждое множество параллельных ребер кратчайшим ребром ( ребром с наименьшим весом) из этого множества. Если граф неориентирован, то можно просто рассматривать граф, который получается из данного заменой каждого неориентированного ребра ( i, /) парой ориентированных ребер ( i, /) и ( /, i) с весом, равным весу исходного неориентированного ребра. Если граф невзвешен, можно считать, что все ребра имеют один и тот же вес. Позднее мы будем рассматривать и отрицательные веса. [40]
Рассматриваемый алгоритм определяет расстояния между вершинами в простом орграфе с неотрицательными весами. К таким орграфам сводятся многие типы графов. Если граф не является простым, его можно сделать таковым, отбрасывая все петли и заменяя каждое множество параллельных ребер кратчайшим ребром ( ребром с наименьшим весом) из этого множества; каждое неориентированное ребро заменяется парой ориентированных ребер. Если граф не взвешен, то можно считать, что все ребра имеют один вес. [41]
В этом разделе мы рассмотрим алгоритмы, отвечающие на вопрос о расстоянии между узлами в простом орграфе с неотрицательными весами. К таким орграфам сводятся многие типы графов; так, если данный орграф не является простым, его можно сделать таковым, отбрасывая все петли и заменяя каждое множество параллельных ребер кратчайшим ребром ( ребром с наименьшим весом) из этого множества. Если граф неориентирован, то можно просто рассматривать граф, который получается из данного заменой каждого неориентированного ребра ( i, /) парой ориентированных ребер ( i, /) и ( /, i) с весом, равным весу исходного неориентированного ребра. Если граф невзвешен, можно считать, что все ребра имеют один и тот же вес. Позднее мы будем рассматривать и отрицательные веса. [42]
Пусть А - конечное множество, элементы которого называются вершинами. В соответствии с тем, является ли U семейством ориентированных или неориентированных ребер, граф G ( 4, U) называется ориентированным или неориентированным. U i, щ имеют общую вершину и каждое ребро встречается в этой последовательности не более одного раза. [43]
По признаку направленности связей между поверхностями восстанавливаемой детали имеются два вида отношений. Подмножество отношений первого вида содержит поверхности, строго от которых проводят измерения. Такие отношения на графе поверхностей детали изображаются ориентированными дугами, выходящими из измерительных баз. Эти отношения включают например, параметр биение поверхности. Подмножество второго вида изображается неориентированными ребрами. В паре поверхностей, связанных ребром, любая поверхность может быть выбрана в качестве измерительной базы. [44]
Граф в общем случае состоит из вершин ( узлов) - условных изображений составляющих его элементов и ребер - линий, соединяющих все или некоторые эти вершины. Вершины, соединенные данным ребром, называют смежными. В нем каждому ребру может быть приписан определенный физический смысл. Возможно сочетание в графе ориентированных и неориентированных ребер. [45]