Հոսքային ցանց

Գրաֆների տեսության մեջ հոսքի ցանցը (flow network), որը նաև կոչվում է տրանսպոտային ցանց, ուղղված գրաֆ է, որտեղ ամեն ծայրը ունի որոշակի թողունակություն, և որտեղ այդ ծայրերը ստանում են հոսք: Հոսքի քանակը եզրերի վրա չի կարող գերազանցել եզրի թողունակությունը: Հաճախ գործառնությունների հետազոտությունում (Operations Research) ուղիղ գրաֆն անվանվում է «ցանց», գագաթները կոչվում են «հանգույցներ», իսկ եզրերը կոչվում են «աղեղներ»:

Հոսքը պետք է բավարարի այն սահմանափակումները, որ որոշ հոսքերի գումարը դեպի հանգույց հավասար է դրանից դուրս եկող հոսքեի գումարին, բացառությամբ այն դեպքերի, երբ դա «աղբյուրն» է` հիմքը, որն ունի ավելի շատ դուրս եկող հոսք, կամ ընդունիչն է, վերջինս էլ ունի ավելի շատ մուտքային հոսք: Ցանցը կարող է օգտագործվել որպես երթևեկության մոդել ճանապարհային համակարգի մեջ, հեղուկներ խողովակների մեջ, հոսանքներ էլեկտրական միացման մեջ կամ որևէ նման մի բան, որի մեջ ինչ-որ բան «ճանապարհորդում» է ցանցային հանգույցների միջոցով:

Նկարագրությունը

$\ G(V,E)$ -ն վերջավոր ուղղահայաց գրաֆ է, որում ամեն ծայրը $\ (u,v) \in E$ ունի ոչ բացասական , իրական արժեքով թողունակություն` $\ c(u,v)$: Եթե $\ (u, v) \not \in E$ մենք ենթադրում ենք, որ $\ c(u, v) = 0$: Մենք տարբերակում ենք երկու գագաթներ` ինֆորմացիայի աղբյուրը $\ s$-ը և ընդունիչը $\ t$-ն: Հոսքային ցանցը իրական ֆունկցիա է $\ f:V \times V \rightarrow \mathbb{R}$ հետևյալ երեք հատկություններով բոլոր $\ u$ և $\ v$ հանգույցների համար:

Թողունակության սահմանափակումներ (Capacity constraints):	$\ f(u,v) \le c(u,v)$: Հոսքը եզրով չի կարող գերազանցել իր թողունակությունը:
Շեղման սիմետրիկություն` համաչափություն (Skew symmetry):	$\ f(u,v) = - f(v,u)$. Ցանցային հոսքը $\ u$ից դեպի $\ v$պետք է լինի հակադիր $\ v$-ից դեպի $\ u$ ցանցային հոսքին (տես օրինակը):
Հոսքի պահպանություն (Flow conservation):	$\ \sum_{w \in V} f(u,w) = 0$, քանի դեռ $\ u=s$ կամ $\ u=t$: Ցանցային հոսքը դեպի հանգույց 0 է , բացառությամբ աղբյուրի (source), որը "արտադրում է" հոսք,և ընդունիչի, որը "սպառում", օգտագործում է հոսքը:

Նկատենք, որ $\ f(u,v)$-ն հոսքային ցանցն է $\ u$-ից դեպի $\ v$: Եթե գրաֆն իրենից ներկայացնում է ֆիզիկական ցանց,և եթե գոյություն ունի իրական հոսք, օրինակ, 4 միավոր $\ u$-ից դեպի $\ v$, և 3 միավորի իրական հոսք $\ v$-ից դեպի $\ u$, մենք ունենք $\ f(u,v)=1$ և $\ f(v,u)=-1$:

Ծայրի մնացորդային թողունակությունը $\ c_f(u,v) = c(u,v) - f(u,v)$-ն է:Սա նկարագրում է մնացորդային ցանցը` որոշված $\ G_f(V,E_f)$-ով, որը տալիս է հասանելի թողունակության որոշակի քանակություն: Տեսնենք, որ դա մնացորդային ցանցում կարող է լինել ծայր $\ u$-իվ դեպի $\ v$, նույնիսկ եթե չկա ոչ մի ծայր` եզր $\ u$-ից դեպի $\ v$ սկզբնական (օրիգինալ) ցանցում: Հոսքերը հակադիր ուղղություններում կրճատվում (չեղարկվում) են` նվազեցնելով հոսքը $\ v$-ից դեպի $\ u$, նույնն է, թե ավելացվում են հոսքերը $\ u$ -ից դեպի $\ v$: Աճող ճանապարհը ուղի է $\ (u_1,u_2,\dots,u_k)$ մնացորդային ցանցում, որտեղ $\ u_1=s$, $\ u_k=t$, և $\ c_f(u_i, u_{i+1}) > 0$. Ցանցն ունի մաքսիմում հոսք, այն և միայն այն դեօքում, եթե չկա աճող ճանապարհ մնացորդային ցանցում:

Եթե որևէ մեկին անհրաժեշտ է մոդելավորել ցանց ավելի քան մեկ սկզբնաղբյուրներով, ապա այդ աղբյուրը` supersource-ը ներկայացվում է գրաֆի տեսքով: Սա պարունակում է գագաթ, որը ծայերով կապված է յուրաքանչյուր սկզբնաղբյուրի հետ անսահման թողունակությամբ,այսպիսով ստեղծվում է գլոբալ սկզբնաղբյուրի տպավորություն: Ընդունիչների համար նմանատիպ կառուցվածքն էլ կոչվում է գերընդունիչ` supersink.

Օրինակ

Հոսքային ցանց, որը ցույց է տալիս հոսքը և թողունակությունը

Աջում մենք տեսնում ենք հոսքային ցանցը` նշված $s$-ով, սկզբնաղբյուրը $t$-ով, և չորս լրացուցիչ հանգույցներ: Հոսքը և թողունակությունը նշանակված է $f/c$-ով: Տեսնենք, թե ինչպես է ցանցն ապահովում շեղման համաչափությունը, թողունակության սահմանափակումները և հոսքի պաշտպանությունը: Հոսքի ամբողջ գումարը $s$-ից դեպի $t$ 5 միավոր է, որը կարող ենք հեշտությամբ նկատել այն փաստից, որ ամբողջ ելքային հոսքը $s$-ից 5 միավոր է, որը նաև մուտքային հոսքն է դեպի $t$: Մենք գիտենք, որ ոչ մի հոսք չի հայտնվում կամ անհետանում ցանկացած հանգույցներում:

Մնացորդային ցանց վերևի հոսքային ցանցի համար, որը ցույց է տալիս մնացորդային թողունակությունները

Ներքևում տեսնում ենք տրված հոսքի համար մնացորդային ցանց: Տեսնենք, թե ինչպես է, որ կա դրական մնացորդային թողունակություն ծայրերի վրա, որտեղ սկզբնական թողունակությունը 0 է, օրինակ ծայրի համար $(d,c)$ է: Այս հոսքը մաքսիմում հոսք չէ:Այստեղ ճանապարհներում կա հասանելի թողունակություն $(s,a,c,t)$, $(s,a,b,d,t)$ և $(s,a,b,d,c,t)$, որոնք աճող ճանապարհներ են: Մնացորդային թողունակության առաջին ճանապարհը հետևյալն է` $\min(c(s,a)-f(s,a), c(a,c)-f(a,c), c(c,t)-f(c,t))$$= \min(5-3, 3-2, 2-1) = \min(2, 1, 1) = 1$: Նկատենք, որ այդ աճող ճանապարհը $(s,a,b,d,c,t)$ գոյություն չունի սկզբնական (օրիգինալ) ցանցում, բայց մենք կարող ենք ուղարկել հոսք դրա միջով և դեռ ստանալ իրական հոսք:

Եթե սա իրական հոսք է, փաստորեն հնարավոր է լինի 2-ի հոսք $a$-ից դեպի $b$, և 1-ի հոսք $b$-ից դեպի $a$, բայց մենք միայն օժանդակում ենք ցանցային հոսքը:

Կիրառություններ

Պատկերացնենք մի շարք ջրատար խողովակներ ցանցին համապատասխան: Յուրաքանչյուր խողովակ ունի որոշակի տրամագիծ, այսպիսով այն կարող է օժանդակել որոշ քանակությամբ ջրի հոսքը:Այնտեղ, որտեղ խողովակները հանդիպում են, ջրի ամբողջ քանակությունը լցվում է դրանց մեջ, և այդ միացումը պետք է հավասար լինի ջրի դուրս եկող քանակությանը: Մենք ունենք ջրի մուտք, որը մեր սկզբնաղբյուրն է (source), և ջրի ելք, որը մեր ընդունիչն է: Հոսքն էլ պետք է լինի ջրելու այն հնարավոր եղանակը, որպեսզի հասնենք մուտքից դեպի ելքին:

Հոսքեր կարող ենք համարել տրանսպորտային ցանցում մարդկանց,կամ էլեկտրականությունը էլեկտարական բաշխման համակարգում: Նմանատիպ ֆիզիկական ցանցերում մուտքային հոսքը ցանկացած միջանկյալ հանգույցում, պետք է հավասար լինի այդ հանգույցի ելքային հոսքին: Այս պաշտպանության սահմանափակումը ձևակերպվում է որպես Կիրչհոֆի հոսանքի օրենք (Kirchhoff's current law):

Հոսքային ցանցերը կիրառվում են նաև էկոլոգիայում:Ցանցային էկոհամակարգի դաշտի վերլուծությունը` մշակված Ռոբերտ Ուլյանովիչի և ուրիշների կողմից, ներառում է իր մեջ հասկացություններ ինֆորմացիայի տեսությունից և ջերմադինամիկաից ուսումնասիրելու այս ցանցերի էվոլյուցիան ժամանակի ընթացքում:

Ամենապարզ և ամենատարածված խնդիրրը, որը լուծվում է օգտագործելով ցանցային հոսքերը, դա այսպես կոչված մաքսիմում հոսքը գտնելն է, վերջինս էլ տրված գրաֆում ապահովում է ամենաշատ հնարավոր հոսքը աղբյուրից դեպի ընդունիչ: Կան շատ ուրիշ խնդիներ, որոնք լուծվում են մաքսիմում հոսքի ալգորիթմի օգնությամբ: Մաքսիմում հոսքի խնդիրները կարող են լուծվել Ֆորդ-Ֆուլկերսոնի ալգորիթմի հիման վրա: Մաքսիմում հոսքի մինիմում կրճատման թեորեմը ապացուցում է, որ մաքսիմում ցանցային հոսքը գտնելը հավասարազոր է մինիմում թողունակության կրճատումը գտնելուն, որը առանձնացնում է աղբյուրն ու ընդունիչը:

Բազմապրանքային հոսքերի խնդրում մենք ունենք բազմաթիվ աղբյուրներ և ընդունիչներ, և տարբեր "ապրանքատեսակներ", որոնք հոսքեր են տրված աղբյուրից դեպի ընդունիչը: Այսպիսի օրինակ կարող են հանդիսանալ տարբեր ապրանքները, որոնք արտադրվել են տարբեր գործարաններում և պետք է մատակարարվեն տարբեր հաճախորդներին նույն տրանսպորտային ցանցով:

Մինիմում արժեքի հոսքի խնդրում ամեն ծայր $u,v$ ունի տրված արժեք` $k(u,v)$, ինչպես նաև հոսքը ուղարկելու արժեքը` $f(u,v)$ ծայրերով` $f(u,v) \cdot k(u,v)$. Այս խնդրի նպատակն է ուղարկել տրված հոսքի քանակությունը աղբյուրից դեպի ընդունիչ հնարավոր ցածր գներով:

Շրջանառության խնդրում մենք ունենք ավելի ցածր սահման $l(u,v)$ ծայրերին,ի հավելումն ավելի բարձր սահմանի $c(u,v)$: Ամեն ծայր ունի իր արժեքը: Հաճախ հոսքի պաշտպանությունը պահում է բոլոր հանգույցները շրջանառության մեջ, և գոյություն ունի կապ ընդունիչից դեպի աղբյուրը: Այս եղանակով մենք կարող ենք որոշել ամբողջ հոսքը $l(t,s)$-ով և $c(t,s)$-ով: Հոսքը շրջանառվում է ցանցով, ինչպես տեսնում ենք խնդրի անվան մեջ:

Աղբյուրներ

• Հոդվածի սկզբնական տարբերակը թարգմանվել է անգլերեն վիքիպեդիայի համանուն հոդվածից։

Արտաքին հղումներ

• Մաքսիմում հոսքի խնդիրը
• Իրական գրաֆի օրինակներ
• Lemon C++գրադարան մաքսիմում հոսքերով, մինիմում արժեքի շրջանառության ալգորիթմներ
• QuickGraph, Գրաֆների կառուցվածքներ, ալգորիթմներ .Net-իհամար