Резюме остатъчен път на транспортната кутия

въведение

• 1 Определения
• 2 имота
• ПРИМЕР 3
• 4 нанасяне Референции
  

На теория графика, транспортната мрежа - насочен графика G = (V, E). в която всяко ребро има неотрицателна капацитет и potokf (U, V). Идентифицира два пика: istochniks и stokt такава, че всеки друг връх от лъжи по пътя от и за тон. Транспортната мрежа могат да бъдат използвани, за да се симулира, например, за движение по пътищата.

Цяло число транспортна мрежа - транспортна мрежа, всички възможности на краищата това - цели числа.

1. Определения

Транспортна мрежа (мрежа поток) - целеви графика, в която

• всеки край се обозначава с неотрицателна трафик. Ако и след това.
• разпределени два пика: източник (източници) и и източване (мивка) гр. такова, че всяка друга мрежа, връх се намира по пътя от и за т.

Поток (поток) - функция със следните свойства за всички върхове:

• Ограничаване на честотната лента (капацитет ограничения). Flow не може да надвишава капацитета на:
• Antisymmetry (кос симетрия). Потокът от задължително да е обратна на движението на:
• Поддържане на потока (опазване на потока): за всички, но на източника и канализационна тръба.

"Количество Flow (стойност на потока) е сумата от източник на потока. В бъдеще ние ще се окаже, че тя е равна на сумата на потока в канала.

Максимална проблем поток (максимум проблем поток): намерите поток е такава, че скоростта на потока е максимален.

Разрезът (и-т рязане) - разделяне на набор от всички върхове на V в две подгрупи, А и В, така че.

раздел Пропускателна капацитет (А, В) (капацитета на S-т разрез на (А, В)) - сумата на капацитета на всички ръбове на А в В.

Поток през разреза (А, В) - сумата от всички потоци от А до Б. Тя не надвишава капацитета на честотната лента на среза, защото.

Минималната разреза - намаляване на минималния капацитет.

Остатъчен капацитет (остатъчен капацитет) Винаги е не-отрицателни краища на условието за ограничаване на честотната лента.

Остатъчен мрежа (остатъчен мрежата) тук - много ребра с неотрицателна остатъчен капацитет. Реброто може да бъде остатъчната мрежа в, дори и да не е в домашната мрежа. Това се прави, когато в домашната мрежа е с обратен ръб (о, ф) и потокът от него е положителен.

Увеличава (остатъчен допълващите) начина (засилвайки път) - път в остатъчната мрежа, когато това може да се докаже, че потокът е максимална, ако и само ако няма начин за повишаване остатъчната мрежа.

2. свойства

Поток през всяка секция е сумата на потоци от източника.
Доказателство. нека нарязани (A, B). Разглеждане на сумата от всички потоци от всички върховете, принадлежащи към А. Това е

През първите суми за всяка двойка на върховете (U, V) има две условия F (U, V) и F (V, U), равни по големина и противоположни по знак. Следователно, това количество е равно на нула. Вторият сумата е поток през участъка (А, В). Следователно, сумата от всички потоци на всички върхове, принадлежащи към А, е равна на потока през разреза. От друга страна, сумата на потоци от всеки възел, с изключение на S и Т, е равна на нула, както и. Следователно, сумата от всички потоци от всички върховете, принадлежащи към А, е сумата на потоци от S. Следователно поток през участъка (А, В) е равна на сумата от потоците S, QED.

Количеството на потоци от гориво е сумата на потока на канала.
Доказателство. разгледа разреза. Потокът през този раздел поток е сумата на канала. От друга страна, що беше показано, потокът през този (или друга) раздел е сумата на потоци от източника. Това доказва теоремата.

Максимален поток е положителен, ако и само ако съществува път от извора до канала, ребрата, простиращи от положителната честотната лента.
Доказателство. Нека този път P съществува. Нека в - минимални пропусквателни на ръбове, принадлежащи P. Нека в поток на всички ръбове на P, и нула при всички други ръбове. Тогава общият поток от източника е равна на с, тогава има положителна. Сега нека да кажем, че това не е така, че е недостъпна от т а в ребрата с положителна трафик. Нека А - множество върхове достъпни от ите от тези ребра, В - недостижима. След това, тъй като след това (А, В) се нарязва. В допълнение, има ребра (а, Ь) с положителен честотна лента, така че, или б ще бъдат постигнати от S. Следователно капацитетът производителност на участъка (А, В) е нула, и по този начин през него поток винаги е нула. Следователно, количеството на потока от източника винаги е нула.

Потокът е максимална, ако и само ако няма начин за повишаване остатъчен seti.Dokazatelstvo. нека този път P е. Нека в - минимум възможностите на краищата, принадлежащи на Р, в остатъчната мрежа. За всички двойки повишават F (U, V), за да се намали в и е (о, ф) от С. Увеличихме общия поток от източник, и, следователно, той не е бил максимално. Сега, напротив, да кажа, че това не е така. Нека докажем чрез противоречие, че F на потока в домашната мрежа осигурява максимална обща поток от с. Да предположим, че това не е така, тогава е поток ", което осигурява по-голяма общия поток на S. Лесно е да се провери, че f'-е - поток в остатъчната мрежа, при положение че то положителен поток на сумата от с. Следователно, остатъчното мрежа е път от източника до мивката, т.е. увеличава път. В момента са получили противоречие.

Ford-Fulkerson теорема. Стойността на максималния поток е минимален капацитет рязане.
Доказателство. размер на поток от и винаги е равен на потока през който и да е, включително и минимално, нарязани, следователно, не надвишава допустимото натоварване на минималната среза. Следователно максималният капацитет на потока от не повече от минимален разрез. Остава да се докаже, че той не е по-малко от него. Нека потока е максимален. След това, мрежата на остатъчния поток не е достижим от източника. Нека A - множество върхове достигнати от източника към остатъчната мрежа, B - недостижим. След това, тъй като след това (А, В) се нарязва. В допълнение, има ребра (а, б) в остатъчен нетен положителен честотна лента, така че иначе биха били постигнати б на S. Поради това, в източник мрежа съгласно всяка поток като ръб е равен на капацитета си, а оттам и на поток през участъка (А, В) е равна на честотната лента. Но потокът през всеки разрез е общият поток от източника, който в този случай е равна на максималния поток. От друга страна, капацитетът на всяко прекъсване е не по-малко от минималната разреза капацитет. Чрез комбиниране на тези три твърдения, ние откриваме, че максималният капацитет на потока на не по-малко от минималната среза. Това доказва теоремата.

Транспортната мрежа с посочване на потока и честотна лента.

Тук е показано на транспортната мрежа на източника, канализацията и четири допълнителни единици. Feed и трафик обозначени съответно. Потокът от източника на изтичане е 5, която се вижда лесно, тъй като потокът е от 5, която също е на разположение.

Остатъчен оглед мрежа план на схема показваща остатъчен капацитет.

По-долу е остатъчен за по-горе мрежа поток. Моля, имайте предвид, че не е ограничаване на капацитета за някои ребра, а в домашната мрежа, тя е равна на нула. Например, един ръб. Този поток не е максимална. Има начини да се увеличат и. Остатъчният капацитет на първия път. Увеличаването на пътя не съществува в домашната мрежа, но можете да го пропуснете за правилния поток.

4. Заявленията

Най-често срещаният пример за използване на транспортните мрежи - намери максималният поток. което означава, че максимум общия поток от S към Т. Fulkerson, Едмъндс алгоритъм - - С цел да се намери максималният поток в Форд алгоритъм мрежа може да се използва Карп и др.

Проблемът с притока на минимална цена, като всеки ръб (U, V) е свързан с цената к (U, V). Разходите за доставка потока F (U, V) от ребро. Задачата - да се изпрати предварително определено количество поток от и за тон с най-ниската цена.

литература