Yashiklar prinsipi

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