Yashiklar prinsipi

Режа:

1. 
   Тармоқ тушунчаси.
   
2. 
   Тармоқдаги оқимлар.
   
3. 
   1-Теорема.
   

Калит сўзлар: Граф, уч, қирра, орграф, ёй, тармоқ, тўплам, блок-схема, гиперграф, боғламли тармоқ, сиртмоқ, ёйнинг ўтказиш қобилияти, учнинг чиқиш ва кириш ярим даражалари, манба, ўпқон, тармоқдаги оқим, ёй бўйлаб оқим, тармоқдаги оқим миқдори, максимал оқим, тўйинган, тўйинмаган, тўғри ва тескари ёйлар, занжир, тармоқнинг “тор жойи”, кесим, манбани ўпқондан ажратувчи кесим, кесимнинг ўтказиш қобилияти, минимал кесим.
1. Тармоқ тушунчаси. Графлар назариясида ҳозиргача баъзи иборалар бўйича умумий келишув қарор топмаганлигини қайд қилган эдик. Бу фикр графлар назариясининг тармоқ ва тармоққа оид тушунчалари билан иш кўрганда яққол намоян бўлади. Баъзан, “тармоқ” ибораси ўрнига “тўр” иборасини ҳам қўллайдилар. Масалан, С.В. Яблонскийнинг 1986 йилда босилиб чиққан Введение в дискретную математику (Дискрет математикага кириш) номли ўқув қўлланмасида граф тушунчаси умумлаштирилиб, тармоқнинг қуйидаги таърифи берилган ва “тармоқ” тушунчаси хусусида фикрлар ҳам баён қилинган.
“Берилган тўплам ва ҳар бир элементи дан олинган мажмуани (наборни) тармоқ деб атаймиз ва билан белгилаймиз, бу ерда . тўпламнинг объектлари тармоқнинг учлари деб, мажмуадаги объектлар эса – тармоқнинг қутблари деб аталади”.
Юқорида эслатилган китобда таъкидланишича: “Адабиётда тармоқ тушунчасига яқин тушунчалар ҳам учрайди, масалан, “блок-схема” тушунчаси, “гиперграф” тушунчаси. Блок-схема тушунчаси тармоқ тушунчасидан олдин пайдо бўлган, гиперграф тушунчаси эса – кейинроқ”.
Гиперграф тушунчаси – бу граф тушунчасининг шундай умумлашмасики, бунда қирралар на фақат икки элементли бўлишлари, улар учлар тўпламининг исталган қисм тўпламлари бўлишлари ҳам мумкин.
Граф тушунчасининг турли умумлашмаларини маъқуллаган ҳамда бундай умумлашмалар турли масаларни ҳал этишда зарур қурол сифатида ишлатилишини таъкидлаган ҳолда [10] китобдаги тармоқ тушунчасининг бир-бирига эквивалент бўлган қуйидаги икки таърифини келтирамиз:
1) ҳар бир ёйига манфиймас ҳақиқий сон мос қўйилган орграф тармоқ деб аталади;
2) тармоқ деб шундай жуфтликка айтиладики, бунда – орграф, эса орграфнинг ёйлари тўпламини манфиймас ҳақиқий сонлар тўпламига акслантирувчи функсия.