Մասնակից:MargaryanMargarit/Սևագրություն

Գրաֆների տեսության մեջ հոսքի ցանցը (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$:

Տես նաև

• Կոնստրուկտալ թեորեմ
• Ֆորդ-Ֆուլկերսոնի ալգորիթմը
• Հոսք (համակարգչային ցանց)
• Մաքսիմում հոսքի, մինիմում կրճատման թեորեմ
• Ամենակարճ ճանապարհի խնդիրը

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

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