6-ma’ruza. Graflar nazariyasi elementlari va o'tish algoritmlari

22-rasm. Yoʻnaltirilmagan grafda qoʻshnilik matritsasi



23-rasm. Yoʻnaltirilgan 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.4.Insidentlik matritsasi.

Insidentlik matritsasi - bu grafning elementlari (qirra - uch) orasidagi bogʻlanishlar koʻrsatiladigan grafni tasvirlash shakli. Matritsaning ustunlari qirralarga, satrlar uchlarga toʻgʻri keladi. Demak, matritsa kvadrat boʻlmaydi. Matritsa yacheykasidagi nolga teng boʻlmagan qiymat uch va qirra (ularning insidentligi) oʻrtasidagi munosabatni bildiradi.
Graflar insidentlik matritsasini _{ } oʻlchamdagi _{ } toʻrtburchaklar matritsasi sifatida aniqlaylik, bunda _{ } elementi 1 ga teng, agar _{ } insident qirraning _{ } uchi boʻlsa, aks holda 0 boʻladi. B matritsasining satrlari insidentlik vektorlari deb nomlanadi va _{ } bilan belgilanadi. 23-rasmda 21-rasmdagi kabi bir xil G graf koʻrsatilgan va uning B insidentlik matritsasi koʻrsatilgan.


24-rasm. Grafda insidentlik matritsasi
Ta’rifdan koʻrinib turibdiki, insidentlik matritsasidagi birlarning umumiy soni graf qirralarining ikki baravariga teng, har qanday satrdagi birlar miqdori mos uchlar darajalariga teng, ustunlar esa ikkita birdan iborat.
Shuning uchun matritsa satrlari orasida oddiy munosabat mavjud: har qanday satr elementlarini ikki modulli qoʻshish orqali qolgan satrlarning bir xil elementlarining qoʻshnilarini olish mumkin. Insidentlik vektori tushunchasidan foydalangan holda, _{ } (mod 2), bu yerda _{ } va _{ }. Shunday qilib, yuqoridagi matritsa uchun bizda:  .
Bogʻlanmagan grafning insidentlik matritsasi, xuddi qoʻshnilik matritsasi singari, blok-diagonali koʻrinishga keltirilishi mumkin, bu yerda har bir diogonal blok ba’zi bir bogʻlangan komponentlarning insidentlik matritsasi hisoblanadi.
Grafda parallel qirralar boʻlmaganligi sababli, agar _{ } va _{ } uchlar qoʻshni boʻlsa, har qanday _{ } insidentlik vektorlari jufligi skalar koʻpaytmasi birga teng boʻladi va agar bu uchlar qoʻshni boʻlmasa, skalar koʻpaytma nolga teng boʻladi. Binobarin, _{ } koʻpaytma graflarning qoʻshnilik matritsasiga toʻgʻri keladigan mos darajalariga teng boʻlgan diagonal elementlar bundan mustasno.
Yoʻnaltirilgan graf holatida tegishli ustundagi har bir uch chiquvchi x vertikal qatorida "−1" va kiruvchi y uch qatorida "1" qiymatiga ega; agar uch va qirra oʻrtasida hech qanday bogʻliqlik boʻlmasa, unda mos keladigan katak "0" qiymatiga ega boʻladi.