Cтраница 1
Ориентированный цикл в графе G - это цикл в графе G с ориентацией, определяемой порядком вершин в цикле. [1]
Если нет ориентированных циклов, то алгоритм 2.2.3 Т осуществляет топологическую сортировку графа G. Если же хотя бы один ориентированный цикл имеется, то ясно, что топологическая сортировка невозможна. Ясно, что при любой интерпретации упражнения ориентированные циклы длины 1 можно исключить из рассмотрения. [2]
Граф может иметь ориентированные циклы или быть ациклическим, если таковых нет. [3]
Очевидно, этот ориентированный цикл является одной из связных компонент графа. [4]
Если Z - ориентированный цикл функционального орграфа D, то через D - Z мы обозначаем орграф, который получается из D удалением всех дуг, принадлежащих циклу Z. Напомним, что дерево, входящее в вершину и, получается из корневого дерева с корнем и путем ориентирования каждого его ребра по направлению к вершине и. Теперь мы подготовлены к тому, чтобы охарактеризовать функциональные орграфы; доказательство нижеследующего утверждения можно найти у Харари, Нормана и Картрайта [ 1, стр. [5]
G не имеет ориентированных циклов. Для ориентированных графов ациклические графы играют роль, подобную роли деревьев для неориентированных графов. [6]
Следовательно, Р - искомый ориентированный цикл, проходящий каждую дугу G точно один раз в заданном на ней направлении. [7]
Предполагается, что для любого ориентированного цикла в сети соответствующая сумма ctj неотрицательна. Примем, что xtj есть величина потока по дуге ( i, j) в течение планового периода. [8]
Путь называется циклом ( ориентированным циклом), если в нем все вершины внутренние. [9]
В ориентированных графах можно искать ориентированные циклы, проходящие через каждую вершину по одному разу. [10]
С помощью алгоритма Терри постройте ориентированный цикл, проходящий через каждое ребро изображенного на рис. Д6 графа по одному разу в каждом из двух направлений. [11]
В ориентированных графах можно искать ориентированные циклы, проходящие через каждую вершину по одному разу. [12]
В полученной схеме Sp нет ориентированных циклов - следовательно это действительно схема из функциональных элементов. [13]
Поскольку, по условию, ориентированных циклов нет, то хотя бы одна свободная вершина должна быть. [14]
А В обозначен индекс пересечения ориентированных циклов Аи В. Поскольку оба цикла А и В двумерны, форма со является симметрической. [15]