Yashiklar prinsipi


Download 0.86 Mb.
bet10/43
Sana18.06.2023
Hajmi0.86 Mb.
#1567285
1   ...   6   7   8   9   10   11   12   13   ...   43
Bog'liq
Dirixle prinsipi Dirixle prinsipi

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

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

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

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

Термин

Ўзбек тилидаги шархи

Граф

жуфтликка айтиладики, бу ерда ва – ( , ) кўринишдаги жуфтликлар кортежи бўлиб, тўпламнинг элементларидан тузилган тўплам.

Графнинг учлари

графда тўпламнинг элементлари.

Йўналтирилмаган (ориентирланмаган) қирра

бўладиган жуфтлик.

Қўшни қирралар

умумий четга эга бўлган иккита қирра (ёй).

Сиртмоқ

графнинг элементи



Download 0.86 Mb.

Do'stlaringiz bilan baham:
1   ...   6   7   8   9   10   11   12   13   ...   43




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling