Ориентированный граф

Cтраница 1

Ориентированный граф бисвязен ( взаимно связен, сильно связен), если все его вершины взаимно связаны. [1]

Мультиграф и псевдограф.| Орграфы с тремя вершинами и тремя дугами. [2]

Ориентированный граф, или орграф, D состоит из конечного непустого множества V вершин и заданного набора X упорядоченных пар различных вершин. Элементы из X называются ориентированными ребрами, или дугами. [3]

Ориентированный граф ( орграф) называется ордеревом, если граф, получаемый при игнорировании ориентации дуг, является деревом. [4]

Ориентированный граф называется обыкновенным, если он не имеет строго параллельных дуг и петель. Заметим, что если обыкновенный ориентированный граф имеет параллельные, но противоположно ориентированные дуги, то соответствующий неориентированный граф уже не будет обыкновенным графом в неориентированном смысле, так: -; у он содержит параллельные ребра. [5]

Ориентированный граф называют слабо связным или слабым, если для любых двух различных вершин графа существует по крайней мере один маршрут, соединяющий их. [6]

Ориентированный граф называется сильно связным, если для каждой пары различных вершин v и ш существует путь из v в w и из ш в и. Очевидно, что сильная связность ориентированного графа означает связность соответствующего неориентированного графа. Обратное, вообще говоря, неверно. [7]

Обозначения операторов. [8]

Ориентированный граф, вершинами которого являются технологические звенья ( операторы, см. рис. 2.2), а дугами - технологические связи, носит название топологической структуры схемы производства или графа производства. [9]

Ориентированный граф, состоящий из нескольких деревьев, называется лесом. Если есть путь из v в w, то v называется предком узла w, a w - потомком узла о. Если v ф w, тою называется подлинным потомком узла и. Узел и его потомок образуют поддерево, и узел v называется корнем этого поддерева. [10]

Ориентированный граф, вершины которого соответствуют переменным и выражениям программы. Из вершины А ведет дуга в вершину В тогда и только тогда, когда А непосредственно используется при вычислении В. [11]

Вершина х доминирует над вершиной. [12]

Ориентированный граф на рис. 2.10 описывает отношение доминирования в частично упорядоченном множестве 5 ( 3); он напоминает рисунок куба. [13]

Ориентированный граф называют слабо связным или слабым, если для любых двух различных вершин графа существует по крайней мере один маршрут, соединяющий их. [14]

Ориентированный граф состоит из непустого множества V, множества А, не пересекающегося с V, и отображения D из А на VxV. Элементы множеств V и А называются соответственно узлами и ребрами, a D называется отоэраженигм направленной инцидентности, связанным с данным ориентированным графом. А и D ( a) ( v, v), то говорят, что v является начальным узлом ребра a, a v - его конечным узлом Для наших целей число узлов и ребер предполагается конечным. Упорядоченный граф обычно обозначается через ( V, A, D) или ( V, А), если D не используется явно. [15]

Страницы: 1 2 3 4