Yashiklar prinsipi

2 - мисол. Геометрик ифодаланиши 2- шаклдаги кўринишда бўлган ориентирланган графни қараймиз. Бу графда ўн битта элемент бор: 5та уч ва 6та ёй, яъни шаклда (5,6)-орграф берилган. Бу графни билан белгилаймиз, бу ерда , ёки . Берилган орграфда сиртмоқ ҳам, каррали ёйлар ҳам йўқ. Бу графнинг ёйи учун 1 бошланғич, 3 уч эса охирги учдир. ■
4
- мисол. 3- шаклда тасвирланган графлар бир-бирига изоморфдир. ■
5- мисол. 6- шаклда тасвирланган графларнинг ҳар бири олтита уч ва еттита қирраларга эга бўлиб, улар изоморф эмас. ■
Ҳ аммаси бўлиб бешта қавариқ мунтазам кўпёқли мавжудлиги қадимдан маълум (Евклид исботлаган): тетраедр, куб, октаедр, додекаедр ва икосаедр. Бу кўпёқлиларнинг умумий номи ҳам бор – Платон жисмлари. Шуниси қизиқки, барча Платон жисмларига мос графлар текисликда геометрик ифодаланади. Масалан, тетраедр ва кубга мос графларнинг геометрик ифодаланиши 5- шаклда тасвирланган.
Д арвоқе, Платон жисмларидан тетраедр, куб ва додекаедр кубик графга мисол бўлади.
Петерсен графи деб аталувчи 6- шаклда тасвирланган граф ҳам кубик графдир.
Агар граф текисликда геометрик ифодаланишга эга бўлса, у ҳолда бундай граф текис (ясси) граф деб аталади. Бундай граф текисликда ётувчи граф деб ҳам аталиши мумкин.
Б
ошқача сўзлар билан айтганда, текис графнинг барча учлари бир текисликда ётади ҳамда барча қирралари (ёйлари) ўша текисликда ётувчи ўзаро кесишмайдиган узлуксиз чизиқлар бўлиб, улар фақат ўзлари инсидент бўлган учлардагина умумий нуқталарга эга.
Платон жисмларига мос барча графлар текис графлардир.
Текис графга изоморф граф планар граф деб аталади.
Текис бўлмаган графга ажойиб мисол учта уй ва учта қудуқ ҳақидаги бошқотирма масалага мос графдир. Учта , , уйлар ва учта , , қудуқлар бор. Ҳар бир уйдан ҳар бир қудуққа ихтиёрий иккитаси кесишмайдиган қилиб узлуксиз йўлакчалар ўтказиш мумкинми?
Қ
оғозда масала шартини қаноатлантирадиган графни чизишга уринишлар муваффақиятсиз тугайди. Шундай уринишлардан бири 7- шаклда келтирилган.
Дарвоқе, учта уй ва учта қудуқ ҳақидаги бошқотирма масалага мос граф ҳар бир бўлагида учтадан учи бўлган икки бўлакли тўла графга мисол бўла олади.
Т екис бўлмаган графга яна бир мисол бешта учга эга бўлган тўла граф – графдир. Бу графнинг ўнта қирралари борлиги равшан. Бу ерда ҳам графни ҳеч қайси иккита қирралари кесишмайдиган қилиб текисликда чизиш муваффақиятсиз тугайди. 8- шаклда графнинг тўққизта қирраси кесишмайдиган узлуксиз чизиқлар қилиб чизилган, лекин ўнинчи чизиқ эса узилишларга эга, унга текисликда «жой йўқ»!