13-amaliy mashg’ulot. Graflarni analitik usulda berilishiga ko’ra chizish. Oddiy graf. Multigraf, psevdograf. Graf uchlarining darajalari va kirralari sonini topish. Graflar ustida amallar. Graflarning qo’shnilik va insidentlik matrisalari

13.3-Misol:

• 
  – multigraf, – psevdograf, – oriyentirlangan multigraf.
  

13.12-Ta’rif. Agar V to`plamning quvvati n ga teng bo`lsa, n soni grafning tartibi deyiladi.
13.13-Ta’rif. Agar V to`plamning quvvati n ga teng bo`lsa, E to`plamning quvvati m ga teng bo`lsa, graf (n, m) graf deyiladi.
13.14- Ta’rif. Agar berilgan uch qirraning oхiri bo`lsa, qirra va uch intsident deyiladi.


Qo‘shmalik(insidentlik) matritsasi. Bizga G yo‘naltirilmagan graf berilgan bo‘lib, u chekli bo‘lsin. Aytaylik (a₁,…,a_n), G grafning qirralari bo‘lsin. U holda qo‘shmalik matritsasi ||A_ij||, i=1,m, j=1, n m ta qator va n ta ustundan iborat bo‘ladi, A_ij matritsaning ustunlariga G ning tugunlari, qatorlariga G ning qirralarini mos qo‘yamiz. U holda
A_ij=
q oidadan foydadanib qo’shmalik matritsasini hosil qilamiz.
13.3-Misol.

	a1	a2	a3	a4	a5	a6	a7
e1	1	1	0	0	0	0	0
e2	1	0	1	0	0	0	0
e3	0	1	0	1	0	0	0
e4	1	0	0	0	1	0	0
e5	0	1	0	0	0	1	0
e6	0	0	1	1	0	0	0
e7	0	0	1	0	1	0	0
e8	0	0	0	1	0	1	0
e9	0	0	0	0	1	0	1
e10	0	0	0	0	0	1	1

Agar G yo‘naltirilgan graf bo‘lsa, u holda

A_ij= qoidadan foydadanib qo’shmalik matritsasini hosil qilamiz.


13.4-Misol.

	A1 a2 a3 a4 a5 a6 a7
e1	-1 1 1 0 0 0 0
e2	-1 0 0 0 0 0 0
e3	0 -1 0 1 0 0 0
e4	0 0 -1 0 1 0 0
e5	0 0 -1 0 0 1 0
e6	0 0 -1 1 0 0 1
e7	0 0 0 0 0 0 2

Qo‘shnilik matritsasi. Faraz qilaylik G graf yo‘naltirilmagan bo‘lsin. Grafning qo‘shnilik matritsasida A_ij ning ustunlariga ham qatorlariga ham grafning tugunlarini mos qo‘yamiz. U xolda
A_ij=
qoidadan foydadanib qo’shnilik matritsasini hosil qilamiz.
13.5-Misol. 13.1-rasmda keltirilgan yo‘naltirilmagan graf uchun qo’shnilik matritsasi quyidagicha bo’ladi.

	a1 a2 a3 a4 a5 a6 a7
a1	0 1 1 0 1 0 0
a2	1 0 0 1 0 1 0
a3	1 0 0 1 1 0 0
a4	0 1 1 0 0 1 0
a5	1 0 1 0 0 0 1
a6	0 1 0 1 0 0 1
a7	0 0 0 0 1 1 0

G yo‘naltirilgan graf bo‘lsin. U holda qo‘shnilik matritsasi A_ij ning ustunlariga ham satrlariga ham grafning tugunlarini mos qo‘yamiz. Uholda

qoidadan foydadanib qo’shnilik matritsasini hosil qilamiz.


13.6-Misol. 13.2-rasmda keltirilgan yo‘naltirilgan graf uchun
qo’shnilik matritsasi quyidagicha bo’ladi.

	a1 a2 a3 a4 a5 a6 a7
a1	0 1 1 0 0 0 0
a2	0 0 0 1 0 0 0
a3	0 0 0 0 1 1 1
a4	0 0 0 0 0 0 0
a5	0 0 0 0 0 0 0
a6	0 0 0 0 0 0 0
a7	0 0 0 0 0 0 1

2. 
   Mustaqil bajarish uchun masala va topshiriqlar
   

1. 
   Graflar ustida amallar
   

Quyidagi keltirilgan yunaltirilgan va yunaltirilmagan graflar uchun:
1) Grafni tuldiruvchisini toping.
2) Grafni kism grafini toping.
3) Ko’shmalik matritsani tuzing.
4) Ko’shnilik matritsani tuzing.

































29)