Yashiklar prinsipi

9- мисол. 2- шаклда тасвирланган орграфнинг учлари қўшнилиги матритсаси қуйидагича бўлади:
. ■
Енди учлари бўлган белгиланган ориентирланмаган мултиграф бўлсин. элементлари графнинг ва учларини туташтирувчи қирралар сонига тенг бўлган ( ) матритса ориентирланмаган мултиграфнинг учлари қўшнилиги матритсаси деб аталади.
10-мисол. 1- шаклда тасвирланган ориентирланмаган мултиграф учлари қўшнилиги матритсаси қуйидагича бўлади:
. ■
Каррали ёйлари бўлган сиртмоқсиз орграф учлари қўшнилиги матритсаси тушунчасини ҳам юқоридагига ўхшаш таърифлаш мумкин.
2- теорема. Графлар фақат ва фақат учлари қўшнилиги матритсалари бир-бирларидан сатрларининг ўринларини ва устунларининг ўринларини мос алмаштиришлар ёрдамида ҳосил бўлсагина изоморф бўлишади.
Исботи. Абстракт графга, унинг учларини белгилашга (рақамлашга) боғлиқ равишда, турлича қўшнилик матритсалари мос келиши табиийдир. Бу матритсаларни солиштириш мақсадида ҳар бирининг та учлари бўлган ихтиёрий иккита белгиланган, ўзаро изоморф ва графларни қараймиз. ва графлар учларига мос қўйилган белгилар турлича ва улардан бири бошқасидан учларнинг қўшнилигини сақловчи қандайдир қоидани қўллаб ҳосил қилинган бўлсин, яъни графдаги ва учлар фақат ва фақат графнинг ва учлари қўшни бўлсагина қўшни бўлсин. графнинг учлари қўшнилиги матритсасини ( ) билан графнинг учлари қўшнилиги матритсасини эса ( ) билан белгиласак, ўринли бўлади. ■
Шундай қилиб, манфиймас бутун сонлардан ташкил топган ва граф учун учлари қўшнилиги матритсаси бўлган квадрат матритса билан граф орасида бир қийматли мослик (изоморфлик аниқлигида) бор деган хулоса ва, бундан, графлар назарияси бўйича изланишлар махсус шартларни қаноатлантирувчи мат-ритсаларни тадқиқ қилишга келтирилиши мумкинлиги келиб чиқади.
( ) қирраларга эга яккаланган учлари, сиртмоқ ва каррали қирралари бўлмаган граф учун элементлари

қуйидагича аниқланган ( , ) -матритса графнинг қирралари қўшнилиги матритсаси деб аталади.