Безконтурний граф - Велика Енциклопедія Нафти та Газа, сторінка 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]