Yashiklar prinsipi

1- теорема. тармоқдаги ихтиёрий оқим миқдори шу тармоқдаги манба ва ўпқонни ажратувчи ҳар қандай кесимнинг ўтказиш қобилиятидан ошмайди, яъни .
Исботи. тармоқдаги оқим таърифидан бевосита қуйидаги тенгликлар келиб чиқади:
, , .
Бу тенгликларнинг мос томонларидаги ифодаларни қўшиб ва ўхшаш ҳадларини ихчамлаб,

тенгликни оламиз. 2) шартни ва эканлигини ҳисобга олсак, охирги тенгликдан муносабат келиб чиқади. ■
Муаммоли топшириқ ва масалалар

1. 
   2- шаклда тасвирланган тармоқда учни манба, учни эса ўпқон деб ҳисоблаб, ундаги бир неча оқимни аниқланг.
   
2. 
   Ф
   орд алгоритмни қўллаб 3- шаклда тасвирланган тармоқ учун дан га максимал оқимни анқланг.
   
3. 
   Ф
   орд алгоритмни қўллаб 2- шаклда тасвирланган тармоқ учун дан га максимал оқимни анқланг.
   
4. 
   тармоқда , , – ёйлар кортежи, – ёйнинг ўтказиш қобилияти, эса максимал оқим бўлсин. У вақтда ҳеч бўлмаганда битта ёй топилиб, шу ёй учун тенглик бажарилишини кўрсатинг.
   
5. 
   тармоқда , , – манба, – ўпқон, – ёйлар кортежи, – ёйнинг ўтказиш қобилияти ва бирор оқим бўлсин. Агар ва ни боғловчи занжирнинг барча тўғри ёйларида ва барча тескари ёйларда эса бўлса, у ҳолда бу занжирга оқимни орттирув-чи йўл деймиз. Берилган оқимнинг максимал оқим бўлиши учун уни орттирувчи йўлнинг топилмаслиги зарур ва етарли эканлигини кўрсатинг.
   

Мустақил таълим мавзулари:

1. 
   Дарахтнинг ҳар бир қирраси ҳақида нима дейиш мумкин?
   
2. 
   Дарахтдаги ўзаро устма-уст тушмайдиган исталган иккита учини нечта оддий занжир билан тутаҳтириш мумкин?
   
3. 
   Биттадан кўп учга эга бўлган исталган дарахтда қанча даражаси бирга тенг учлар бор?