Yashiklar prinsipi


Download 0.89 Mb.
bet38/41
Sana18.06.2023
Hajmi0.89 Mb.
#1567410
1   ...   33   34   35   36   37   38   39   40   41
Bog'liq
Graflar nazariyasi

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

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


  1. 2- шаклда тасвирланган тармоқда учни манба, учни эса ўпқон деб ҳисоблаб, ундаги бир неча оқимни аниқланг.


  2. Форд алгоритмни қўллаб 3- шаклда тасвирланган тармоқ учун дан га максимал оқимни анқланг.


  3. Форд алгоритмни қўллаб 2- шаклда тасвирланган тармоқ учун дан га максимал оқимни анқланг.

  4. тармоқда , , – ёйлар кортежи, – ёйнинг ўтказиш қобилияти, эса максимал оқим бўлсин. У вақтда ҳеч бўлмаганда битта ёй топилиб, шу ёй учун тенглик бажарилишини кўрсатинг.

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


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

  1. Дарахтнинг ҳар бир қирраси ҳақида нима дейиш мумкин?

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

  3. Биттадан кўп учга эга бўлган исталган дарахтда қанча даражаси бирга тенг учлар бор?



Download 0.89 Mb.

Do'stlaringiz bilan baham:
1   ...   33   34   35   36   37   38   39   40   41




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling