Ориентированная графа

Cтраница 2

Теорема применима также к ориентированным графам. Если о - минимальное число разделяющих вершин для ориентированных цепей от А к В, то существует о непересекающихся ориентированных цепей между этими множествами. [16]

Деревья Нг мы рассматриваем как ориентированные графы. [17]

В дальнейшем в основном рассматриваются ориентированные графы, не содержащие контуров. [18]

Наряду с обычными часто рассматривают ориентированные графы. Vi, Vj), в которых места элементов твердо закреплены. [19]

Подача газа потребителям по тупиковым н кольцевым сетям. [20]

Примеры газовых сетей, представляющих собой конечные связные ориентированные графы, показаны на рис. 6.8. Графы, у которых ребра пересекаются только в узлах, называются плоскими. [21]

В этой главе мы будем рассматривать ориентированные графы GV, Ey, дугам которых приписаны веса. Это означает, что каждой дуге, и е Е поставлено в соответствие некоторое вещественное число a ( u v), называемое весом данной дуги. [22]

Это соответствие между двудольными графами и ориентированными графами позволяет перенести результаты, полученные выше для двудольных графов, на ориентированные графы. [23]

Введем общее понятие потока сигналов в ориентированных графах или сетях, которые имеют источники [ 6 - ( и) 0 ], стоки [ 6 ( и) 0 ] и, возможно, контуры и петли. Наличие контуров и петель соответствует понятиям обратных связей в сетях. Величина х, называется весом Vj. Задача анализа сетей состоит в том, чтобы найти выражения для полного потока сигналов от источника к стоку ( который часто называется коэффициентом усиления в стоке) через значения сигналов и коэффициенты усиления дуг. Связь между сигналами в различных вершинах может быть представлена в общей функциональной форме или в специальной форме линейных отношений. [24]

Для представления важных NP-полных задач об ориентированных графах нам понадобятся следующие определения. [25]

Этот алгоритм легко может быть распространен на ориентированные графы ( см. также задачи 7 и 8) и состоит в следующем. Алгоритм нахождения эйлерова цикла. Начинать с некоторой вершины р и каждый раз вычеркивать пройденное ребро. [26]

Зададимся теперь следующим вопросом: какие графы и ориентированные графы являются консервативными. Интересно ( хотя не так уж и удивительно), что ранее примененные методы дают хорошую ха-рактеризацию этих графов для неориентированного случая. [27]

Нумерация вершин графа ( в скобках, соответствующая очередности, в которой они просматриваются в процессе поиска в глубину. [28]

Методика поиска в глубину очевидным образом переносится на ориентированные графы. [29]

По определениям, принятым в этих монографиях, ориентированные графы могут содержать и петли, и параллельные ребра. Рассматриваемые далее ориентированные графы могут содержать параллельные ребра, но петель не содержат. [30]

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