|
Algoritmlarni loyihalash fanidan mustaqil ishi
|
| bet | 3/10 | | Sana | 27.05.2024 | | Hajmi | 0,61 Mb. | | #254553 |
Bog'liq algoritm.MIQoʻshnilik matritsasi. Qoʻshnilik matritsasini n-tartibli A=[ai,aj] nosimmetrik kvadrat matritsa sifatida aniqlaymiz, unda ai,j elementlar 1 ga teng, agar grafda {vi,vj } qirrasi boʻlsa, ya‘ni vi va vj qoʻshni boʻlsa, 0 ga teng, agar bunday qirra mavjud boʻlmasa.
Ta‘rifdan kelib chiqadiki, har qanday i uchun ∑nj=1ai,j = 𝑑(vi) , har qanday j uchun ∑ni=1ai,j = 𝑑(vj) va ∑ni=1∑nj=1ai,j =2m, ya‘ni qoʻshnilik matritsasining har qanday qatori yoki ustunidagi birlar soni 86 grafning tegishli vertikal darajasiga teng va ularning umumiy soni uning qirralarining ikki baravariga teng. Misol sifatida –rasmda berilgan grafning A qoʻshnilik matritsasini 𝑑 darajalar ketma-ketligini yozamiz
4-rasm. Grafni qo’shnilik matritsasi orqali tasvirlash
Qoʻshnilik matritsasi orgrafni tavsiflash uchun ham, yoʻnaltirilmagan grafni tasvirlash uchun ham mos keladi. Yoʻnaltirilmagan graf uchun elementlarning qiymatlari asosiy diagonalga nisbatan nosimmetrikdir.
Qoʻshnilik matritsadan foydalanish faqat qirralari koʻp boʻlmagan hamda murakkab boʻlmagan graflar uchun afzalroqdir, chunki u har bir element uchun bitta bit saqlashni talab qiladi. Agar graf murakkab boʻlsa, unda xotiraning katta qismi nollarni saqlashga sarflanadi, ammo murakkab graflarda qoʻshnilik matritsasi grafni xotirada ixchamroq ifodalaydi va taxminan n2 bit xotiradan foydalanadi. Ushbu kattalik qoʻshnilik roʻyxatlariga qaraganda yaxshiroq (pastga qarang).
5-rasm. Yo’naltirilmagan grafda qo’shnilik matritsasi
Qoʻshnilik matritsasini amalga oshirish uchun massivlar massivi qoʻllaniladi: vektorlar vektori (vector>) yoki kaliti uchlar soni, qiymati esa vektori. Agar grafni kengaytirish kerak boʻlmasa, u holda vektorni array (massiv) bilan almashtirish kerak.
6-rasm. Yo’naltirilgan grafda qo’shnilik matritsasi
|
| |
