Бесконтурный граф

Cтраница 1

Эквивалентные преобразования М - сети. [1]

Бесконтурный граф G превращается в сеть G при задании соответствующей порядковой функции. Положим, G содержит контуры. [2]

Действительно, в конечном бесконтурном графе всегда существует вершина а, в которую не заходит ни одна дуга. [3]

Можно сказать, что бесконтурный граф Н с помеченными ребрами является графом общего решения системы ( 1), если через каждую вершину графа проходит хотя бы один путь максимальной длины, а отображение а н Т ( а) является взаимно однозначным соответствием между множеством Р и множеством максимальных путей графа. [4]

Ясно, что G - бесконтурный граф. [5]

Дуги, обозначенные как прямые, образуют бесконтурный граф, и никакая дуга не может быть добавлена без образования контура. По теореме 14 и части 1 леммы разделение дуг на прямые и обратные единственно. [6]

По-прежнему будем считать, что модель программы - ориентированный бесконтурный граф, вершины которого соответствуют операциям обработки и обмена, а дуги - информационным связям и условным ветвлениям. Задание представляется в виде последовательности двух и более операций, работа - в виде последовательности операций и заданий. Каждая из операций характеризуется априори заданными длительностью rfj и стоимостью С - выполнения на ресурсе j - ro типа и соответствующими значениями т -, Cij, полученными в результате масштабирования. TV)) гДе xi - независимая переменная ( длительность TJ операции или стоимость Ci использования ею ресурса), j - назначение г-й операции. [7]

Согласно алгоритму 3.5 при описании алгоритма нахождения путей в бесконтурном графе мы можем предположить, что каждая дуга идет из вершины с меньшим номером в вершину с большим номером. [8]

Потребуем, чтобы числа wtj удовлетворяли следующему условию: существует ориентированный бесконтурный граф G ( N, U) такой, что из и. Нетрудно заметить, что в приведенном выше примере числа wtj такому условию удовлетворяют. [9]

АЛГОРИТМ 3.6. ( Нахождение расстояний от источника до всех вершин в бесконтурном графе. [10]

&) не более п ( п - 1) / 2 единиц ( G - бесконтурный граф), а в результате выполнения одного преобразования II в нее вводится по крайней мере одна новая единица. [11]

Первая задача хорошо известна в теории исследования операций. Эффективно она решается только для бесконтурных графов. Рассмотрим ее для бесконтурного взвешенного графа. С одной стороны, этот случай включает в себя и обыкновенные графы, с другой стороны, он более близок к требованиям практики. [12]

Приведенные в таблицах оценки сложности алгоритмов справедливы в предположении, что отношение строгого порядка, заданное на множестве требований ( если оно не пусто), представлено своим графом редукции. Отметим, что переход от произвольного бесконтурного графа к его транзитивному замыканию или к графу редукции требует выполнения не более 0 ( п3) операций [7], где п - число вершин графа. [13]

Ниже детально описан алгоритм 4.10, носящий имя Хопк-рофта - Карпа. В этом алгоритме вспомогательная бесконтурная сеть, а точнее вспомогательный бесконтурный граф, поскольку пропускные способности всех ребер равны единице, строится при помощи процедуры PGA. Далее проводится поиск в ширину в графе Нм, начиная от свободных вершин в X. Увеличение существующего паросочетания вдоль максимального множества кратчайших увеличивающих цепей с попарно различными множествами вершин реализуется процедурой ФАЗА. [14]

Очевидно, что задачу определения расстояния между всеми парами вершин можно решить, используя я раз ( поочередно для каждой вершины) один из описанных ранее методов нахождения расстояний от фиксированной вершины. Таким образом, мы получаем алгоритм со сложностью О ( я4) ( при использовании метода Форда - Беллмана) или О ( я3) для бесконтурных графов или неотрицательных весов. Однако оказывается, что в общем случае я-кратное использование метода Форда - Беллмана не является наилучшим методом. [15]

Страницы: 1 2