Велика енциклопедия на нефт и газ

Безконтурна графика

Графика G с отворен край се превръща в мрежа G, когато е посочена съответната редовна функция. Да предположим, че G съдържа контури. [2]

В действителност, в краен безконтурен граф винаги съществува връх a, в който не влиза нито една дъга. [3]

Можем да кажем, че неконтролираната графика H с обозначени ръбове е графика на общото решение на системата (1), ако поне един път с максимална дължина преминава през всеки връх на графиката, а картографирането на T (a) е едно -до-едно съответствие между множеството P и множеството от максимални пътеки на графиката. [4]

Ясно е, че G е неконтролирана графика. [пет]

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

Както и преди, ще приемем, че програмният модел е насочена отворена графика, чиито върхове съответстват на операциите за обработка и обмен, а дъгите съответстват на информационни връзки и условни клонове. Задачата се представя като последователност от две или повече операции, работата - като последователност от операции и задачи. Всяка от операциите се характеризира с априори зададена продължителност rfj и цена C - изпълнение на ресурс от тип j - ro и съответстващи стойности на m -, Cij, получени в резултат на мащабиране. TV)) където xi е независимата променлива (продължителността TJ на операцията или цената Ci на нейното използване на ресурса), j е целта на i-тата операция. [7]

Според алгоритъм 3.5, когато описваме алгоритъма за намиране на пътеки в отворена графика, можем да приемем, че всяка дъга преминава от връх с по-ниско число към връх с по-голямо число. [8]

Нека изискваме числата wtj да отговарят на следното условие: съществува насочена неконтролирана графика G (N, U), такава от и. Лесно е да се види, че в горния пример числата wtj отговарят на това условие. [девет]

АЛГОРИТЪМ 3.6. (Намиране на разстоянията от източника до всички върхове в неконтролирана графика. [10]

&) не повече от n (n - 1)/2 единици (G е отворена графика) и в резултат на извършването на една трансформация II в нея се въвежда поне една нова единица. [единадесет]

Първият проблем е добре известен в теорията на операционните изследвания. Може да бъде ефективно решен само за безконтурни графики. Помислете за неконтролирана претеглена графика. От една страна, този случай включва и обикновени графики; от друга страна, той е по-близо до изискванията на практиката. [12]

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

Алгоритъм 4.10, кръстен на Hopk-roft - Karp, е описан подробно по-долу. В този алгоритъм помощна безконтурна мрежа или по-скоро спомагателна безконтурна графика, тъй като честотната лента на всички ръбове е равна на една, се изгражда с помощта на процедурата PGA. На следващо място се извършва първоначално търсене в графика Hm, като се започне от свободните върхове в X. Увеличаването на съществуващото съвпадение по максималния набор от най-кратки увеличаващи се пътища с двойно различни набори от върхове се осъществява чрез процедурата PHASE. [14]

Очевидно проблемът за определяне на разстоянието между всички двойки върхове може да бъде решен с помощта на един от описаните по-рано методи за намиране на разстоянията от фиксиран връх (един по един за всеки връх). По този начин получаваме алгоритъм със сложност O (n4) (използвайки метода на Форд - Белман) или O (n3) за неконтролирани графики или неотрицателни тегла. Оказва се обаче, че като цяло използването на метода на Форд-Белман i-fold не е най-добрият метод. [петнадесет]