Yashiklar prinsipi

1- мисол. 1- шаклда манба ва ўпқони бўлган тармоқ тасвирланган бўлиб, унинг ёйлари ёнига мос ўтказиш қобилиятлари ёзилган, бунда ,
,

Бу тармоқ учун , , , , , , , , , , , , эканлиги шаклдан кўриниб турибди.
Тармоқнинг ҳар бир учи учун чиқиш ярим даражалари ва кириш ярим даражаларини аниқлаймиз: , , , , , , , , , , , .
Берилган тармоқ орқали манбадан ўпқонга 4 катталикка эга бўлган оқимни қуйидаги сонлар тўплами билан ифодалаш мумкин: , , , , , , , , , , , , . Қаралаётган оқимнинг миқдори . ■

Тармоқ бўйлаб ўтказиш мумкин бўлган оқимлар орасида миқдори энг катта (максимал) оқимни топиш амалиёт нуқ-таи назаридан катта аҳамиятга эгадир. Бундай оқимлар максимал оқимлар деб аталади. 1- мисолда келтирилган оқим максимал оқим эмас, чунки берилган тармоқ учун миқдори 5 бўлган оқим бор (ушбу параграфнинг охирига қаранг).
Албатта, умумий ҳолда, тармоқда бир неча турли максимал оқимлар бўлиши мумкин.
Максимал оқимни ўрганишда қуйидаги тушунчаларни киритиш мақсадга мувофиқдир. Тўйинган ёй – бу ёй бўйлаб оқим миқдори унинг ўтказиш қобилиятига тенг, тўйинмаган ёй – бу ёй бўйлаб оқим миқдори унинг ўтказиш қобилиятидан кичик.
2- мисол. 1- мисолда қаралган тармоқ учун аниқланган оқимда ва бўлгани учун тўйинмаган, эса тўйинган ёйлардир. ■
Тармоқдаги оқимларни ўрганишда занжир тушунчаси муҳим рол ўйнайди. Бу ерда занжир деганда тармоқдаги йўналиши эътиборга олинмасдан бир-бирига уланган ёйлар кетма-кетлигини тушунамиз. Бирор занжирга тегишли ёйнинг йўналиши занжирдаги учлар кетма-кетлигини ўтиш йўналишига мос тушса, бу ёйни тўғри ёй деб, акс ҳолда эса, уни тескари ёй деб атаймиз.
Тармоқдаги оқимларни тадқиқ қилганда кесим тушунчаси ҳам муҳим ҳисобланади. тармоқнинг орграфи учлари тўплами ни ўзаро кесишмайдиган ҳамда ҳар бири бўш бўлмаган иккита ва қисм тўпламларга ажратамиз, яъни , , ва .
Бошланғич учи тўпламга, охирги учи эса тўпламга тегишли бўлган барча ёйлар тўпламини кесим деб атаймиз. Кесимни билан белгилаймиз.
Агар кесим бўлиб, манба тўпламга, ўпқон эса тўпламга тегишли бўлса, у ҳолда га манбани ўпқондан ажратувчи (ёки айирувчи) кесим деб аталади.
Ҳар бир кесимга қиймати кесимни ташкил этувчи барча ёйлар ўтказиш қобилиятлари йиғиндисига тенг бўлган ва кесимнинг ўтказиш қобилияти (ёки миқдори) деб аталувчи сон мос қўйилиши мумкин:
.
Барча мумкин бўлган кесимлар ичида ўтказиш қобилияти энг кичик бўлганини минимал кесим деб атаймиз.
Тармоқда бир неча турли максимал оқимлар бўлиши мумкин эканлигини юқорида таъкидлаган эдик. Худди шунга ўхшаш, тармоқда бир неча турли минимал кесимлар бўлиши ҳам мумкин.
Равшанки, агар тармоқ бошланғич учи манбада ва охирги учи ўпқонда бўлган занжирдангина иборат бўлса, бу тармоқ бўйлаб ўтказиш мумкин бўлган максимал оқим қиймати шу занжирни ташкил этувчи ёйларнинг ўтказиш қобилиятларининг минимал қиймати билан чегараланган бўлади. Шу туфайли, бу ерда, минимал ўтказиш қобилиятига эга бўлган ёй тармоқнинг (занжирнинг) “тор жойи” деб аталиши жойиздир.
Тармоқдаги манбани ўпқондан ажратувчи кесим ибораси исталган тармоқда “тор жой” иборасининг ўхшаши сифатида қаралиши мумкин.
Фараз қилайлик, – тармоқдаги қандайдир оқим бўлсин. Бу тармоқдаги учдан учга йўналган бирор йўл бўйлаб оқим шу йўл ёйларидаги оқимларнинг энг кичик қиймати сифатида аниқланади:
.
Табиийки, тармоқдаги оқимнинг миқдори учун

тенглик ўринлидир, бу ерда – орграфдаги учдан учга йўналган барча йўллар тўпламидан иборат.
Кесимнинг таърифидан кўриниб турибдики, учдан учга олиб борувчи ихтиёрий йўл шу ва учларни ажратувчи ҳар қандай кесимнинг ҳеч бўлмаганда битта ёйини ўзида сақлайди. Шунинг учун, агар ихтиёрий кесимнинг барча ёйларини тармоқдан олиб ташласак, у ҳолда орграфда учдан учга борадиган бирорта ҳам йўл (ва, демак, оқим ҳам) мавжуд бўлмайди.
Демак, юқорида айтилганларни ҳисобга олиб тармоқдаги оқим миқдори билан ихтиёрий кесимнинг ўтказиш қобилияти узвий боғланган деган хулосага келиш мумкин. Бу боғланиш қуйидаги теоремада ўзининг аниқ ифодасини топган.