Մասնակից:MargaryanMargarit/Սևագրություն
Սա MargaryanMargarit մասնակցի սևագրության էջն է՝ «ավազարկղը», և մասնակցի էջի ենթաէջերից մեկն է։ Այն ծառայում է որպես սևագիր և փորձարկումների վայր։ Սա հանրագիտարանային հոդված չէ։ Ձեր անձնական ավազարկղը ստեղծելու համար սեղմեք այստեղ։ Այլ ավազարկղեր՝ Ընդհանուր ավազարկղ |
Գրաֆների տեսության մեջ հոսքի ցանցը (flow network), որը նաև կոչվում է տրանսպոտային ցանց, ուղղված գրաֆ է, որտեղ ամեն ծայրը ունի որոշակի թողունակություն, և որտեղ այդ ծայրերը ստանում են հոսք: Հոսքի քանակը եզրերի վրա չի կարող գերազանցել եզրի թողունակությունը: Հաճախ գործառնությունների հետազոտությունում (Operations Research) ուղիղ գրաֆն անվանվում է «ցանց», գագաթները կոչվում են «հանգույցներ», իսկ եզրերը կոչվում են «աղեղներ»:
Հոսքը պետք է բավարարի այն սահմանափակումները, որ որոշ հոսքերի գումարը դեպի հանգույց հավասար է դրանից դուրս եկող հոսքեի գումարին, բացառությամբ այն դեպքերի, երբ դա «աղբյուրն» է` հիմքը, որն ունի ավելի շատ դուրս եկող հոսք, կամ ընդունիչն է, վերջինս էլ ունի ավելի շատ մուտքային հոսք: Ցանցը կարող է օգտագործվել որպես երթևեկության մոդել ճանապարհային համակարգի մեջ, հեղուկներ խողովակների մեջ, հոսանքներ էլեկտրական միացման մեջ կամ որևէ նման մի բան, որի մեջ ինչ-որ բան «ճանապարհորդում» է ցանցային հանգույցների միջոցով:
Նկարագրությունը[խմբագրել | խմբագրել կոդը]
-ն վերջավոր ուղղահայաց գրաֆ է, որում ամեն ծայրը ունի ոչ բացասական , իրական արժեքով թողունակություն` : Եթե մենք ենթադրում ենք, որ : Մենք տարբերակում ենք երկու գագաթներ` ինֆորմացիայի աղբյուրը -ը և ընդունիչը -ն: Հոսքային ցանցը իրական ֆունկցիա է հետևյալ երեք հատկություններով բոլոր և հանգույցների համար:
Թողունակության սահմանափակումներ (Capacity constraints): : Հոսքը եզրով չի կարող գերազանցել իր թողունակությունը: Շեղման սիմետրիկություն` համաչափություն (Skew symmetry): . Ցանցային հոսքը ից դեպի պետք է լինի հակադիր -ից դեպի ցանցային հոսքին (տես օրինակը): Հոսքի պահպանություն (Flow conservation): , քանի դեռ կամ : Ցանցային հոսքը դեպի հանգույց 0 է , բացառությամբ աղբյուրի (source), որը "արտադրում է" հոսք,և ընդունիչի, որը "սպառում", օգտագործում է հոսքը:
Նկատենք, որ -ն հոսքային ցանցն է -ից դեպի : Եթե գրաֆն իրենից ներկայացնում է ֆիզիկական ցանց,և եթե գոյություն ունի իրական հոսք, օրինակ, 4 միավոր -ից դեպի , և 3 միավորի իրական հոսք -ից դեպի , մենք ունենք և :
Տես նաև[խմբագրել | խմբագրել կոդը]
- Կոնստրուկտալ թեորեմ
- Ֆորդ-Ֆուլկերսոնի ալգորիթմը
- Հոսք (համակարգչային ցանց)
- Մաքսիմում հոսքի, մինիմում կրճատման թեորեմ
- Ամենակարճ ճանապարհի խնդիրը
Հղումներ[խմբագրել | խմբագրել կոդը]
Արտաքին հղումներ[խմբագրել | խմբագրել կոդը]
- Մաքսիմում հոսքի խնդիրրը
- հոսք
- Իրական գրաֆի օրինակներ
- Ծրագրեր հոսքային ցանցերի խնդիրների համար
- Lemon C++գրադարան մաքսիմում հոսքերով մինիմում արժեքի շրջանառության ալգորիթմներ
- QuickGraph, Գրաֆների կառուցվածքներ, ալգորիթմներ .Net-ի համար
Category:Network flow Category:Graph algorithms Category:Operations research Category:Directed graphs