Yashiklar prinsipi

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