Yashiklar prinsipi

11- мисол. 12- шаклда тасвирланган графда 5та қирра бўлиб, унинг қирралари қўшнилиги матритсаси

кўринишга эгадир. ■
Равшанки, сиртмоқсиз ва каррали қирраларсиз граф қирралари қўшнилиги матритсаси бош диагоналга нисбатан симметрик квадрат матритсадир ва унинг бош диагонали ноллардан иборат.
4. Инсидентлик матритсалари. Учлари ва қирралари ( ) бўлган белгиланган граф берилган бўлсин. Бу графнинг учларига сатрлари, қирраларига эса устунлари мос келувчи ва элементлари

кўринишда аниқланган ( , ) матритса графнинг инсидентлик матритсаси деб аталади.
12- мисол. 1- шаклда тасвирланган графнинг инсидентлик матритсаси қуйидагича бўлади:
. ■
Енди учлари ва қирралари ( ) бўлган белгиланган сиртмоқсиз орграфни қараймиз. Элементлари

кўринишда аниқланган ( , ) матритсага графнинг инсидентлик матритсаси деб аталади.
13- мисол. 11- шаклда тасвирланган графнинг инсидентлик матритсаси қуйидагича бўлади:
. ■
3- теорема. Графлар (орграфлар) фақат ва фақат инсидентлик матритсалари бир-бирларидан сатрларининг ўринларини ва устунларининг ўринларини мос алмаштиришлар ёрдамида ҳосил бўлсагина изоморф бўлишади.
Исботи 2- теореманинг исботига ўхшаш бажарилади. ■
Глоссарий:

Термин	Ўзбек тилидаги шархи
Граф	жуфтликка айтиладики, бу ерда ва – ( , ) кўринишдаги жуфтликлар кортежи бўлиб, тўпламнинг элементларидан тузилган тўплам.
Графнинг учлари	графда тўпламнинг элементлари.
Йўналтирилмаган (ориентирланмаган) қирра	бўладиган жуфтлик.
Қўшни қирралар	умумий четга эга бўлган иккита қирра (ёй).
Сиртмоқ	графнинг элементи