Yashiklar prinsipi

1- лемма (“кўришишлар” ҳақида). Ихтиёрий ориентирланмаган графда барча учлар даражалари йиғиндиси қирралар сонининг икки бараварига тенг.
Агар графнинг учлар тўпламини ўзаро кесишмайдиган шундай иккита қисм тўпламларга (бўлакларга) ажратиш мумкин бўлсаки, графнинг ихтиёрий қирраси бу тўпламларнинг биридан олинган қандайдир учни иккинчи тўпламдан олинган бирор уч билан туташтирадиган бўлса, у ҳолда бундай граф икки бўлакли граф (бихроматик ёки Кёниг графи) деб аталади. Таърифдан кўриниб турибдики, икки бўлакли графнинг ҳар бир бўлагидаги ихтиёрий иккита учлар қўшни бўла олмайди. Бирор бўлагида фақат битта уч бўлган тўла икки бўлакли граф юлдуз деб аталади.
Агар икки бўлакли графнинг турли бўлакларига тегишли исталган иккита учи қўшни бўлса, у ҳолда бу граф тўла икки бўлакли граф деб аталади. Тўла икки бўлакли графни билан белгилаймиз, бу ерда ва билан графнинг бўлакларидаги учлар сонлари белгиланган. граф учун ва бўлиши равшан, бу ерда – графнинг учлари сони, – унинг қирралари сони.
Графнинг икки бўлакли граф бўлиши ҳақидаги баъзи қўшимча маълумотлар (Кёниг теоремаси) ушбу бобнинг 4- параграфида келтирилган.
Иккидан катта ихтиёрий натурал сон учун бўлакли граф тушунчасини ҳам киритиш мумкин.
3. Графлар назариясига оид бошланғич
мисоллар.
1- мисол. Ўзбекистон Республикаси ҳудудидаги аеропортлар тўпламини билан, бу шаҳарлар орасида белгиланган вақт мобайнида амалга оширилаётган самолётларнинг учиб қўниш ҳодисалари кортежини билан белгилаймиз. У ҳолда жуфтликни граф деб қараш мумкин. Бу ерда графнинг учларига аеропортлар, ёйларига эса самолётларнинг учиб қўниш ҳодисалари мос келади. Табиийки, графда каррали ёйлар бўлиши мумкин, агар, қандайдир сабабга кўра, самолёт учган аеропортга қайтиб қўнса, у ҳолда бу ҳодисага қаралаётган графдаги сиртмоқ мос келади. ■