11- мисол. 12- шаклда тасвирланган графда 5та қирра бўлиб, унинг қирралари қўшнилиги матритсаси
кўринишга эгадир. ■
Равшанки, сиртмоқсиз ва каррали қирраларсиз граф қирралари қўшнилиги матритсаси бош диагоналга нисбатан симметрик квадрат матритсадир ва унинг бош диагонали ноллардан иборат.
4. Инсидентлик матритсалари. Учлари ва қирралари ( ) бўлган белгиланган граф берилган бўлсин. Бу графнинг учларига сатрлари, қирраларига эса устунлари мос келувчи ва элементлари
кўринишда аниқланган ( , ) матритса графнинг инсидентлик матритсаси деб аталади.
12- мисол. 1- шаклда тасвирланган графнинг инсидентлик матритсаси қуйидагича бўлади:
. ■
Енди учлари ва қирралари ( ) бўлган белгиланган сиртмоқсиз орграфни қараймиз. Элементлари
кўринишда аниқланган ( , ) матритсага графнинг инсидентлик матритсаси деб аталади.
13- мисол. 11- шаклда тасвирланган графнинг инсидентлик матритсаси қуйидагича бўлади:
. ■
3- теорема. Графлар (орграфлар) фақат ва фақат инсидентлик матритсалари бир-бирларидан сатрларининг ўринларини ва устунларининг ўринларини мос алмаштиришлар ёрдамида ҳосил бўлсагина изоморф бўлишади.
Исботи 2- теореманинг исботига ўхшаш бажарилади. ■
Глоссарий:
Термин
|
Ўзбек тилидаги шархи
|
Граф
|
жуфтликка айтиладики, бу ерда ва – ( , ) кўринишдаги жуфтликлар кортежи бўлиб, тўпламнинг элементларидан тузилган тўплам.
|
Графнинг учлари
|
графда тўпламнинг элементлари.
|
Йўналтирилмаган (ориентирланмаган) қирра
|
бўладиган жуфтлик.
|
Қўшни қирралар
|
умумий четга эга бўлган иккита қирра (ёй).
|
Сиртмоқ
|
графнинг элементи
|
Do'stlaringiz bilan baham: |