5.3.1. Изявление на проблема за определяне на максималния поток в комуникационна мрежа
Нека проектирана мрежа. При проектирането на даден набор от информационни източници S и набор от данни за получателя Т. Обикновено тези комплекти могат да бъдат припокриване или идентичен S = Т. тоест, една възлова точка може да бъде възел източника и получателя. Всеки възел на множеството S генерира поток от информация, която се предава към възли на набор Т. Клоновете на графиката може да има предварително определена честотна лента с (U, V), между всяка двойка възли U и V. или може да се наложи да се определи способността на всеки клон. Bandwidth клонове (ръбове) могат да се разглеждат като максималната скорост на предаване на информация по клона.
Предвид топологията на мрежата, т.е. съвпадение набор от възли и клони, клоните дадени тегловна матрица А [U, V], където теглата изпълнява честотна лента на всеки клон.
Какво задачи вече може да бъде решен с тези първоначални данни? Очевидно е, че множеството от свързани възли могат да бъдат идентифицирани. Можете да намерите най-кратките пътища между всички двойки върхове. Най-накрая да намерите всички пътища между върховете и и т. В допълнение, всеки път трябва да бъде различен от друга, най-малко един клон или възел. Въпреки това, решението на всяка една от тези задачи върби няма да ни позволи да се отговори на въпроса - какво е максималното количество информация за единица време може да бъде предаден от възел и към възел тон. или от група с множество възли S на комплекта група от възлови точки. Т. решаване на посочените по-горе проблеми не помагат и решават, че обратният проблем - колко и какви капацитети изисква клонове да пропуснете всички информационните потоци между набор S от възли и множество точки на Т. Такъв проблем по пътя към истинските мрежи, и не работи (не позволява измерение предизвикателства и несигурност на въвеждане на данни).
За формулирането на проблема, ние се формализира някои понятия. Ние присвоява на всеки клон (U, V) част от теглото е (U, V), поток, наречен от ф о. Стойността на потока за всеки клон (U, V) може да се разглежда като скоростта, с която се предава информация в този бранш.
След това количество наречен отклонението на F на потока в об
където Σf (V, U) - отпадъчните води от върховете ст. Σf (U, V) - поток въвеждане на връх V, определя количеството на отпадъчните води от върха ф.
Тази стойност може да бъде отрицателна (когато срещу по-голяма част, това, което излиза), положителни (когато не са в обем по-голям от страна) и на 0. последния случай ще ни интересува най-много. Това означава, че потокът не се натрупва и не се случи във всеки от върховете изключение S и т.
Под поток от и за тон имаме предвид функцията, за която условия
Което нишка може да се прехвърля от и за тон чрез тези клонове? Очевидно е, че има предвид, че клона, ориентирани
това означава, че ще бъде равна на сумата от индивидуалните възможности на отраслите, включени в среза.
Съгласно прорез R (А) на съответната мрежа AV (подклас V), А ≠ V. А ≠ 0. имаме предвид множеството от дъги, (U, V), така че (U, V) W. Ua и VV \ А.
За произволно е на потока в поток мрежа през процепа определено в очевиден начин
След това, ако си представим, че SA. телевизор \ А. потокът на Т се определя като
Представяме идеята за минимален разрез. При минималната вложката Zoom разделяне и и т. имаме предвид произволна точка на R (A), SA и телевизор \ А с минималната широчина на честотната лента.
Пример. Ние формулира класическата теория на потоци в мрежи теория. Тази теорема е максималният поток и минимално напречно сечение:
Размерът на всеки поток и за тон. не надвишава допустимото натоварване на минималната разреза, и там е поток, който достига тази стойност.
Максималният дебит в мрежата
Всички известни алгоритми за конструиране максимален поток на базата на последователни увеличения поток, промяна на потока, което увеличава стойността си, най-често на базата на метода за увеличаване на верига (или удължаване пътеки).
Ние предлагаме поредица от понятия, които ще бъдат необходими в по-нататъшното представяне.
Ние казваме, че дъга m G мрежа е допустимо дъга от ф да о по отношение на F на потока. ако
Свързани статии