Axborotlarga ishlov berish va boshqarish” kafedrasi tizimlarnazari ya s I fanidan Sirtqi ta’lim yo‘nalishi uchun Ma’ruza matni 5330200-«Informatika va axborot texnologiyalari»

3.4.1-misol:
3.4.1-rasm. Yo`naltirilmagan graf.
3.4.1-jadval.
Yo`naltirilmagan graf uchun qo`shmalik matritsasi jadvali.

	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 yo`naltirilgan graf bo`lsa, u holda
(3.4.2)

( 3.4.2.)-qoidadan foydalanib qo`shmalik matritsasini hosil qilamiz.

3.4.2-misol.

3.4.2-rasm. Yo`naltirilgan graf.

3.4.2-jadval.
Yo`naltirilgan graf uchun qo`shmalik matritsasi jadvali.

	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	0	0	1	0	-1	0	0
e5	0	0	1	0	0	-1	0
e6	0	0	1	0	0	0	-1
e7	0	0	0	0	0	0	2

3.4.2. Qo`shnilik matritsasi.
Faraz qilaylik, yo`naltirilmagan graf bo`lsin. Grafning qo`shnilik matritsasida ning ustunlariga ham qatorlariga ham grafning tugunlarini mos qo`yamiz. U xolda


(3.4.3)


(3.4.3)-qoidadan foydalanib qo`shnilik matritsasini hosil qilamiz.
3.4.3-misol: 3.4.1-rasmda keltirilgan yo`naltirilmagan graf uchun qo`shnilik matritsasi quyidagicha bo`ladi:

3.4.3-jadval.

Yo`naltirilmagan graf uchun qo`shnilik matritsasi jadvali.

	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

yo`naltirilgan graf bo`lsin. U holda qo`shnilik matritsasi ning ustunlariga ham satrlariga ham grafning tugunlarini mos qo`yamiz.
U holda,


(3.4.4)


(3.4.4)-qoidadan foydadanib qo`shnilik matritsasini hosil qilamiz.
3.4.4-misol: 3.4.2-rasmda keltirilgan yo`naltirilgan graf uchun qo`shnilik matritsasi quyidagicha bo`ladi.

3.4.4-jadval.

Yo`naltirilgan graf uchun qo`shnilik matritsasi jadvali.

	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

3.4.3. Graf yoylari ro`yhati va uzunlik matritsasi.
Ro`yhatda grafning barcha tugunlari keltiriladi. Ro`yhatning jadval ko`rinishda tasvirlash qulayroq bo`lib, bunda qo`shni tugunlar juft holda belgilanadi [8].
Agar graf yo`naltirilgan bo`lsa, u holda har bir juftlikda birinchi yoyning boshlang`ich tuguni ikkinchi tugash tuguni nomeri ko`rsatiladi.
Agar graf izolyatsiyalangan tugunlar bo`lsa, u holda ular alohida ko`rsatilgan bo`lishi shart.
Uzunlik matritsasi. Bu kvadrat matritsa bo`lib, uning umumiy elementi quyidagicha bo`ladi.


(3.4.5.)
Bu erda -yoy uzunligi.
3.4.5.-misol. 3.5.3-rasmdagi grafni yoylar ro`yhati va uzunlik matritsasi shaklida ifodala

3.4.3-rasm. 3.4.5-misolning grafi.

3.4.5-jadval.

Grafning yoylar uzunligi ro`yhati usulida tasvirlash.

X1	X2	X2	X4	X4	X5
X2	X3	X6	X3	X6	X4

3.4.6-jadval.

Grafning uzunlik matritsasi jadvali.

A=		X1	X2	X3	X4	X5	X6
	X1		U1
	X2	-U1		U2
	X3		-U2		-U5
	X4			-U5		-U6	U4
	X5				U6
	X6				-U4

3.5. Graflarda yo`l va konturlar.
Grafdagi yo`l deb 2 ta ixtiyoriy va tugunlarni bog`lab turuvchi yoylar ketma-ketligiga aytiladi va u harfi bilan belgilanadi.
3.5.1-misol. Quyidagi grafdagi X<sub>1</sub> tugundan X<sub>4</sub> tugungacha bo`lgan yo`llarni hisoblaylik.

3.5.1-rasm. Grafga misollar

Agar bitta yo`ldagi yoy takrorlanmasa, bunday yo`l sodda yo`l deb ataladi.

Agar yo`lda hech bir tugun bir martadan ortiq qatnashmasa, bunday yo`l elementar, aks holda esa noelementar yo`l deyiladi. Yo`llar tugallangan va tugallanmagan bo`ladi.
Boshlanishi va oxirgi tugunlari umumiy bo`lsa bunday yo`l kontur deyiladi.
3.51-rasmda berilgan graf uchun konturlar quyidagicha aniqlanadi:




Konturni ham yoylar va tugunlar ketma-ketligi sifatida berish mumkin. Agar yoylar ketma-ketligi ixtiyoriy tugundan faqat bir martagina o`tsa, bunday kontur oddiy (elementar) kontur deyiladi.
Agar graflardagi yoylarga mos bir qancha sonli koeffisientlar yoki funksiyalar qo`yilgan bo`lsa (yoy ogirligi), bunday graf yuklangan (vzveshenniy) deyiladi. Yo`l yoki kontur uchun uning uzunligi tushunchasi mavjud bo`lib, uni quyidagi ikki usul orqali aniqlash mumkin:
1. Yo`l uzunligi uning tarkibidagi yoylar soniga teng.
2. Yuklangan graflar uchun uning tarkibidagi yoylar uzunliklari (og`irliklari) ko`paytmasi (ba`zida yigindasi)ga teng bo`ladi.