Feed мрежа

Функция, която определя nek- броя на мрежовите дъги (насочено графика). Всяко число се тълкува като определена интензивност на товара на потока бодното на тази дъга. AP с. са удобен модел за изследване на някои проблеми в transnorte, комуникации и др. области, свързани с движението на стоки, информация и др .. Много от проблема с потоци са линейното програмиране проблем и може да бъде решен с общи методи на тази теория. Въпреки това, в повечето случаи за поток задача позволи ефективни методи разтвор на теория графика. Нека всеки дъга (х, у) N .seti дължи неотрицателно реално число в (х, у) - дъга лента (х, у). Твърди се, че F на потока (х, у,) са стационарни поток величина именно върховете Rb връх S, дъги отговарят ограничена честотна лента капацитет, ако има такива дъга (х, у), тук -flow излизане, връх х, и - потокът включени в връх х. Проблемът на максималния поток между две възли е необходимо да се изгради постоянен поток от най-горния връх RB-те, с максималната възможна стойност ст. наличието на ефективни алгоритми за решаване на този проблем. Нека X - подмножество на върховете на мрежата N такова, че. След това множеството от дъги (х, у) Така че това. обади. нарязани. Bandwidth раздел, наречен. стойност. На следващата теорема за максимален и минимален поток напречно сечение: максималната стойност на потока е равна на минималната намаление на производствения капацитет. Заявленията често използват теоремата на цяло число, ако дъги честотна лента е неразделна, тогава има най-много число (фиксиран) дебит. Проблемът на максималния поток между два върха се намалява редица проблеми: проблемът с максимална AP с. множество източници и мивки; Проблемът на P. максимално с. като не-отрицателни ограничения на потока по дъги както на горната и долната част; Максималната проблем поток в неориентирани и смесени мрежи; Максималната проблем поток в мрежата с широчина на честотната лента на дъги и върховете и сътр. теоремата за максимален дебит и минимално сечение идентифицирани обща основа за брой на резултатите, получени по-рано в теорията на графики и комбинаторика. Установено е, че в резултат на това теорема може да бъде получен: теорема максимално съвпадение в двустранна графика теоремата на различни представители, теоремата на графики К-свързан (виж каре връзка.) Покриване теорема частично подредени определен най-малък брой схеми и друга информация. различни задачи на максимална проблема на потока е важен метод за теория на графите и комбинаторика. В редица проблеми на ап. Всяка дъга (X, Y) .sopostavlyaetsya номер (X, Y) - разходите за транспортиране на товарни единици на дъгата (X, Y) е необходимо да се намери .i поток, който отговаря на определени ограничения и свежда до минимум цялостното скоростта на потока. Проблемът на стойността на минимален поток е намирането на постоянен поток от най-горния връх RB S, който отговаря на ограниченията на дъги, пресичащи способности, и такава, че неговата стойност е равна на предварително определен брой о, а цената е минимална. В мрежата на транспортната задача е двустранно графично. В горната част на един дял Sl. Sm тълкува като отправни точки врата-ветното товари, други върхове T1. T н - двете дестинации. Всяка точка на тръгване Si има конкретна оферта дву и Tj всяка дестинация е известна търсенето CJ. Известен като разходите за превоз на товар ий на Si единици Т й. Предизвикателството е да се намери минимален поток на разходите, задоволяване на потребностите на всички дестинации. Ние също обмислят мулти-продуктови потоци и потоци, промяна във времето. . Референции [1] L. Ford - Fulkerson R. D. - П. потоци в мрежи платно. от английски език. М. 1966. VB Alekseev.

Източник: енциклопедия по математика в Gufo.me