Yashiklar prinsipi

2 - мисол. 2- шаклда тасвирланган граф 1- шаклда ифодаланган граф учун тўлдирувчи графдир.
Графлар устида шундай амалларни бажариш мумкинки, улар элементлари сони берилган графдагидан кўпроқ бўлган бошқа графларнинг ҳосил бўлишига олиб келади. Бундай амаллар қаторига учни қўшиш амали ёки қиррани (ёйни) қўшиш амалини киритиш мумкин.
Графга янги учни қўшиш турлича усул билан амалга оширилиши мумкин. Масалан, янги учни берилган графга қўшиш шу графнинг ва учларига инсидент бўлган қандайдир қиррасига қўшиш орқали қуйидагича икки босқичда бажарилиши мумкин:
1) қирра берилган графдан олиб ташланади;
2) ҳосил бўлган графга иккита янги қирралар: ва учларга инсидент қирра ҳамда ва учларга инсидент қирра қўшилади.
Бу жараён графда қиррага даражаси 2 бўлган янги учни қўшиш (киритиш) ёки қиррани иккига бўлиш амали деб аталади.
Агар граф графдан қиррани иккига бўлиш амалини чекли марта кетма-кет қўллаш воситасида ҳосил қилинган бўлса, у ҳолда граф графнинг бўлиниш графи деб аталади.
Бўлиниш графлари изоморф бўлган графлар гомеоморф графлар деб аталади.
3
- шаклда тасвирланган графлар изоморф эмас, лекин улар гомеоморф, чунки бу графларнинг ҳар бири 4- шаклда тасвирланган бўлиниш графига эга.
2 . Графларни бирлаштириш.
ва графлар берилган бўлсин. Учлари тўплами ва қирралари (ёйлари) кортежи каби аниқланган⁴ граф ва графларнинг бирлашмаси (уюшмаси) деб аталади ва кўринишда белгиланади.
3- мисол. 5- шаклда учлари тўпламлари кесишмайдиган ва графларнинг бирлашмаси амали тасвирланган. ■
4 - мисол. Учлари тўпламлари кесишадиган графларнинг бирлашмаси амали 6- шаклда тасвирланган. ■
А
гар бирлаштирилаётган графларнинг учлари тўпламлари кесишмаса, у ҳолда бу графларнинг бирлашмаси дизъюнкт бирлашма деб аталади. Масалан, 5- шаклда тасвирланган бирлашма дизъюнкт, 6- шаклдаги бирлашма эса – дизъюнкт эмас.