По този начин, честота матрица за ориентирана задача графика има формата:
Подреждане на върха. Fulkerson алгоритъм
Номерация на възли и дъги, точно като техните конфигурации, не променя същността на природните явления и процеси, които описват графиките. В тази работа - процесът на производство на млечни продукти. Този имот се нарича графика изоморфизъм. Разтворът на проблеми, свързани с графики опростени, ако горната част на дъгата и графиките, разположени в определен ред.
Смята се, че един чифт върхове диграфът връх аз се предходните, а върховете Й - последван, ако съществува път от и до й, както и по пътя от и до й не съществува.
Чрез поръчка на върховете на диграфа разберем това номерация на върховете, в които:
връх от първата група не разполагате с изложеното по-горе, и върховете на последната група - следващата;
отгоре на всички други групи, не е нужно предишния и в началото на последната група - следващата;
връх на същите групи не са свързани чрез дъги.
След поръчване на върховете получени графика изоморфни на първоначалния.
Подреждането на върховете на диграфа може да се реализира, като следвате Fulkerson алгоритъм, който включва следните етапи:
1. Намерете връх, които не са включени в дъгата. Това е първото ниво на възли. След тях номерация, заедно с техните инциденти дъги психически отстранен от графиката.
2. В останалите графиката, както в оригинала, са върхове, които не са включени в дъга. Тези върхове са произволно номерирани от естествени числа, след като препратката към възлите първо ниво. Това челната.
Изолиране и наброяващи нива продължава до последния връх.
Поръчваме номерацията на върха, като следвате този алгоритъм:
Фигура 4.6 - изоморфни графики
В едно позоваване възел на графиката (фиг. 4.2) не включва аудио дъга, и намира дъга (1,3), (1,4). Задаване на възел номер 1 1 показва възел на фиг. 4.6 заедно с изходящи дъги и психически премахване върха на оригинална графиката.
Сред останалите възли на графиката на възел 2 сега не е част от една дъга. Задаване възел номер 2, съответно, и е показана на Фигура 4.6. Мислено премахване върха с неговите инциденти дъги от графиката.
Сега в блок 3, не е част от един дъга. Задаваме този горния номер 3 и го прехвърля на ориза. 4.6 и психически премахне от графиката.
На следващо място, ние виждаме, че във възела 4 не е част от една и съща дъга. Ние го броя 4 присвоява и се прехвърли в нов чертеж, психически да се маха от оригиналния графиката.
След операцията се извършва от звеното 5, без да въвеждате в нея дъги. Ние му номер 5 присвоява и се прехвърли в нов чертеж, психически да се маха от оригиналния графиката.
Сред останалите възли на графиката в блок 6 вече не включва всяка дъга. Задаване възел номера 6, съответно, и е показана на Фигура 4.6. Мислено премахване върха с неговите инциденти дъги от графиката.
Сега в събранието 7 не е част от една и съща дъга. Задаваме този горния номер 7. го прехвърля на ориза. 4.6 и психически премахне от графиката.
I остава един възел 8 без влизане и излизане от него дъги. Ние присвоява този възел номер 8 и е показано на фиг. 4.6.
По този начин, ние получаваме нова нареди графика (фиг. 4.6) е изоморфен на оригиналния графиката (фиг. 4.2).
Максималният дебит.
Алгоритъмът за определяне на максималния поток:
1. Конструкция на първоначалния поток
Една подгрупа на идентифицираните върховете достъпни от източник на ненаситени I ребра. Ако запасите S не попада в подгрупата на A, максималният поток е изградена, и проблемът е решен. Ако фондовата S влиза в подгрупата, трябва да преминете към следващата стъпка от алгоритъма.
Свързани статии