|
Nazorat savollari
Dinamik dasturlashning umumiy vazifasini qanday o'rnatish kerak?
Dinamik dasturlash muammosi qanday shakllantirilgan va uning chiziqli dasturlash muammolaridan farqi nimada?
Dinamik dasturlashning matematik modelining xususiyatlari qanday?
Dinamik dasturlash usulining asosi nimada?
Optimallashtirish tamoyili nima va Bellman tenglamalari qanday yozilgan?
11m: Tarmoqlardagi oqimlar.
Asosiy vazifalar
Agar yo'naltirilgan grafning har bir yoyiga biron bir moddaning oqishini tayinlasak, grafik transport, aloqa va boshqa sohalarda, tovarlar, ma'lumotlar yoki odamlarning xayoliy yoki xayoliy harakati bilan bog'liq qator muammolarni o'rganish uchun qulay modelga aylanadi.
Ikkita asosiy vazifalar o'rganilmoqda:
har bir yoy orqali o'tuvchi oqim yuqorida va pastda joylashgan bo'lishi sharti bilan berilgan ikkita vertikal o'rtasidagi umumiy oqimni maksimal darajada oshirish;
har bir kamonga oqim birligining qiymati belgilanganda, minimal xarajatlar bilan cheklangan oqimlarni topish muammosi.
Biz yo'naltirilgan graf ta'rifini cheklaymiz
- ko'chadan mavjudligi nomaqbuldir
- agar vi dan vj gacha bo'lgan yoy bo'lsa, vj dan vi gacha bo'lgan yoy yo'q
Yo'naltirilgan graf bog’langan bo'lishi kerak
Ajratuvchi to'plamlar
G = (V, E) ulangan grafikka, F E esa uning chekkalari to'plamiga bo'lingan bo'lsin. Bundan tashqari, F subgrafi G = (V, E - F) o'chirilgan taqdirda, ajratuvchi to'plam deb ataladi.
Ajratuvchi to'plamlar har doim mavjud (agar grafikda kamida ikkita vertikal chiziq bo'lsa), chunki F = E har doim o'rnatilishi mumkin, shubhasiz, grafikni ikkitadan ortiq tarkibiy qismlarga ajratish mumkin.
Kesimlar
Agar bog'langan G = (V, E) grafigi berilgan bo'lsa va uning uchlari A va A bo'lmagan ikkita pastki qismga bo'lingan bo'lsa, A ni A bilan bog'laydigan qirralarning kesmasi kesish deb ataladi.
Har qanday A to'plam uchun, bu G to'plamning ulanishi tufayli cheklanmagan bo'ladi va shuning uchun kesish aniqlanadi. Berilgan har qanday grafik uchun, turli xil to'plamlar bilan belgilangan kesmalar to'plami barcha ajratuvchi to'plamlar sinfining kichik sinfini tashkil qiladi va bundan tashqari, har qanday ajratuvchi to'plamda uning pastki qismi sifatida kamida bitta kesma mavjud.
Tarmoqlar
Tarmoq deganda biz S = G, c juftlikni nazarda tutamiz, bu erda G = V, E - ixtiyoriy yo'naltirilgan grafik, va c: E R har bir yoy, v that manfiy bo'lmagan haqiqiy son bilan bog'liq bo'lgan funktsiya. c (va, v), bu yoyning o'tkazish qobiliyati deb nomlangan. V va E to'plamlari navbati bilan vertikallar to'plami va S tarmog'ining yoylari to'plami deb ataladi.
Tarmoq oqimi
S tarmog'idagi oqim f funktsiyasi E.da aniqlangan f (u, v) yoy bo'ylab (u, v) oqim deyiladi. Aniqroq aytganda, oqim u dan v gacha bo'lsa f (u, v)> 0 va oqim v dan u gacha bo'lsa f (u, v) <0. Aniqlik uchun biz tarmoqning geometrik bajarilishini yodda tutamiz va | f (u, v) | bir hil moddaning yoy orqali doimiy oqimi tezligi sifatida (u, v). Oqim yo'nalishi f (u, v) belgisi bilan belgilanadi.
Oqim effekti bo'yicha uchlarini tasniflash
Ixtiyoriy f: E R funksiya va S tarmog'ining xtiyoriy iverteksi v uchun, biz ularning miqdorini hisoblaymiz
Agar f (u, v) ni u dan v gacha bo'lgan oqim sifatida talqin qilsak, Divf (v) miqdori v verteksidan kelib chiqadigan "oqim" (aniq oqim) ni aniqlaydi. Bu qiymat
> 0 bo'lishi mumkin (agar u verteksning ichiga kirgandan ko'ra ko'proq chiqadigan bo'lsa), <0 (agar verteksga undan ko'p kirish kirsa, ya'ni oqim v v verteksida "to'planadi") va nihoyat , = 0. Bir vertex oqim hosil qiladi, yutadi yoki saqlaydi.
V +, V– va V0 to'plamlariga tarmoq uchlarini quyidagicha guruhlaymiz:
V+ = {v V| Div (v) > 0},
V– = {v V| Div (v) < 0},
V0 = {v V| Div (v) < 0}.
V +, V–. V0 ga navbati bilan manbalar, lavabolar va oraliq vertikallar deyiladi
Maksimal oqim muammosini bir nechta chayqalish bilan bir nechta manbalar bilan bitta manbaga va bitta chig'anoqqa aylantirish
Oqim miqdori
Biz tarmog'imizdagi ikkita uchni tanlaymiz – s manba, va t drenaj(stok) t (s t).
S tarmog'idagi s dan t gacha bo'lgan oqim orqali biz f: E R shaklidagi quyidagi shartlarni bajaruvch ixtiyoriy funktsiyani nazarda tutamiz
f(u, v) с(и, v) xar bir qirra u, v Е (o’tkazuvchanlik qobiliyatini chegarasi),
f(u, v) = — f (v, u) (антисимметриklik)
va
Div f (v) = 0 xar bir uch v V \{s, t} (oqimni saqlash).
W(f) = Div f (s)-miqdorni f oqimning miqdori deb ataymiz.
S tarmoqning А V (А , А V) qism to’plamiga mos Р(А) kesim deb , u, v Е, u А и v V\A , kabi qirralar to’plamini tushunamiz.
S tarmog'idagi ixtiyoriy f oqim uchun, P(A) kesim orqali oqim tabiiy ravishda quyidagicha aniqlanadi:
Лемма 1.Agar s А va t V\A, u holda S dagi ixtiyoriy f oqim uchun t da W(f) = f(A, V\A) — f(V\A, A) bo’ladi.
Isbot. Hamma v A. uchun Divf (v) = 0 tenglamalarni umumlashtiramiz. Bu yig'indisi p (ortiqcha) va minus belgisi bilan berilgan bir qator atamalardan iborat va hech bo'lmaganda bitta vertikal, v esa A ga tegishli bo'lsa. A ga tegishli, keyin f (u, v) Divf (u) ga ortiqcha ishora bilan va Divf (v) da minus belgisi bilan paydo bo'ladi (va Divf (r) ifodasida va v dan boshqa har qanday r uchun ko'rinmaydi), F (u, v) va A, v V \ A shartlarining har biri aniq bir marta Divf (u) belgisi bilan paydo bo'ladi, bu esa f (A, V \ A) ni beradi. ) F (u, v) va V \ A, v A o'xshash atamalar f (V \ A, A) atamasi uchun javobgardir. Boshqa tomondan, bizning yig'indimiz Divf (s) = W (f), chunki har bir v A \ {s} uchun Divf (v) = 0.
Доказательство. Суммируем уравнения Divf (v) = 0 для всех v А. Эта сумма складывается из некоторого числа слагаемых f(u, v), снабженных знаком плюс и минус, причем хотя бы одна из вершин и, v принадлежит множеству А. Если обе вершины принадлежат A, то f(u, v) появляется со знаком плюс в Divf(u) и со знаком минус в Divf(v) (и не появляется в выражении Divf(r) ни для одного r, отличного от и и v), что в сумме дает 0. Каждое из слагаемых f(u, v), и A, v V\A появляется в точности один раз со знаком плюс в Divf(u), что в сумме дает f(A, V\A). Аналогичные слагаемые f(u, v), и V\A, v A отвечают за слагаемое f(V\A, A). С другой стороны наша сумма равна Divf(s) = W(f), ибо Divf(v) = 0 для каждого v A\{s}.
A A = V \ {t} ni olsak, ushbu holatda Lemma 1-dan olamiz
Divf(s) = W(f) = f(V\{t}, {t}) – f({t}, V\{t}) =
= – (f({t}, V\{t}) – f(V\{t}, {t})) = – Divf(t),
bu intuitiv haqiqatni ifoda etadi: manbadan keladigan oqim miqdori aniq drenajga kiradi. Umumiy holda, Lemma 1 oqimning umumiy miqdorini s ni t dan ajratadigan ixtiyoriy bo'limda o'lchash mumkinligini aytadi.
P (A) kesimning o'tkazuvchanligini aniqlang:
Под минимальным разрезом, разделяющим s и t, мы будем понимать произвольный разрез Р(А), s А, t V\A с минимальной пропускной способностью.
Do'stlaringiz bilan baham: |
