15-ma’ruza. Graflarning berilish usullari. Qo‘shnilik va insidentlik matritsalari. Graflarning izomorfligi (2 soat). Reja


Download 103.97 Kb.
bet4/6
Sana31.01.2024
Hajmi103.97 Kb.
#1833017
1   2   3   4   5   6
Misol. 1- shaklda tasvirlangan oriyentirlanmagan multigraf uchlari qo‘shniligi matritsasi quyidagicha bo‘ladi:
.
Bizga G yo`naltirilmagan, chekli graf berilgan bo`lsin. Aytaylik, (v1,…,vn), G grafning uchlari bo`lsin. U holda insidentlik matritsasi ||Aij|| (i=1,...,m, j=1,..., n) deb m ta qator va n ta ustundan iborat quyidagi ko`rinishda hosil qilingan matritsaga aytiladi:
a) Aij matritsaning satrlariga G ning uchlari, ustunlariga G ning qirralari mos qo`yiladi;
b) U holda
Aij=
qoidadan foydalanib, intsidentlik matritsasini hosil qilamiz.


Misol 1.

Agar G yo`naltirilgan graf bo`lsa, u holda
Aij=
qoidadan foydadanib insidentlik matritsasini hosil qilamiz.
Misol 2.



Oriyentirlangan graf uchun insidentlik matritsasi deb har bir elementi aij quyidagicha aniqlangan [n * m] tartibli to`g`ri burchakli matritsaga aytiladi, bu erda n – uchlar to`plamining quvvati, m – qirralar to`plamining quvvati



agar xi ui uchning boshi bo`lsa,

agar xi ui uchning oхiri bo`lsa,

agar xi ui qirraga insident bo`lmasa.



Misol 3. Rasmda tasvirlangan graf uchun insidentlik matritsasini yozamiz:

Buning uchun qirralarni u1, u2,…, u6 bilan belgilab chiqamiz. Insidentlik matritsasining ko`rinishi quyidagicha bo`ladi.




Download 103.97 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6




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