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

Հոսքային ցանց
Դաս	directed graph? և weighted graph?

Գրաֆների տեսության մեջ հոսքի ցանցը (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)\leq 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)$ -ով։ Հոսքը շրջանառվում է ցանցով, ինչպես տեսնում ենք խնդրի անվան մեջ։